Modeling disjunctive constraints with a logarithmic number of binary variables and constraints

Many combinatorial constraints over continuous variables such as SOS1 and SOS2 constraints can be interpreted as disjunctive constraints that restrict the variables to lie in the union of a finite number of specially structured polyhedra. Known mixed integer binary formulations for these constraints have a number of binary variables and extra constraints linear in the number of polyhedra. We give sufficient conditions for constructing formulations for these constraints with a number of binary variables and extra constraints logarithmic in the number of polyhedra. Using these conditions we introduce mixed integer binary formulations for SOS1 and SOS2 constraints that have a number of binary variables and extra constraints logarithmic in the number of continuous variables. We also introduce the first mixed integer binary formulations for piecewise linear functions of one and two variables that use a number of binary variables and extra constraints logarithmic in the number of linear pieces of the functions. We prove that the new formulations for piecewise linear functions have favorable tightness properties and present computational results showing that they can significantly outperform other mixed integer binary formulations.     

A branch-and-cut procedure for the Udine Course Timetabling problem

A branch-and-cut procedure for the Udine Course Timetabling problem is described. Simple compact integer linear programming formulations of the problem employ only binary variables. In contrast, we give a formulation with fewer variables by using a mix of binary and general integer variables. This formulation has an exponential number of constraints, which are added only upon violation. The number of constraints is exponential. However, this is only with respect to the upper bound on the general integer variables, which is the number of periods per day in the Udine Course Timetabling problem.     

Binary extended formulations of polyhedral mixed-integer sets

We analyze different ways of constructing binary extended formulations of polyhedral mixed-integer sets with bounded integer variables and compare their relative strength with respect to split cuts. We show that among all binary extended formulations where each bounded integer variable is represented by a distinct collection of binary variables, what we call “unimodular” extended formulations are the strongest. We also compare the strength of some binary extended formulations from the literature. Finally, we study the behavior of branch-and-bound on such extended formulations and show that branching on the new binary variables leads to significantly smaller enumeration trees in some cases.     

Monoidal cut strengthening revisited

There are two distinct strengthening methods for disjunctive cuts with some integer variables; they differ in the way they modularize the coefficients. In this paper, we introduce a new variant of one of these methods, the monoidal cut strengthening procedure, based on the paradox that sometimes weakening a disjunction helps the strengthening procedure and results in sharper cuts. We first derive a general result that applies to cuts from disjunctions with any number of terms. It defines the coefficients of the cut in a way that takes advantage of the option of adding new terms to the disjunction. We then specialize this result to the case of split cuts for mixed integer programs with some binary variables, in particular Gomory mixed integer cuts, and to intersection cuts from multiple rows of a simplex tableau. In both instances we specify the conditions under which the new cuts have smaller coefficients than the cuts obtained by either of the two currently known strengthening procedures.     

On the integrality of an extreme solution to pluperfect graph and balanced systems

Let A be a nonnegative integer matrix, and let e denote the vector all of whose components are equal to 1. The pluperfect graph theorem states that if for all integer vectors b the optimal objective value of the linear program minse′xvbAx ? b, x ? 0 s is integer, then those linear programs possess optimal integer solutions. We strengthen this theorem and show that any lexicomaximal optimal solution to the above linear program (under any arbitrary ordering of the variables) is integral and an extreme point of sxvbAx ? b, x ? 0 s. We note that this extremality property of integer solutions is also shared by covering as well as packing problems defined by a balanced matrix A.     

How to select a small set of diverse solutions to mixed integer programming problems

Given an oracle that generates a large number of solutions to mixed integer programs, we present exact and heuristic approaches to select a small subset of solutions that maximizes solution diversity. We obtain good results on binary variables, but report scaling problems when considering general integer and continuous variables.     

Symmetric ILP: Coloring and small integers

This paper presents techniques for handling symmetries in integer linear programs where variables can take integer values, extending previous work dealing exclusively with binary variables. Orthogonal array construction and coloring problems are used as illustrations.     

Solving integer programs with a few important binary gub constraints

During a branch and bound search of an integer program, decisions have to be taken about which subproblem to solve next and which variable or special ordered set to branch on. Both these decisions are usually based on some sort of estimated change in the objective caused by different branching. When the next subproblem is chosen, the estimated change in the objective is often found by summing the change caused by changing all integer variables with non-integer values, as if they were independent. For special ordered sets the estimation is done for each set as a whole. The purpose of this paper is to report some results from trying to do a simultaneous estimation for all the variables in a binary gub constraint. By this, the analysed problems contain one or a few constraints saying that the sum ofn binary variables should be equal tom (<n).I am grateful to Scicon Ltd. for giving me access to the SCICONIC source code.     

Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality

The problem of integer programming in bounded variables, over constraints with no more than two variables in each constraint is NP-complete, even when all variables are binary. This paper deals with integer linear minimization problems inn variables subject tom linear constraints with at most two variables per inequality, and with all variables bounded between 0 andU. For such systems, a 2-approximation algorithm is presented that runs in time O(mnU ² log(Un ² m)), so it is polynomial in the input size if the upper boundU is polynomially bounded. The algorithm works by finding first a super-optimal feasible solution that consists of integer multiples of 1/2. That solution gives a tight bound on the value of the minimum. It furthermore has an identifiable subset of integer components that retain their value in an integer optimal solution of the problem. These properties are a generalization of the properties of the vertex cover problem. The algorithm described is, in particular, a 2-approximation algorithm for the problem of minimizing the total weight of true variables, among all truth assignments to the 2-satisfiability problem.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.Research supported in part by ONR contracts N00014-88-K-0377 and N00014-91-J-1241.Research supported in part by ONR contract N00014-91-C-0026.Part of this work was done while the author was visiting the International Computer Science Institute in Berkeley, CA and DIMACS, Rutgers University, New Brunswick, NJ.     

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.

     

Modelling either-or relations in integer programming

Logical relations occur frequently in integer programming problems and are modelled by introducing binary variables in association with linear expressions. Applications requiring constraints involving precedence, exclusion, implication and other conditions give rise to the logical relations OR and IMPLIES in the models. These relations will be considered in this paper from a modelling point of view and formulations investigated for situations where the logical variables link sets of integer variables. Valid inequalities (cuts) that can be added to a model will be developed for a number of the formulations and the computational benefits of these cuts will be considered from an experimental point of view by considering the performance of sets of problem instances. New formulations and combinations of older established formulations will be considered. It will be contended that tight formulations may not always be the most successful.     

Direct methods with maximal lower bound for mixed-integer optimal control problems

Many practical optimal control problems include discrete decisions. These may be either time-independent parameters or time-dependent control functions as gears or valves that can only take discrete values at any given time. While great progress has been achieved in the solution of optimization problems involving integer variables, in particular mixed-integer linear programs, as well as in continuous optimal control problems, the combination of the two is yet an open field of research. We consider the question of lower bounds that can be obtained by a relaxation of the integer requirements. For general nonlinear mixed-integer programs such lower bounds typically suffer from a huge integer gap. We convexify (with respect to binary controls) and relax the original problem and prove that the optimal solution of this continuous control problem yields the best lower bound for the nonlinear integer problem. Building on this theoretical result we present a novel algorithm to solve mixed-integer optimal control problems, with a focus on discrete-valued control functions. Our algorithm is based on the direct multiple shooting method, an adaptive refinement of the underlying control discretization grid and tailored heuristic integer methods. Its applicability is shown by a challenging application, the energy optimal control of a subway train with discrete gears and velocity limits.      

Heuristics Based on Partial Enumeration for the Unrelated Parallel Processor Scheduling Problem

The classical deterministic scheduling problem of minimizing the makespan on unrelated parallel processors is known to be NP-hard in the strong sense. Given the mixed integer linear model with binary decision variables, this paper presents heuristic algorithms based on partial enumeration. Basically, they consist in the construction of mixed integer subproblems, considering the integrality of some subset of variables, formulated using the information obtained from the solution of the linear relaxed problem. Computational experiments are reported for a collection of test problems, showing that some of the proposed algorithms achieve better solutions than other relevant approximation algorithms published up to now.     

Valid inequalities for a single constrained 0-1 MIP set intersected with a conflict graph

In this paper a mixed integer set resulting from the intersection of a single constrained mixed 0–1 set with the vertex packing set is investigated. This set arises as a subproblem of more general mixed integer problems such as inventory routing and facility location problems. Families of strong valid inequalities that take into account the structure of the simple mixed integer set and that of the vertex packing set simultaneously are introduced. In particular, the well-known mixed integer rounding inequality is generalized to the case where incompatibilities between binary variables are present. Exact and heuristic algorithms are designed to solve the separation problems associated to the proposed valid inequalities. Preliminary computational experiments show that these inequalities can be useful to reduce the integrality gaps and to solve integer programming problems.     

A primogenitary linked quad tree approach for solution storage and retrieval in heuristic binary optimization

A data structure, called the primogenitary linked quad tree (PLQT), is used to store and retrieve solutions in heuristic solution procedures for binary optimization problems. Two ways are proposed to use integer vectors to represent solutions represented by binary vectors. One way is to encode binary vectors into integer vectors in a much lower dimension and the other is to use the sorted indices of binary variables with values equal to 0 or equal to 1. The integer vectors are used as composite keys to store and retrieve solutions in the PLQT. An algorithm processing trial solutions for insertion into or retrieval from the PLQT is developed. Examples are provided to demonstrate the way the algorithm works. Another algorithm traversing the PLQT is also developed. Computational results show that the PLQT approach takes only a very tiny portion of the CPU time taken by a linear list approach for the same purpose for any reasonable application. The CPU time taken by the PLQT managing trial solutions is negligible as compared to that taken by a heuristic procedure for any reasonably hard to solve binary optimization problem, as shown in a tabu search heuristic procedure for the capacitated facility location problem. Compared to the hashing approach, the PLQT approach takes the same or less amount of CPU time but much less memory space while completely eliminating collision.     

Decomposition algorithms with parametric Gomory cuts for two-stage stochastic integer programs

We consider a class of two-stage stochastic integer programs with binary variables in the first stage and general integer variables in the second stage. We develop decomposition algorithms akin to the $L$ -shaped or Benders’ methods by utilizing Gomory cuts to obtain iteratively tighter approximations of the second-stage integer programs. We show that the proposed methodology is flexible in that it allows several modes of implementation, all of which lead to finitely convergent algorithms. We illustrate our algorithms using examples from the literature. We report computational results using the stochastic server location problem instances which suggest that our decomposition-based approach scales better with increases in the number of scenarios than a state-of-the art solver which was used to solve the deterministic equivalent formulation.     

Finding all nondominated points of multi-objective integer programs

We develop exact algorithms for multi-objective integer programming (MIP) problems. The algorithms iteratively generate nondominated points and exclude the regions that are dominated by the previously-generated nondominated points. One algorithm generates new points by solving models with additional binary variables and constraints. The other algorithm employs a search procedure and solves a number of models to find the next point avoiding any additional binary variables. Both algorithms guarantee to find all nondominated points for any MIP problem. We test the performance of the algorithms on randomly-generated instances of the multi-objective knapsack, multi-objective shortest path and multi-objective spanning tree problems. The computational results show that the algorithms work well.     

Development of a new approach for deterministic supply chain network design

This paper proposes a mixed integer linear programming model and solution algorithm for solving supply chain network design problems in deterministic, multi-commodity, single-period contexts. The strategic level of supply chain planning and tactical level planning of supply chain are aggregated to propose an integrated model. The model integrates location and capacity choices for suppliers, plants and warehouses selection, product range assignment and production flows. The open-or-close decisions for the facilities are binary decision variables and the production and transportation flow decisions are continuous decision variables. Consequently, this problem is a binary mixed integer linear programming problem. In this paper, a modified version of Benders’ decomposition is proposed to solve the model. The most difficulty associated with the Benders’ decomposition is the solution of master problem, as in many real-life problems the model will be NP-hard and very time consuming. In the proposed procedure, the master problem will be developed using the surrogate constraints. We show that the main constraints of the master problem can be replaced by the strongest surrogate constraint. The generated problem with the strongest surrogate constraint is a valid relaxation of the main problem. Furthermore, a near-optimal initial solution is generated for a reduction in the number of iterations.     

Discrete and geometric Branch and Bound algorithms for?medical image registration

Aiming at the development of an exact solution method for registration problems, we present two different Branch & Bound algorithms for a mixed integer programming formulation of the problem. The first B&B algorithm branches on binary assignment variables and makes use of an optimality condition that is derived from a graph matching formulation. The second, geometric B&B algorithm applies a geometric branching strategy on continuous transformation variables. The two approaches are compared for synthetic test examples as well as for 2-dimensional medical data. The results show that medium sized problem instances can be solved to global optimality in a reasonable amount of time.     

On the relative strength of split,triangle and quadrilateral cuts

Integer programs defined by two equations with two free integer variables and nonnegative continuous variables have three types of nontrivial facets: split, triangle or quadrilateral inequalities. In this paper, we compare the strength of these three families of inequalities. In particular we study how well each family approximates the integer hull. We show that, in a well defined sense, triangle inequalities provide a good approximation of the integer hull. The same statement holds for quadrilateral inequalities. On the other hand, the approximation produced by split inequalities may be arbitrarily bad.