L-shaped decomposition of two-stage stochastic programs with integer recourse

We consider two-stage stochastic programming problems with integer recourse. The L-shaped method of stochastic linear programming is generalized to these problems by using generalized Benders decomposition. Nonlinear feasibility and optimality cuts are determined via general duality theory and can be generated when the second stage problem is solved by standard techniques. Finite convergence of the method is established when Gomory’s fractional cutting plane algorithm or a branch-and-bound algorithm is applied.     

Mixed-integer quadratic programming

This paper considers mixed-integer quadratic programs in which the objective function is quadratic in the integer and in the continuous variables, and the constraints are linear in the variables of both types. The generalized Benders' decomposition is a suitable approach for solving such programs. However, the program does not become more tractable if this method is used, since Benders' cuts are quadratic in the integer variables. A new equivalent formulation that renders the program tractable is developed, under which the dual objective function is linear in the integer variables and the dual constraint set is independent of these variables. Benders' cuts that are derived from the new formulation are linear in the integer variables, and the original problem is decomposed into a series of integer linear master problems and standard quadratic subproblems. The new formulation does not introduce new primary variables or new constraints into the computational steps of the decomposition algorithm.The author wishes to thank two anonymous referees for their helpful comments and suggestions for revising the paper.     

Cross decomposition for mixed integer programming

Many methods for solving mixed integer programming problems are based either on primal or on dual decomposition, which yield, respectively, a Benders decomposition algorithm and an implicit enumeration algorithm with bounds computed via Lagrangean relaxation. These methods exploit either the primal or the dual structure of the problem. We propose a new approach, cross decomposition, which allows exploiting simultaneously both structures. The development of the cross decomposition method captures profound relationships between primal and dual decomposition. It is shown that the more constraints can be included in the Langrangean relaxation (provided the duality gap remains zero), the fewer the Benders cuts one may expect to need. If the linear programming relaxation has no duality gap, only one Benders cut is needed to verify optimality.     

Disjunctive cuts for continuous linear bilevel programming

This work shows how disjunctive cuts can be generated for a bilevel linear programming problem (BLP) with continuous variables. First, a brief summary on disjunctive programming and bilevel programming is presented. Then duality theory is used to reformulate BLP as a disjunctive program and, from there, disjunctive programming results are applied to derive valid cuts. These cuts tighten the domain of the linear relaxation of BLP. An example is given to illustrate this idea, and a discussion follows on how these cuts may be incorporated in an algorithm for solving BLP.     

A projection method for the uncapacitated facility location problem

Several algorithms already exist for solving the uncapacitated facility location problem. The most efficient are based upon the solution of the strong linear programming relaxation. The dual of this relaxation has a condensed form which consists of minimizing a certain piecewise linear convex function. This paper presents a new method for solving the uncapacitated facility location problem based upon the exact solution of the condensed dual via orthogonal projections. The amount of work per iteration is of the same order as that of a simplex iteration for a linear program inm variables and constraints, wherem is the number of clients. For comparison, the underlying linear programming dual hasmn + m + n variables andmn +n constraints, wheren is the number of potential locations for the facilities. The method is flexible as it can handle side constraints. In particular, when there is a duality gap, the linear programming formulation can be strengthened by adding cuts. Numerical results for some classical test problems are included.     

Multicut Benders decomposition algorithm for process supply chain planning under uncertainty

In this paper, we present a multicut version of the Benders decomposition method for solving two-stage stochastic linear programming problems, including stochastic mixed-integer programs with only continuous recourse (two-stage) variables. The main idea is to add one cut per realization of uncertainty to the master problem in each iteration, that is, as many Benders cuts as the number of scenarios added to the master problem in each iteration. Two examples are presented to illustrate the application of the proposed algorithm. One involves production-transportation planning under demand uncertainty, and the other one involves multiperiod planning of global, multiproduct chemical supply chains under demand and freight rate uncertainty. Computational studies show that while both the standard and the multicut versions of the Benders decomposition method can solve large-scale stochastic programming problems with reasonable computational effort, significant savings in CPU time can be achieved by using the proposed multicut algorithm.     

Continuous Modular Design Problem: Analysis and Solution Algorithms

This article studies the continuous modular design (MD) problem. First, the article presents duality results for problem (MD) based upon the Wolfe duality theory for nonlinear programming. From these results, an optimality test for problem (MD) is derived that consists of solving a single, balanced transportation problem. Second, the article shows that two well-known optimization approaches, the generalized Benders decomposition and the separable programming approach of linear programming, each have the potential to solve efficiently large instances of problem (MD).This research was supported by a Summer Research Grant from the Warrington College of Business Administration, University of Florida, Gainesville, Florida. The author is indebted to Panos Pardalos for introducing the topic to him.     

On duality theory of convex semi-infinite programming

In this article we discuss weak and strong duality properties of convex semi-infinite programming problems. We use a unified framework by writing the corresponding constraints in a form of cone inclusions. The consequent analysis is based on the conjugate duality approach of embedding the problem into a parametric family of problems parameterized by a finite-dimensional vector.     

A decomposition approach for global optimum search in QP,NLP and MINLP problems

Nonconvex programming problems are frequently encountered in engineering and operations research. A large variety of global optimization algorithms have been proposed for the various classes of programming problems. A new approach for global optimum search is presented in this paper which involves a decomposition of the variable set into two sets —complicating and noncomplicating variables. This results in a decomposition of the constraint set leading to two subproblems. The decomposition of the original problem induces special structure in the resulting subproblems and a series of these subproblems are then solved, using the Generalized Benders' Decomposition technique, to determine the optimal solution. The key idea is to combine a judicious selection of the complicating variables with suitable transformations leading to subproblems which can attain their respective global solutions at each iteration. Mathematical properties of the proposed approach are presented. Even though the proposed approach cannot guarantee the determination of the global optimum, computational experience on a number of nonconvex QP, NLP and MINLP example problems indicates that a global optimum solution can be obtained from various starting points.     

A cutting plane method from analytic centers for stochastic programming

The stochastic linear programming problem with recourse has a dual block-angular structure. It can thus be handled by Benders' decomposition or by Kelley's method of cutting planes; equivalently the dual problem has a primal block-angular structure and can be handled by Dantzig-Wolfe decomposition—the two approaches are in fact identical by duality. Here we shall investigate the use of the method of cutting planes from analytic centers applied to similar formulations. The only significant difference form the aforementioned methods is that new cutting planes (or columns, by duality) will be generated not from the optimum of the linear programming relaxation, but from the analytic center of the set of localization.This research has been supported by the Fonds National de la Recherche Scientifique Suisse (grant # 12-26434.89), NSERC-Canada and FCAR-Quebec.Corresponding author.     

Robust conjugate duality for convex optimization under uncertainty with application to data classification

In this paper we present a robust conjugate duality theory for convex programming problems in the face of data uncertainty within the framework of robust optimization, extending the powerful conjugate duality technique. We first establish robust strong duality between an uncertain primal parameterized convex programming model problem and its uncertain conjugate dual by proving strong duality between the deterministic robust counterpart of the primal model and the optimistic counterpart of its dual problem under a regularity condition. This regularity condition is not only sufficient for robust duality but also necessary for it whenever robust duality holds for every linear perturbation of the objective function of the primal model problem. More importantly, we show that robust strong duality always holds for partially finite convex programming problems under scenario data uncertainty and that the optimistic counterpart of the dual is a tractable finite dimensional problem. As an application, we also derive a robust conjugate duality theorem for support vector machines which are a class of important convex optimization models for classifying two labelled data sets. The support vector machine has emerged as a powerful modelling tool for machine learning problems of data classification that arise in many areas of application in information and computer sciences.     

Analysis of Decomposition Algorithms with Benders Cuts for p-Median Problem

In this paper the algorithms for solving the p-median problem based on the Benders decomposition are investigated. A family of problems hard for solving with such algorithms is constructed and then generalized to a special NP-hard case of the p-median problem. It is shown that the effectiveness of the considered algorithms depends on the choice of the optimal values of the dual variables used in Benders cuts. In particular, the depth of the cuts can be equal to one.     

An improved Benders decomposition algorithm for the logistics facility location problem with capacity expansions

We investigate a logistics facility location problem to determine whether the existing facilities remain open or not, what the expansion size of the open facilities should be and which potential facilities should be selected. The problem is formulated as a mixed integer linear programming model (MILP) with the objective to minimize the sum of the savings from closing the existing facilities, the expansion costs, the fixed setup costs, the facility operating costs and the transportation costs. The structure of the model motivates us to solve the problem using Benders decomposition algorithm. Three groups of valid inequalities are derived to improve the lower bounds obtained by the Benders master problem. By separating the primal Benders subproblem, different types of disaggregated cuts of the primal Benders cut are constructed in each iteration. A high density Pareto cut generation method is proposed to accelerate the convergence by lifting Pareto-optimal cuts. Computational experiments show that the combination of all the valid inequalities can improve the lower bounds significantly. By alternately applying the high density Pareto cut generation method based on the best disaggregated cuts, the improved Benders decomposition algorithm is advantageous in decreasing the total number of iterations and CPU time when compared to the standard Benders algorithm and optimization solver CPLEX, especially for large-scale instances.     

Speed-up Benders decomposition using maximum density cut (MDC) generation

The classical implementation of Benders decomposition in some cases results in low density Benders cuts. Covering Cut Bundle (CCB) generation addresses this issue with a novel way generating a bundle of cuts which could cover more decision variables of the Benders master problem than the classical Benders cut. Our motivation to improve further CCB generation led to a new cut generation strategy. This strategy is referred to as the Maximum Density Cut (MDC) generation strategy. MDC is based on the observation that in some cases CCB generation is computational expensive to cover all decision variables of the master problem than to cover part of them. Thus MDC strategy addresses this issue by generating the cut that involves the rest of the decision variables of the master problem which are not covered in the Benders cut and/or in the CCB. MDC strategy can be applied as a complimentary step to the CCB generation as well as a standalone strategy. In this work the approach is applied to two case studies: the scheduling of crude oil and the scheduling of multi-product, multi-purpose batch plants. In both cases, MDC strategy significant decreases the number of iterations of the Benders decomposition algorithm, leading to improved CPU solution times.     

A so-called Cluster Benders Decomposition approach for solving two-stage stochastic linear problems

The optimization of stochastic linear problems, via scenario analysis, based on Benders decomposition requires appending feasibility and/or optimality cuts to the master problem until the iterative procedure reaches the optimal solution. The cuts are identified by solving the auxiliary submodels attached to the scenarios. In this work, we propose the algorithm named scenario Cluster Benders Decomposition (CBD) for dealing with the feasibility cut identification in the Benders method for solving large-scale two-stage stochastic linear problems. The scenario tree is decomposed into a set of scenario clusters and tighter feasibility cuts are obtained by solving the auxiliary submodel for each cluster instead of each individual scenario. Then, the scenario cluster based scheme allows to identify tighter feasibility cuts that yield feasible second stage decisions in reasonable computing time. Some computational experience is reported by using CPLEX as the solver of choice for the auxiliary LP submodels at each iteration of the algorithm CBD. The results that are reported show the favorable performance of the new approach over the traditional single scenario based Benders decomposition; it also outperforms the plain use of CPLEX for medium-large and large size instances.     

A binary decision diagram based algorithm for solving a class of binary two-stage stochastic programs

We consider a special class of two-stage stochastic integer programming problems with binary variables appearing in both stages. The class of problems we consider constrains the second-stage variables to belong to the intersection of sets corresponding to first-stage binary variables that equal one. Our approach seeks to uncover strong dual formulations to the second-stage problems by transforming them into dynamic programming (DP) problems parameterized by first-stage variables. We demonstrate how these DPs can be formed by use of binary decision diagrams, which then yield traditional Benders inequalities that can be strengthened based on observations regarding the structure of the underlying DPs. We demonstrate the efficacy of our approach on a set of stochastic traveling salesman problems.

     

On <Emphasis Type="Italic">G</Emphasis>-invex multiobjective programming. Part II. Duality

This paper represents the second part of a study concerning the so-called G-multiobjective programming. A new approach to duality in differentiable vector optimization problems is presented. The techniques used are based on the results established in the paper: On G-invex multiobjective programming. Part I. Optimality by T.Antczak. In this work, we use a generalization of convexity, namely G-invexity, to prove new duality results for nonlinear differentiable multiobjective programming problems. For such vector optimization problems, a number of new vector duality problems is introduced. The so-called G-Mond–Weir, G-Wolfe and G-mixed dual vector problems to the primal one are defined. Furthermore, various so-called G-duality theorems are proved between the considered differentiable multiobjective programming problem and its nonconvex vector G-dual problems. Some previous duality results for differentiable multiobjective programming problems turn out to be special cases of the results described in the paper.     

The theory of linear programming:skew symmetric self-dual problems and the central path *

The literature in the field of interior point methods for linear programming has been almost exclusively algorithm oriented. Recently Güler, Roos, Terlaky and Vial presented a complete duality theory for linear programming based on the interior point approach. In this paper we present a more simple approach which is based on an embedding of the primal problem and its dual into a skew symmetric self-dual problem. This embedding is essentially due Ye, Todd and Mizuno

First we consider a skew symmetric self-dual linear program. We show that the strong duality theorem trivally holds in this case. Then, using the logarithmic barrier problem and the central path, the existence of a strictly complementary optimal solution is proved. Using the embedding just described, we easily obtain the strong duality theorem and the existence of strictly complementary optimal solutions for general linear programming problems     

On linear programs with linear complementarity constraints

The paper is a manifestation of the fundamental importance of the linear program with linear complementarity constraints (LPCC) in disjunctive and hierarchical programming as well as in some novel paradigms of mathematical programming. In addition to providing a unified framework for bilevel and inverse linear optimization, nonconvex piecewise linear programming, indefinite quadratic programs, quantile minimization, and ℓ ₀ minimization, the LPCC provides a gateway to a mathematical program with equilibrium constraints, which itself is an important class of constrained optimization problems that has broad applications. We describe several approaches for the global resolution of the LPCC, including a logical Benders approach that can be applied to problems that may be infeasible or unbounded.