Computational experience with bank-one positive definite quasi-newton algorithms

Rank-one positive definite Quasi-Newton algorithms for unconstrained minimization of the type described by Kleinmichel and Spedicato are numerically evaluated versus the BFS algorithm. Results show that, while on certain functions some rank-one methods perform better, overall the BFS still comes first, its superiority being more evident for larger dimensional problems.     

A linear programming approach for linear programs with probabilistic constraints

We study a class of mixed-integer programs for solving linear programs with joint probabilistic constraints from random right-hand side vectors with finite distributions. We present greedy and dual heuristic algorithms that construct and solve a sequence of linear programs. We provide optimality gaps for our heuristic solutions via the linear programming relaxation of the extended mixed-integer formulation of Luedtke et al. (2010) [13] as well as via lower bounds produced by their cutting plane method. While we demonstrate through an extensive computational study the effectiveness and scalability of our heuristics, we also prove that the theoretical worst-case solution quality for these algorithms is arbitrarily far from optimal. Our computational study compares our heuristics against both the extended mixed-integer programming formulation and the cutting plane method of Luedtke et al. (2010) [13]. Our heuristics efficiently and consistently produce solutions with small optimality gaps, while for larger instances the extended formulation becomes intractable and the optimality gaps from the cutting plane method increase to over 5%.     

The chance constrained critical path with location-scale distributions

The Chance Constrained Critical Path (CCCP) generally depends on the preassigned minimum probability level. It is shown that for a wide class of probability distributions there always exists a probability value for which the CCCP remains unchanged for all probabilities greater than or equal to that value. This probability value is easily obtained from an optimal solution of a simple network problem. In addition, necessary and sufficient conditions for the CCCP to be unconditionally independent of the minimum probability level are given for that class of probability distributions.     

Optimality and duality with generalized convexity

Hanson and Mond have given sets of necessary and sufficient conditions for optimality and duality in constrained optimization by introducing classes of generalized convex functions, called type I and type II functions. Recently, Bector defined univex functions, a new class of functions that unifies several concepts of generalized convexity. In this paper, optimality and duality results for several mathematical programs are obtained combining the concepts of type I and univex functions. Examples of functions satisfying these conditions are given.     

Computations with disjunctive cuts for two-stage stochastic mixed 0-1 integer programs

Two-stage stochastic mixed-integer programming (SMIP) problems with recourse are generally difficult to solve. This paper presents a first computational study of a disjunctive cutting plane method for stochastic mixed 0-1 programs that uses lift-and-project cuts based on the extensive form of the two-stage SMIP problem. An extension of the method based on where the data uncertainty appears in the problem is made, and it is shown how a valid inequality derived for one scenario can be made valid for other scenarios, potentially reducing solution time. Computational results amply demonstrate the effectiveness of disjunctive cuts in solving several large-scale problem instances from the literature. The results are compared to the computational results of disjunctive cuts based on the subproblem space of the formulation and it is shown that the two methods are equivalently effective on the test instances.     

Column generation approaches to ship scheduling with flexible cargo sizes

We present a Dantzig–Wolfe procedure for the ship scheduling problem with flexible cargo sizes. This problem is similar to the well-known pickup and delivery problem with time windows, but the cargo sizes are defined by intervals instead of by fixed values. The flexible cargo sizes have consequences for the times used in the ports because both the loading and unloading times depend on the cargo sizes. We found it computationally hard to find exact solutions to the subproblems, so our method does not guarantee to find the optimum over all solutions. To be able to say something about how good our solution is, we generate a bound on the difference between the true optimal objective and the objective in our solution. We have compared our method with an a priori column generation approach, and our computational experiments on real world cases show that our Dantzig–Wolfe approach is faster than the a priori generation of columns, and we are able to deal with larger or more loosely constrained instances. By using the techniques introduced in this paper, a more extensive set of real world cases can be solved either to optimality or within a small deviation from optimality.     

Linear programming with variable matrix entries

We consider linear programming (continuous or integer) where some matrix entries are decision parameters. If the variables are nonnegative the problem can be easily solved in two phases. It is shown that direct costs on the matrix entries make the problem NP-hard. Finally, a strong duality result is provided.     

Finding and identifying optimal inventory levels for systems with common components

In this article, we consider the problem of finding the optimal inventory level for components in an assembly system where multiple products share common components in the presence of random demand. Previously, solution procedures that identify the optimal inventory levels for components in a component commonality problem have been considered for two product or one common component systems. We will here extend this to a three products system considering any number of common components. The inventory problem considered is modeled as a two stage stochastic recourse problem where the first stage is to set the inventory levels to maximize expected profit while the second stage is to allocate components to products after observing demand. Our main contribution, and the main focus of this paper, is the outline of a procedure that finds the gradient for the stochastic problem, such that an optimal solution can be identified and a gradient based search method can be used to find the optimal solution.     

An exact penalty on bilevel programs with linear vector optimization lower level

We are interested in a class of linear bilevel programs where the upper level is a linear scalar optimization problem and the lower level is a linear multi-objective optimization problem. We approach this problem via an exact penalty method. Then, we propose an algorithm illustrated by numerical examples.     

A note on article “A tolerance approach to the fuzzy goal programming problems with unbalanced triangular membership function”

Kim and Whang use a tolerance approach for solving fuzzy goal programming problems with unbalanced membership functions [J.S. Kim, K. Whang, A tolerance approach to the fuzzy goal programming problems with unbalanced triangular membership function, European Journal of Operational Research 107 (1998) 614–624]. In this note it is shown that some results in that article are incorrect. The necessary corrections are proposed.     

On semi-infinite minmax programming with generalized invexity

Here, we consider the minmax programming problem with a set of restrictions indexed in a compact. As a novelty, we obtain optimality criteria of the Kuhn--Tucker type involving a limited number of restrictions and prove both necessity and sufficiency under new weaker invexity assumptions. Also some dual problems are introduced and it is proved that the weak and strong duality properties hold within the same environment.     

The bilevel knapsack problem with stochastic right-hand sides

We introduce the bilevel knapsack problem with stochastic right-hand sides, and provide necessary and sufficient conditions for the existence of an optimal solution. When the leader’s decisions can take only integer values, we present an equivalent two-stage stochastic programming reformulation with binary recourse. We develop a branch-and-cut algorithm for solving this reformulation, and a branch-and-backtrack algorithm for solving the scenario subproblems. Computational experiments indicate that our approach can solve large instances in a reasonable amount of time.     

Survivable network design with demand uncertainty

The objective in designing a communications network is to find the most cost efficient network design that specifies hardware devices to be installed, the type of transmission links to be installed, and the routing strategy to be followed. In this paper algorithmic ideas are presented for improving tractability in solving the survivable network design problem by taking into account uncertainty in the traffic requirements. Strategies for improving separation of metric inequalities are presented and an iterative approach for obtaining solutions, that significantly reduces computing times, is introduced. Computational results are provided based on data collected from an operational network.     

A Semidefinite Programming Heuristic for Quadratic Programming Problems with Complementarity Constraints

The presence of complementarity constraints brings a combinatorial flavour to an optimization problem. A quadratic programming problem with complementarity constraints can be relaxed to give a semidefinite programming problem. The solution to this relaxation can be used to generate feasible solutions to the complementarity constraints. A quadratic programming problem is solved for each of these feasible solutions and the best resulting solution provides an estimate for the optimal solution to the quadratic program with complementarity constraints. Computational testing of such an approach is described for a problem arising in portfolio optimization.Research supported in part by the National Science Foundations VIGRE Program (Grant DMS-9983646).Research partially supported by NSF Grant number CCR-9901822.     

Higher-Order Duality in Nondifferentiable Minimax Programming with Generalized Type I Functions

A unified higher-order dual for a nondifferentiable minimax programming problem is formulated. Weak, strong and strict converse duality theorems are discussed involving generalized higher-order (F,α,ρ,d)-Type I functions. The research of second author was supported by the Department of Atomic Energy, Government of India, under the NBHM Post Doctoral Fellowship Program 40/9/2005-R&D II/2398.     

带有随机因素的逆DEA模型

本文讨论含有随机因素的逆 DEA模型 .逆 DEA模型解决的问题是 :对于某个决策单元 (DMU ) ,若增加其输入 ,在保持相对效率水平不变的情况下 ,估计 (预测 )输出应增加多少 .因此逆 DEA模型可用于短期预测问题 .带有随机因素的逆 DEA模型 ,是将该问题转化成机会约束的多目标规划问题 ,在某些特殊情况下 ,成为机会约束的线性规划问题 .     

Two theorems on multilevel programming problems with dominated objective functions

In this paper, we present two theorems on the structure of a type of multilevel programming problems. The theorems explore relations among a multilevel programming problem, a dynamical programming, and a nonlinear programming problem.     

Nested decomposition of multistage nonlinear programs with recourse

Nested decomposition is extended to the case of arborescent nonlinear programs. Duals of extensive forms of nonlinear multistage stochastic programs constitute a particular class of those problems; the method is tested on a set of problems of that type.     

Solving Difficult Multicommodity Problems with a Specialized Interior-Point Algorithm

A scheduling problem with piecewise linear (PL) optimization extends conventional scheduling by imposing a conjunction of combinatorial PL constraints involving the objective function variables. To solve this problem, this paper presents a hybrid algorithm where Constraint Programming (CP) search is supported and driven by a (integer) linear programming solver running on a well-controlled subproblem which is dynamically tightened. The paper discusses and compares different ways of decomposing the problem constraints between the CP search and the solver. We show how the subproblem structure and the piecewise linearity are exploited by the search.     

Stochastic lot-sizing problem with deterministic demands and Wagner-Whitin costs

In this paper, we consider a two-stage stochastic uncapacitated lot-sizing problem with deterministic demands and Wagner-Whitin costs. We develop an extended formulation in the higher dimensional space that provides integral solutions by showing that its constraint matrix is totally unimodular. We also provide the integral polyhedron of the problem in the original space by projecting the extended formulation to the original space.