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.     

First-order inertial algorithms involving dry friction damping

We present a Branch-and-Cut algorithm for a class of nonlinear chance-constrained mathematical optimization problems with a finite number of scenarios. Unsatisfied scenarios can enter a recovery mode. This class corresponds to problems that can be reformulated as deterministic convex mixed-integer nonlinear programming problems with indicator variables and continuous scenario variables, but the size of the reformulation is large and quickly becomes impractical as the number of scenarios grows. The Branch-and-Cut algorithm is based on an implicit Benders decomposition scheme, where we generate cutting planes as outer approximation cuts from the projection of the feasible region on suitable subspaces. The size of the master problem in our scheme is much smaller than the deterministic reformulation of the chance-constrained problem. We apply the Branch-and-Cut algorithm to the mid-term hydro scheduling problem, for which we propose a chance-constrained formulation. A computational study using data from ten hydroplants in Greece shows that the proposed methodology solves instances faster than applying a general-purpose solver for convex mixed-integer nonlinear programming problems to the deterministic reformulation, and scales much better with the number of scenarios.

     

A trust region SQP algorithm for mixed-integer nonlinear programming

We propose a modified sequential quadratic programming method for solving mixed-integer nonlinear programming problems. Under the assumption that integer variables have a smooth influence on the model functions, i.e., that function values do not change drastically when in- or decrementing an integer value, successive quadratic approximations are applied. The algorithm is stabilized by a trust region method with Yuan’s second order corrections. It is not assumed that the mixed-integer program is relaxable or, in other words, function values are evaluated only at integer points. The Hessian of the Lagrangian function is approximated by a quasi-Newton update formula subject to the continuous and integer variables. Numerical results are presented for a set of 80 mixed-integer test problems taken from the literature. The surprising result is that the number of function evaluations, the most important performance criterion in practice, is less than the number of function calls needed for solving the corresponding relaxed problem without integer variables.     

Outer approximation algorithms for separable nonconvex mixed-integer nonlinear programs

A rigorous decomposition approach to solve separable mixed-integer nonlinear programs where the participating functions are nonconvex is presented. The proposed algorithms consist of solving an alternating sequence of Relaxed Master Problems (mixed-integer linear program) and two nonlinear programming problems (NLPs). A sequence of valid nondecreasing lower bounds and upper bounds is generated by the algorithms which converge in a finite number of iterations. A Primal Bounding Problem is introduced, which is a convex NLP solved at each iteration to derive valid outer approximations of the nonconvex functions in the continuous space. Two decomposition algorithms are presented in this work. On finite termination, the first yields the global solution to the original nonconvex MINLP and the second finds a rigorous bound to the global solution. Convergence and optimality properties, and refinement of the algorithms for efficient implementation are presented. Finally, numerical results are compared with currently available algorithms for example problems, illuminating the potential benefits of the proposed algorithm.     

An outer-approximation approach for information-maximizing sensor selection

This paper addresses information-maximizing sensor selection that determines a set of measurement locations providing the largest entropy reduction in the estimates of the state variables. A new mixed-integer semidefinite program (MISDP) formulation is proposed for this selection under the constraints resulting from communication limitations. This formulation employs binary variables indicating if the corresponding measurement location is selected, and ensures convexity of the objective function and linearity of the constraint functions by exploiting the linear equivalent form of a bilinear term involving binary variables. An outer-approximation algorithm is then developed for the MISDP formulation that obtains the global optimal solution by solving a sequence of mixed-integer linear programs for which reliable solvers are available. Numerical experiments verify the solution optimality and the computational effectiveness of the proposed algorithm by comparing it to branch-and-bound-based approaches with nonlinear programming relaxation. An example of sensor selection to track a moving target is considered to demonstrate the applicability of the proposed method and highlight its ability to handle quadratic constraints.     

Optimizing the supply chain configuration for make-to-order manufacturing

We consider a make-to-order (MTO) manufacturer who has won multiple contracts with specified quantities to be delivered by certain due dates. Before production starts, the company must configure its supply chain and make sourcing decisions. It also needs to plan the starting time for each production task under limited availability of resources such as machines and workforce. We develop a model for simultaneously optimizing such sourcing and planning decisions while exploiting their tradeoffs. The resulting multi-mode resource-constrained project scheduling problem (MMRCPSP) with a nonlinear objective function is NP-complete. To efficiently solve it, a hybrid Benders decomposition (HBD) algorithm combining the strengths of both mathematical programming and constraint programming is developed. The HBD exploits the structure of the model formulation and decomposes it into a relaxed master problem handled by mixed-integer nonlinear programming (MINLP), and a scheduling feasibility sub-problem handled by constraint programming (CP). Cuts are iteratively generated by solving the feasibility sub-problem and added back to the relaxed master problem, until an optimal solution is found or infeasibility is proved. Computational experiments are conducted to examine performance of the model and algorithm. Insights about optimal configuration of MTO supply chains are drawn and discussed.     

Dual decomposition in stochastic integer programming

We present an algorithm for solving stochastic integer programming problems with recourse, based on a dual decomposition scheme and Lagrangian relaxation. The approach can be applied to multi-stage problems with mixed-integer variables in each time stage. Numerical experience is presented for some two-stage test problems.     

Improving benders decomposition using a genetic algorithm

We develop and investigate the performance of a hybrid solution framework for solving mixed-integer linear programming problems. Benders decomposition and a genetic algorithm are combined to develop a framework to compute feasible solutions. We decompose the problem into a master problem and a subproblem. A genetic algorithm along with a heuristic are used to obtain feasible solutions to the master problem, whereas the subproblem is solved to optimality using a linear programming solver. Over successive iterations the master problem is refined by adding cutting planes that are implied by the subproblem. We compare the performance of the approach against a standard Benders decomposition approach as well as against a stand-alone solver (Cplex) on MIPLIB test problems.     

Convergence and Application of a Decomposition Method Using Duality Bounds for Nonconvex Global Optimization

The subject of this article is a class of global optimization problems, in which the variables can be divided into two groups such that, in each group, the functions involved have the same structure (e.g. linear, convex or concave, etc.). Based on the decomposition idea of Benders (Ref. 1), a corresponding master problem is defined on the space of one of the two groups of variables. The objective function of this master problem is in fact the optimal value function of a nonlinear parametric optimization problem. To solve the resulting master problem, a branch-and-bound scheme is proposed, in which the estimation of the lower bounds is performed by applying the well-known weak duality theorem in Lagrange duality. The results of this article concentrate on two subjects: investigating the convergence of the general algorithm and solving dual problems of some special classes of nonconvex optimization problems. Based on results in sensitivity and stability theory and in parametric optimization, conditions for the convergence are established by investigating the so-called dual properness property and the upper semicontinuity of the objective function of the master problem. The general algorithm is then discussed in detail for some nonconvex problems including concave minimization problems with a special structure, general quadratic problems, optimization problems on the efficient set, and linear multiplicative programming problems.     

Improved logarithmic linearizing method for optimization problems with free-sign pure discrete signomial terms

Free-sign pure discrete signomial (FPDS) terms are vital to and are frequently observed in many nonlinear programming problems, such as geometric programming, generalized geometric programming, and mixed-integer non-linear programming problems. In this study, all variables in the FPDS term are discrete variables. Any improvement to techniques for linearizing FPDS term contributes significantly to the solving of nonlinear programming problems; therefore, relative techniques have continually been developed. This study develops an improved exact method to linearize a FPDS term into a set of linear programs with minimal logarithmic numbers of zero-one variables and constraints. This method is tighter than current methods. Various numerical experiments demonstrate that the proposed method is significantly more efficient than current methods, especially when the problem scale is large.     

Decomposition strategy for the stochastic pooling problem

The stochastic pooling problem is a type of stochastic mixed-integer bilinear program arising in the integrated design and operation of various important industrial networks, such as gasoline blending, natural gas production and transportation, water treatment, etc. This paper presents a rigorous decomposition method for the stochastic pooling problem, which guarantees finding an ${\epsilon}$ -optimal solution with a finite number of iterations. By convexification of the bilinear terms, the stochastic pooling problem is relaxed into a lower bounding problem that is a potentially large-scale mixed-integer linear program (MILP). Solution of this lower bounding problem is then decomposed into a sequence of relaxed master problems, which are MILPs with much smaller sizes, and primal bounding problems, which are linear programs. The solutions of the relaxed master problems yield a sequence of nondecreasing lower bounds on the optimal objective value, and they also generate a sequence of integer realizations defining the primal problems which yield a sequence of nonincreasing upper bounds on the optimal objective value. The decomposition algorithm terminates finitely when the lower and upper bounds coincide (or are close enough), or infeasibility of the problem is indicated. Case studies involving two example problems and two industrial problems demonstrate the dramatic computational advantage of the proposed decomposition method over both a state-of-the-art branch-and-reduce global optimization method and explicit enumeration of integer realizations, particularly for large-scale problems.     

Global optimization of mixed-integer bilevel programming problems

Two approaches that solve the mixed-integer nonlinear bilevel programming problem to global optimality are introduced. The first addresses problems mixed-integer nonlinear in outer variables and C²-nonlinear in inner variables. The second adresses problems with general mixed-integer nonlinear functions in outer level. Inner level functions may be mixed-integer nonlinear in outer variables, linear, polynomial, or multilinear in inner integer variables, and linear in inner continuous variables. This second approach is based on reformulating the mixed-integer inner problem as continuous via its vertex polyheral convex hull representation and solving the resulting nonlinear bilevel optimization problem by a novel deterministic global optimization framework. Computational studies illustrate proposed approaches.     

Column enumeration based decomposition techniques for a class of non-convex MINLP problems

We propose a decomposition algorithm for a special class of nonconvex mixed integer nonlinear programming problems which have an assignment constraint. If the assignment decisions are decoupled from the remaining constraints of the optimization problem, we propose to use a column enumeration approach. The master problem is a partitioning problem whose objective function coefficients are computed via subproblems. These problems can be linear, mixed integer linear, (non-)convex nonlinear, or mixed integer nonlinear. However, the important property of the subproblems is that we can compute their exact global optimum quickly. The proposed technique will be illustrated solving a cutting problem with optimum nonlinear programming subproblems.     

An efficient strategy for the activation of MIP relaxations in a multicore global MINLP solver

Solving mixed-integer nonlinear programming (MINLP) problems to optimality is a NP-hard problem, for which many deterministic global optimization algorithms and solvers have been recently developed. MINLPs can be relaxed in various ways, including via mixed-integer linear programming (MIP), nonlinear programming, and linear programming. There is a tradeoff between the quality of the bounds and CPU time requirements of these relaxations. Unfortunately, these tradeoffs are problem-dependent and cannot be predicted beforehand. This paper proposes a new dynamic strategy for activating and deactivating MIP relaxations in various stages of a branch-and-bound algorithm. The primary contribution of the proposed strategy is that it does not use meta-parameters, thus avoiding parameter tuning. Additionally, this paper proposes a strategy that capitalizes on the availability of parallel MIP solver technology to exploit multicore computing hardware while solving MINLPs. Computational tests for various benchmark libraries reveal that our MIP activation strategy works efficiently in single-core and multicore environments.     

Computational strategies for non-convex multistage MINLP models with decision-dependent uncertainty and gradual uncertainty resolution

In many planning problems under uncertainty the uncertainties are decision-dependent and resolve gradually depending on the decisions made. In this paper, we address a generic non-convex MINLP model for such planning problems where the uncertain parameters are assumed to follow discrete distributions and the decisions are made on a discrete time horizon. In order to account for the decision-dependent uncertainties and gradual uncertainty resolution, we propose a multistage stochastic programming model in which the non-anticipativity constraints in the model are not prespecified but change as a function of the decisions made. Furthermore, planning problems consist of several scenario subproblems where each subproblem is modeled as a nonconvex mixed-integer nonlinear program. We propose a solution strategy that combines global optimization and outer-approximation in order to optimize the planning decisions. We apply this generic problem structure and the proposed solution algorithm to several planning problems to illustrate the efficiency of the proposed method with respect to the method that uses only global optimization.     

Conic mixed-integer rounding cuts

A conic integer program is an integer programming problem with conic constraints. Many problems in finance, engineering, statistical learning, and probabilistic optimization are modeled using conic constraints. Here we study mixed-integer sets defined by second-order conic constraints. We introduce general-purpose cuts for conic mixed-integer programming based on polyhedral conic substructures of second-order conic sets. These cuts can be readily incorporated in branch-and-bound algorithms that solve either second-order conic programming or linear programming relaxations of conic integer programs at the nodes of the branch-and-bound tree. Central to our approach is a reformulation of the second-order conic constraints with polyhedral second-order conic constraints in a higher dimensional space. In this representation the cuts we develop are linear, even though they are nonlinear in the original space of variables. This feature leads to a computationally efficient implementation of nonlinear cuts for conic mixed-integer programming. The reformulation also allows the use of polyhedral methods for conic integer programming. We report computational results on solving unstructured second-order conic mixed-integer problems as well as mean–variance capital budgeting problems and least-squares estimation problems with binary inputs. Our computational experiments show that conic mixed-integer rounding cuts are very effective in reducing the integrality gap of continuous relaxations of conic mixed-integer programs and, hence, improving their solvability. This research has been supported, in part, by Grant # DMI0700203 from the National Science Foundation.     

A convexification method for a class of global optimization problems with applications to reliability optimization

A convexification method is proposed for solving a class of global optimization problems with certain monotone properties. It is shown that this class of problems can be transformed into equivalent concave minimization problems using the proposed convexification schemes. An outer approximation method can then be used to find the global solution of the transformed problem. Applications to mixed-integer nonlinear programming problems arising in reliability optimization of complex systems are discussed and satisfactory numerical results are presented.     

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.     

A scenario decomposition algorithm for 0–1 stochastic programs

We propose a scenario decomposition algorithm for stochastic 0–1 programs. The algorithm recovers an optimal solution by iteratively exploring and cutting-off candidate solutions obtained from solving scenario subproblems. The scheme is applicable to quite general problem structures and can be implemented in a distributed framework. Illustrative computational results on standard two-stage stochastic integer programming and nonlinear stochastic integer programming test problems are presented.     

The extended supporting hyperplane algorithm for convex mixed-integer nonlinear programming

A new deterministic algorithm for solving convex mixed-integer nonlinear programming (MINLP) problems is presented in this paper: The extended supporting hyperplane (ESH) algorithm uses supporting hyperplanes to generate a tight overestimated polyhedral set of the feasible set defined by linear and nonlinear constraints. A sequence of linear or quadratic integer-relaxed subproblems are first solved to rapidly generate a tight linear relaxation of the original MINLP problem. After an initial overestimated set has been obtained the algorithm solves a sequence of mixed-integer linear programming or mixed-integer quadratic programming subproblems and refines the overestimated set by generating more supporting hyperplanes in each iteration. Compared to the extended cutting plane algorithm ESH generates a tighter overestimated set and unlike outer approximation the generation point for the supporting hyperplanes is found by a simple line search procedure. In this paper it is proven that the ESH algorithm converges to a global optimum for convex MINLP problems. The ESH algorithm is implemented as the supporting hyperplane optimization toolkit (SHOT) solver, and an extensive numerical comparison of its performance against other state-of-the-art MINLP solvers is presented.