A hierarchy of relaxations for linear generalized disjunctive programming

Generalized disjunctive programming (GDP), originally developed by Raman and Grossmann (1994), is an extension of the well-known disjunctive programming paradigm developed by Balas in the mid 70s in his seminal technical report (Balas, 1974). This mathematical representation of discrete-continuous optimization problems, which represents an alternative to the mixed-integer program (MIP), led to the development of customized algorithms that successfully exploited the underlying logical structure of the problem. The underlying theory of these methods, however, borrowed only in a limited way from the theories of disjunctive programming, and the unique insights from Balas’ work have not been fully exploited.In this paper, we establish new connections between the fields of disjunctive programming and generalized disjunctive programming for the linear case. We then propose a novel hierarchy of relaxations to the original linear GDP model that subsumes known relaxations for this model, and show that a subset of these relaxations are tighter than the latter. We discuss the usefulness of these relaxations within the context of MIP and illustrate these results on the classic strip-packing problem.     

Lift-and-project cuts for convex mixed integer nonlinear programs

We describe a computationally effective method for generating lift-and-project cuts for convex mixed-integer nonlinear programs (MINLPs). The method relies on solving a sequence of cut-generating linear programs and in the limit generates an inequality as strong as the lift-and-project cut that can be obtained from solving a cut-generating nonlinear program. Using this procedure, we are able to approximately optimize over the rank one lift-and-project closure for a variety of convex MINLP instances. The results indicate that lift-and-project cuts have the potential to close a significant portion of the integrality gap for convex MINLPs. In addition, we find that using this procedure within a branch-and-cut solver for convex MINLPs significantly reduces the total solution time for many instances. We also demonstrate that combining lift-and-project cuts with an extended formulation that exploits separability of convex functions yields significant improvements in both relaxation bounds and the time to calculate the relaxation. Overall, these results suggest that with an effective separation routine, like the one proposed here, lift-and-project cuts may be as effective for solving convex MINLPs as they have been for solving mixed-integer linear programs.     

Global optimization of mixed-integer nonlinear programs: A theoretical and computational study

This work addresses the development of an efficient solution strategy for obtaining global optima of continuous, integer, and mixed-integer nonlinear programs. Towards this end, we develop novel relaxation schemes, range reduction tests, and branching strategies which we incorporate into the prototypical branch-and-bound algorithm. In the theoretical/algorithmic part of the paper, we begin by developing novel strategies for constructing linear relaxations of mixed-integer nonlinear programs and prove that these relaxations enjoy quadratic convergence properties. We then use Lagrangian/linear programming duality to develop a unifying theory of domain reduction strategies as a consequence of which we derive many range reduction strategies currently used in nonlinear programming and integer linear programming. This theory leads to new range reduction schemes, including a learning heuristic that improves initial branching decisions by relaying data across siblings in a branch-and-bound tree. Finally, we incorporate these relaxation and reduction strategies in a branch-and-bound algorithm that incorporates branching strategies that guarantee finiteness for certain classes of continuous global optimization problems. In the computational part of the paper, we describe our implementation discussing, wherever appropriate, the use of suitable data structures and associated algorithms. We present computational experience with benchmark separable concave quadratic programs, fractional 0–1 programs, and mixed-integer nonlinear programs from applications in synthesis of chemical processes, engineering design, just-in-time manufacturing, and molecular design.The research was supported in part by ExxonMobil Upstream Research Company, National Science Foundation awards DMII 95-02722, BES 98-73586, ECS 00-98770, and CTS 01-24751, and the Computational Science and Engineering Program of the University of Illinois.     

A hierarchy of relaxations for nonlinear convex generalized disjunctive programming

We propose a framework to generate alternative mixed-integer nonlinear programming formulations for disjunctive convex programs that lead to stronger relaxations. We extend the concept of “basic steps” defined for disjunctive linear programs to the nonlinear case. A basic step is an operation that takes a disjunctive set to another with fewer number of conjuncts. We show that the strength of the relaxations increases as the number of conjuncts decreases, leading to a hierarchy of relaxations. We prove that the tightest of these relaxations, allows in theory the solution of the disjunctive convex program as a nonlinear programming problem. We present a methodology to guide the generation of strong relaxations without incurring an exponential increase of the size of the reformulated mixed-integer program. Finally, we apply the theory developed to improve the computational efficiency of solution methods for nonlinear convex generalized disjunctive programs (GDP). This methodology is validated through a set of numerical examples.     

Models and solution techniques for production planning problems with increasing byproducts

We consider a production planning problem where the production process creates a mixture of desirable products and undesirable byproducts. In this production process, at any point in time the fraction of the mixture that is an undesirable byproduct increases monotonically as a function of the cumulative mixture production up to that time. The mathematical formulation of this continuous-time problem is nonconvex. We present a discrete-time mixed-integer nonlinear programming (MINLP) formulation that exploits the increasing nature of the byproduct ratio function. We demonstrate that this new formulation is more accurate than a previously proposed MINLP formulation. We describe three different mixed-integer linear programming (MILP) approximation and relaxation models of this nonconvex MINLP, and we derive modifications that strengthen the linear programming relaxations of these models. We also introduce nonlinear programming formulations to choose piecewise-linear approximations and relaxations of multiple functions that share the same domain and use the same set of break points in the domain. We conclude with computational experiments that demonstrate that the proposed formulation is more accurate than the previous formulation, and that the strengthened MILP approximation and relaxation models can be used to obtain provably near-optimal solutions for large instances of this nonconvex MINLP. Experiments also illustrate the quality of the piecewise-linear approximations produced by our nonlinear programming formulations.     

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.     

Linearization-based algorithms for mixed-integer nonlinear programs with convex continuous relaxation

We present two linearization-based algorithms for mixed-integer nonlinear programs (MINLPs) having a convex continuous relaxation. The key feature of these algorithms is that, in contrast to most existing linearization-based algorithms for convex MINLPs, they do not require the continuous relaxation to be defined by convex nonlinear functions. For example, these algorithms can solve to global optimality MINLPs with constraints defined by quasiconvex functions. The first algorithm is a slightly modified version of the LP/NLP-based branch-and-bouund \((\text{ LP/NLP-BB })\) algorithm of Quesada and Grossmann, and is closely related to an algorithm recently proposed by Bonami et al. (Math Program 119:331–352, 2009). The second algorithm is a hybrid between this algorithm and nonlinear programming based branch-and-bound. Computational experiments indicate that the modified LP/NLP-BB method has comparable performance to LP/NLP-BB on instances defined by convex functions. Thus, this algorithm has the potential to solve a wider class of MINLP instances without sacrificing performance.     

Branch-and-price for a class of nonconvex mixed-integer nonlinear programs

This work attempts to combine the strengths of two major technologies that have matured over the last three decades: global mixed-integer nonlinear optimization and branch-and-price. We consider a class of generally nonconvex mixed-integer nonlinear programs (MINLPs) with linear complicating constraints and integer linking variables. If the complicating constraints are removed, the problem becomes easy to solve, e.g. due to decomposable structure. Integrality of the linking variables allows us to apply a discretization approach to derive a Dantzig-Wolfe reformulation and solve the problem to global optimality using branch-andprice. It is a remarkably simple idea; but to our surprise, it has barely found any application in the literature. In this work, we show that many relevant problems directly fall or can be reformulated into this class of MINLPs. We present the branch-and-price algorithm and demonstrate its effectiveness (and sometimes ineffectiveness) in an extensive computational study considering multiple large-scale problems of practical relevance, showing that, in many cases, orders-of-magnitude reductions in solution time can be achieved.

     

Optimal operating strategy for a long-haul liner service route

This paper proposes an optimal operating strategy problem arising in liner shipping industry that aims to determine service frequency, containership fleet deployment plan, and sailing speed for a long-haul liner service route. The problem is formulated as a mixed-integer nonlinear programming model that cannot be solved efficiently by the existing solution algorithms. In view of some unique characteristics of the liner shipping operations, this paper proposes an efficient and exact branch-and-bound based ε-optimal algorithm. In particular, a mixed-integer nonlinear model is first developed for a given service frequency and ship type; two linearization techniques are subsequently presented to approximate this model with a mixed-integer linear program; and the branch-and-bound approach controls the approximation error below a specified tolerance. This paper further demonstrates that the branch-and-bound based ε-optimal algorithm obtains a globally optimal solution with the predetermined relative optimality tolerance ε in a finite number of iterations. The case study based on an existing long-haul liner service route shows the effectiveness and efficiency of the proposed solution method.     

A special ordered set approach for optimizing a discontinuous separable piecewise linear function

We give a special ordered set (SOS) approach that optimizes a discontinuous separable piecewise linear function, even when a mixed-integer programming (MIP) model is not available for it. When a MIP model is available, our SOS model gives a linear programming relaxation bound that is as good as the MIPs.     

Undercover: a primal MINLP heuristic exploring a largest sub-MIP

We present Undercover, a primal heuristic for nonconvex mixed-integer nonlinear programs (MINLPs) that explores a mixed-integer linear subproblem (sub-MIP) of a given MINLP. We solve a vertex covering problem to identify a smallest set of variables to fix, a so-called cover, such that each constraint is linearized. Subsequently, these variables are fixed to values obtained from a reference point, e.g., an optimal solution of a linear relaxation. Each feasible solution of the sub-MIP corresponds to a feasible solution of the original problem. We apply domain propagation to try to avoid infeasibilities, and conflict analysis to learn additional constraints from infeasibilities that are nonetheless encountered. We present computational results on a test set of mixed-integer quadratically constrained programs (MIQCPs) and MINLPs. It turns out that the majority of these instances allows for small covers. Although general in nature, we show that the heuristic is most successful on MIQCPs. It nicely complements existing root-node heuristics in different state-of-the-art solvers and helps to significantly improve the overall performance of the MINLP solver SCIP.     

Convex quadratic relaxations for mixed-integer nonlinear programs in power systems

This paper presents a set of new convex quadratic relaxations for nonlinear and mixed-integer nonlinear programs arising in power systems. The considered models are motivated by hybrid discrete/continuous applications where existing approximations do not provide optimality guarantees. The new relaxations offer computational efficiency along with minimal optimality gaps, providing an interesting alternative to state-of-the-art semidefinite programming relaxations. Three case studies in optimal power flow, optimal transmission switching and capacitor placement demonstrate the benefits of the new relaxations.     

On generalized surrogate duality in mixed-integer nonlinear programming

Mathematical Programming - The most important ingredient for solving mixed-integer nonlinear programs (MINLPs) to global $$\epsilon $$ -optimality with spatial branch and bound is a tight,...     

Nonanticipative duality,relaxations, and formulations for chance-constrained stochastic programs

We propose two new Lagrangian dual problems for chance-constrained stochastic programs based on relaxing nonanticipativity constraints. We compare the strength of the proposed dual bounds and demonstrate that they are superior to the bound obtained from the continuous relaxation of a standard mixed-integer programming (MIP) formulation. For a given dual solution, the associated Lagrangian relaxation bounds can be calculated by solving a set of single scenario subproblems and then solving a single knapsack problem. We also derive two new primal MIP formulations and demonstrate that for chance-constrained linear programs, the continuous relaxations of these formulations yield bounds equal to the proposed dual bounds. We propose a new heuristic method and two new exact algorithms based on these duals and formulations. The first exact algorithm applies to chance-constrained binary programs, and uses either of the proposed dual bounds in concert with cuts that eliminate solutions found by the subproblems. The second exact method is a branch-and-cut algorithm for solving either of the primal formulations. Our computational results indicate that the proposed dual bounds and heuristic solutions can be obtained efficiently, and the gaps between the best dual bounds and the heuristic solutions are small.     

New convergent heuristics for 0–1 mixed integer programming

Several hybrid methods have recently been proposed for solving 0–1 mixed integer programming problems. Some of these methods are based on the complete exploration of small neighborhoods. In this paper, we present several convergent algorithms that solve a series of small sub-problems generated by exploiting information obtained from a series of relaxations. These algorithms generate a sequence of upper bounds and a sequence of lower bounds around the optimal value. First, the principle of a linear programming-based algorithm is summarized, and several enhancements of this algorithm are presented. Next, new hybrid heuristics that use linear programming and/or mixed integer programming relaxations are proposed. The mixed integer programming (MIP) relaxation diversifies the search process and introduces new constraints in the problem. This MIP relaxation also helps to reduce the gap between the final upper bound and lower bound. Our algorithms improved 14 best-known solutions from a set of 108 available and correlated instances of the 0–1 multidimensional Knapsack problem. Other encouraging results obtained for 0–1 MIP problems are also presented.     

Global optimization of general nonconvex problems with intermediate polynomial substructures

This work considers the global optimization of general nonconvex nonlinear and mixed-integer nonlinear programming problems with underlying polynomial substructures. We incorporate linear cutting planes inspired by reformulation-linearization techniques to produce tight subproblem formulations that exploit these underlying structures. These cutting plane strategies simultaneously convexify linear and nonlinear terms from multiple constraints and are highly effective at tightening standard linear programming relaxations generated by sequential factorable programming techniques. Because the number of available cutting planes increases exponentially with the number of variables, we implement cut filtering and selection strategies to prevent an exponential increase in relaxation size. We introduce algorithms for polynomial substructure detection, cutting plane identification, cut filtering, and cut selection and embed the proposed implementation in BARON at every node in the branch-and-bound tree. A computational study including randomly generated problems of varying size and complexity demonstrates that the exploitation of underlying polynomial substructures significantly reduces computational time, branch-and-bound tree size, and required memory.     

A heuristic to generate rank-1 GMI cuts

Gomory mixed-integer (GMI) cuts are among the most effective cutting planes for general mixed-integer programs (MIP). They are traditionally generated from an optimal basis of a linear programming (LP) relaxation of a MIP. In this paper we propose a heuristic to generate useful GMI cuts from additional bases of the initial LP relaxation. The cuts we generate have rank one, i.e., they do not use previously generated GMI cuts. We demonstrate that for problems in MIPLIB 3.0 and MIPLIB 2003, the cuts we generate form an important subclass of all rank-1 mixed-integer rounding cuts. Further, we use our heuristic to generate globally valid rank-1 GMI cuts at nodes of a branch-and-cut tree and use these cuts to solve a difficult problem from MIPLIB 2003, namely timtab2, without using problem-specific cuts.     

Evaluating mixed-integer programming models over multiple right-hand sides

A critical measure of model quality for a mixed-integer program (MIP) is the difference, or gap, between its optimal objective value and that of its linear programming relaxation. In some cases, the right-hand side is not known exactly; however, there is no consensus metric for evaluating a MIP model when considering multiple right-hand sides. In this paper, we provide model formulations for the expectation and extrema of absolute and relative MIP gap functions over finite discrete sets.     

Linear regularity, equirregularity, and intersection mappings for convex semi-infinite inequality systems

We study the mixed-integer rounding (MIR) closures of polyhedral sets. The MIR closure of a polyhedral set is equal to its split closure and the associated separation problem is NP-hard. We describe a mixed-integer programming (MIP) model with linear constraints and a non-linear objective for separating an arbitrary point from the MIR closure of a given mixed-integer set. We linearize the objective using additional variables to produce a linear MIP model that solves the separation problem exactly. Using a subset of these additional variables yields an MIP model which solves the separation problem approximately, with an accuracy that depends on the number of additional variables used. Our analysis yields an alternative proof of the result of Cook et al. (1990) that the split closure of a polyhedral set is again a polyhedron. We also discuss a heuristic to obtain MIR cuts based on our approximate separation model, and present some computational results. Andrea Lodi was supported in part by the EU projects ADONET (contract n. MRTN-CT-2003-504438) and ARRIVAL (contract n. FP6-021235-2).     

LaGO: a (heuristic) Branch and Cut algorithm for nonconvex MINLPs

We present a Branch and Cut algorithm of the software package LaGO to solve nonconvex mixed-integer nonlinear programs (MINLPs). A linear outer approximation is constructed from a convex relaxation of the problem. Since we do not require an algebraic representation of the problem, reformulation techniques for the construction of the convex relaxation cannot be applied, and we are restricted to sampling techniques in case of nonquadratic nonconvex functions. The linear relaxation is further improved by mixed-integer-rounding cuts. Also box reduction techniques are applied to improve efficiency. Numerical results on medium size test problems are presented to show the efficiency of the method.