HOME    »    SCIENTIFIC RESOURCES    »    Volumes
Abstracts and Talk Materials
Mixed Integer Programming
July 25 - 29, 2005


Tobias Achterberg (Konrad-Zuse-Zentrum für Informationstechnik (ZIB))

Conflict analysis in mixed integer programming
July 28, 2005

Conflict analysis for infeasible subproblems is one of the key ingredients in modern SAT solvers to cope with large real-world instances. In contrast, it is common practice for today's mixed integer programming solvers to just discard infeasible subproblems and the information they reveal.

In this talk we try to remedy this situation by generalizing SAT infeasibility analysis to mixed integer programming. We present heuristics for branch-and-cut solvers to generate valid inequalities from the current infeasible subproblem and the associated branching information. SAT techniques can then be used to strengthen the resulting cuts. We performed computational experiments which show the potential of our method: On feasible MIP instances, the number of required branching nodes was reduced by 50% in the geometric mean. However, the total solving time increased by 20%. On infeasible MIPs arising in the context of chip verification, the number of nodes was reduced by 90%,thereby reducing the solving time by 60%.

Edoardo Amaldi (Politecnico di Milano)

Randomized relaxation methods for the Maximum Feasible Subsystem problem
December 31, 1969

In the MaxFS problem, given an infeasible linear system Ax>=b, one wishes to find a feasible subsystem containing a maximum number of inequalities. This NP-hard problem has interesting applications in a variety of fields. In some challenging applications in telecommunications and computational biology one faces very large MaxFS instances with up to millions of inequalities in thousands of variables. We propose to tackle large-scale instances of MaxFS using randomized and thermal variants of the classical relaxation method for solving systems of linear inequalities. We establish lower bounds on the probability that these methods identify an optimal solution within a given number of iterations. These bounds, which are expressed as a function of a condition number of the input data, imply that with probability 1 these randomized methods identify an optimal solution after finitely many iterations. Computational results obtained for medium- to large-scale instances arising in the design of linear classifiers, in the planning of digital video broadcasts and in the modelling of the energy functions driving protein folding, indicate that an efficient implementation of such a method perform very well in practice.

Joint work with P. Belotti and R. Hauser.

Kent Andersen (Université Catholique de Louvain)

Strengthening the formulation of mixed integer programs with an example in production scheduling
July 28, 2005

Joint work with Yves Pochet.

We consider the following question: Is it possible to replace a constraint of a MIP formulation with a new and tighter inequality? We show that, if there is a valid inequality, which dominates a constraint of the formulation, then there is a coefficient in the formulation that can be strengthened. We also show that an algorithm, which is based on strengthening one coefficient at a time, stops after a finite number of strengthening steps. We give examples for which the difference between the quality of the original formulation and a resulting strengthened formulation is relatively large: on some problems, the effect of modifying the coefficients in the original formulation is larger than the effect of adding a large number of cutting planes (in terms of amount of integrality gap closed). For instance, on one MIPLIB instance, all of the integrality gap is closed by strengthening the coefficients in the initial formulation while optimizing over the first Chvatal closure only closes 61% of the integrality gap. We also solve another "hard" instance to optimality by strengthening coefficients in every round of a cutting plane algorithm based on mixed integer Gomory cuts and split cuts. The same cutting plane algorithm was unable to solve this instance without including the strengthening step. The instance was only recently solved with an approach based on the first Chvatal closure.

We finish by demonstrating how coefficient strengthening can be used to design a model for a production scheduling problem. First, an initial formulation of a small problem is produced, and the coefficients in this formulation are strengthened with expensive techniques. The resulting formulation is then evaluated by tracing the logic of each strengthened coefficient. The result is a new understanding of how to build a tight formulation of the problem. We believe this suggests that it might be of interest to construct a tool for strengthening coefficients.

Egon Balas (Carnegie-Mellon University)

Recent advances in lift and project
July 25, 2005

In a recent joint paper with Michael Perregaard a precise correspondence was established between lift-and-project cuts for mixed 0-1 programs, simple disjunctive cuts (intersection cuts) and mixed-integer Gomory cuts. The correspondence maps members of one family onto members of the others. It also establishes a many-to-one mapping between bases of the higher-dimensional cut generating linear program (CGLP) and bases of the linear programming relaxation of the given mixed integer program. As a result, an algorithm is developed that solves (CGLP) without explicitly constructing it, by mimicking the pivoting steps of the higher dimensional (CGLP) simplex tableau by certain pivoting steps in the lower dimensional LP simplex tableau. Due to the smaller problem size and the vastly reduced number of pivots needed by the new algorithm, it finds a deepest lift-and-project cut typically in a fraction of the time needed by the original (CGLP)-based algorithm.

The new cut generating procedure can also be interpreted as an algorithm for systematically strengthening mixed integer Gomory (MIG) cuts. Starting with a MIG cut from a given source row k of the optimal LP simplex tableau, a certain sequence of pivots is performed, each of which results in a new simplex tableau, generally neither primal nor dual feasible, such that the MIG cut from the same source row k is guaranteed to be stronger (in terms of the amount by which it cuts off the LP optimum) then the previous MIG cut. In other words, if S is the set of all bases (feasible or not) of the LP relaxation, this procedure finds a member B of S such that the MIG cut from row k of the simplex tableau associated with B is strongest over all bases in S.

After extensive computational testing, the new procedure has been incorporated in the MIP module of the commercial code XPRESS, where it serves as the default cut generating routine.

Dimitris Bertsimas (Massachusetts Institute of Technology)
http://web.mit.edu/dbertsim/www/
Daniel Bienstock (Columbia University)
http://www.columbia.edu/~dano/
Adam N. Letchford (University of Lancaster)
http://www.lancs.ac.uk/staff/letchfoa/
George L. Nemhauser (Georgia Institute of Technology)
Robert Weismantel (Otto-von-Guericke-Universität Magdeburg)
http://www.ifor.math.ethz.ch/staff/weismant

Roundtable discussion
July 26, 2005

1. Funding issues Is IP research still fundable? Differences between US and Europe 2. Raising IP's profile Does the profile need to be raised? If so, how? New application areas? 3. Cultivating a research community How to increase collaboration Differences between US and Europe 4. IP research directions--What are "the next big ideas?" 5. IP education 6. The next conference? Does this conference have its own niche? (IPCO/MPS/etc.) When? Where?

Daniel Bienstock (Columbia University)
http://www.columbia.edu/~dano/

Applying discrete optimization to robust power grid problems
July 27, 2005

During the past decade several major power blackouts affected North America, Europe and South America. It is quite likely (in fact, expected) that more serious events will take place in the future, with potentially very damaging consequences to economies and public health. Rather than being the result of particular economic or operational factors, the blackouts can be seen as caused by the inherent complexity entailed by modern transmission networks, which comprise thousands of nodes and links and span very large geographical areas.

In this talk we will describe ongoing work on solving a number of optimization models related to the design, maintenance and operation of electrical power transmission networks. This is joint work with Sara Mattia (Rome).

Miguel Constantino (University of Lisbon)

A special case of the integer single node flow set with upper bounds
July 25, 2005

In this talk we discuss the polyhedral structure of the convex hull of the integer single node flow set with two possible values for the upper bounds on the arc flows. These mixed integer sets may arise as substructure of more complex mixed integer sets that model the feasible solutions of real application problems such as network design, location and lotsizing. We give a complete description of this special integer single node flow polyhedron based on the generalization of the description of the integer single node flow polyhedron with two arcs. All the coefficients of the facet-defining inequalities can be computed in polynomial time adapting a known algorithm from Hirschberg and Wong (1976) for the two integer knapsack problem. We report on computational experience.

Joint work with Agostinho Agra.

Ismael Regis de Farias JR. (University at Buffalo (SUNY))

Branch-and-cut for cardinality constrained optimization
July 25, 2005

Given a set of continuous variables and for each variable a constant, a cardinality constraint requires that no less than a specified number of variables is equal to their corresponding constants. Cardinality constraints appear in several applications, such as feature selection in data mining. I will present a polyhedral study of problems with cardinality constraints and a branch-and-cut approach to solve them. In particular, I will present a few unusual properties of these polyhedra.

Joint work with Ming Zhao.

Sven de Vries (TU München)

Faster separation of 1-wheel inequalities for stable set polytopes
July 26, 2005

For the solution of hard integer programs with branch-and-cut algorithms it is a necessity to check during the separation phase for violated inequalities of the stable set relaxation of the instances conflict graph. These conflict graphs turn out to be sparse. For instance the majority (39/60) of the new and difficult MIPLIB2003 integer programs contain large substructures with constraints of type xi 1 for binary variables.

A stable set in a graph G=(V,E) is a set of pairwise nonadjacent vertices. A common approach for finding a maximum weight stable set of G is to optimize over the convex hull STAB(G) of the incidence vectors of stable sets; this approach requires knowledge of strong valid inequalities and algorithms to separate them. We present an O(|V|2|E|+|V|3log |V|) separation algorithm for the nonsimple 1-wheel inequalities (Cheng and Cunningham, 1995), which is faster than the previously known O(|V|4) algorithm. In particular this is faster for the sparse instances coming from the conflict graphs of general integer programs.

Jonathan Eckstein (Rutgers, The State University of New Jersey)

Rounding heuristics and ramp-up procedures for parallel MIP
December 31, 1969
    Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • Slides(pdf)

This poster describes a heuristic method for mixed integer programming (MIP), and its incorporation into PICO, a highly parallel branch-and-bound MIP solver. The heuristic performs pivot-based rounding with the help of a concave integrality merit function. The surrounding branch-and-bound environment begins with a synchronous "ramp-up" phase, and then transitions to asynchronous tree-parallel search. During ramp-up, there are several ways of inducing parallelism: using multiple alternative merit functions, and partitioning the search space by prospective branching. I discuss how to combine these two approaches and how to prospectively branch on multiple layers of variables, along with implementation and computational results for the PICO MIP solver.

Friedrich Eisenbrand (Max-Planck-Institut für Informatik)

Split cuts and the stable set polytope of quasi-line graphs
July 26, 2005

Edmonds showed in 1965 that the convex hull of all matchings of a graph can be obtained by applying one round of Gomory-Chv'atal cutting planes to the fractional matching polytope. More precisely, he showed that this convex hull can be described by non-negativity, degree and odd-set constraints.

15 years later, Minty and Sbihi showed that a maximum-cardinality stable set in a claw-free graph can be computed in polynomial time, thereby generalizing Edmonds' algorithm for maximum cardinality matching. Since then, it is a long standing open problem to find an explicit description of the stable set polytope of claw-free graphs.

In this talk we show that the convex hull of stable sets of quasi-line graphs is obtainable by applying one round of split cuts. The class of quasi-line graphs is a proper superclass of line graphs and a proper subclass of claw-free graphs for which it is known that not all facets have 0/1 normal vectors. The necessary split-cuts are a generalization of Edmonds' odd-set inequalities, called clique family inequalities.

Joint work with G. Oriolo, P. Ventura and G. Stauffer.

Oktay Gunluk (IBM)
http://www.research.ibm.com/people/o/oktay/

Two-step MIR inequalities for mixed-integer sets
July 26, 2005
    Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • Slides(pdf)

In the first part of the talk, we use facets of simple mixed-integer sets with three variables to derive a parametric family of valid inequalities for general mixed-integer sets. We call these inequalities "two-step MIR inequalities" as they can be derived by applying the simple mixed-integer rounding (MIR) principle of Wolsey (1998) twice.

In the second part, we study the shooting experiment of Gomory which computationally identifies "important" facets of the cyclic group polyhedra. This idea has recently been re-considered by Evans (2002) and Gomory, Johnson and Evans (2003). We present computational results that suggest that MIR and two-step MIR inequalities are important.

In the last part of the talk, we present computational experience with general mixed-integer programs.

Joint work with Sanjeeb Dash at IBM Research.

Xiaoyun Ji (Rensselaer Polytechnic Institute)

Branch-and-Price-and-Cut on Clique Partition Problem with Minimum Clique Size Requirement
December 31, 1969
    Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • Slides(pdf)

Given a complete graph G=(V,E) with edge weight on each edge, we consider the problem of partitioning the vertices of graph G into subcliques that have at least S vertices, so as to minimize the total weight of the edges that have both endpoints in the same subclique. In this poster, we consider using branch-and-price method to solve the problem. We demonstrated the necessity of cutting planes for this problem and suggested effective ways of adding cutting planes in the branch-and-price framework. The NP hard pricing problem is solved as an integer programming problem. We present some preliminary computational results on large randomly generated problems.

Miroslav Karamanov (Carnegie-Mellon University)

Branching on general disjunctions
December 31, 1969

Joint work with Gerard Cornuejols.

This paper considers a modification of the branch-and-cut algorithm for Mixed Integer Linear Programming problems where branching is performed on general disjunctions rather than on variables. We introduce a procedure for selecting promising disjunctions based on a heuristic measure of disjunction quality. This measure exploits the relation between branching disjunctions and intersection cuts. In this work, we focus on disjunctions defining mixed integer Gomory cuts. The procedure is tested on instances from the literature. Experiments show that the proposed procedure is more efficient than branching on variables for a majority of the instances. The metrics we consider are solution time and tree size for the instances that could be solved to optimality within a given time limit, and integrality gap closed for the remaining instances.

Jean Bernard Lasserre (Centre National de la Recherche Scientifique (CNRS))
http://www.laas.fr/~lasserre/

Integerprogramming, duality and superadditive functions
July 29, 2005
    Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • Slides(pdf)

We consider the general integer program P: max {c'x : Ax=b; x nonnegative integer} which has a well-known abstract dual optimization problem stated in terms of superadditive functions. Using a linear program equivalent to P, introduced recently, we show that its dual can be interpreted as a simplified and more tractable form of the abstract dual, and identifies a subclass of superadditive functions, sufficient to consider in the abstract dual. This class of superadditive functions is also used to characterize the integer hull of the convex polytope {x : Ax=b; x nonnegative}.

Andrea Lodi (IBM)
http://www.or.deis.unibo.it/lodi.html

Heuristic integer (and mixed integer) linear programming
July 28, 2005

In recent years a lot of work has been devoted to general-purpose methods for finding good heuristic solutions to Integer and Mixed Integer Linear Programs (MIPs). Some of these methods are now successfully integrated in commercial and non commercial MIP solvers. We review these results, compare some of the techniques, discuss advantages and drawbacks and we try to give a flavor of what has still to be done in the area.

Marco Luebbecke (TU Berlin)

Locomotives and rail cars: Switching, routing, and scheduling
December 31, 1969

Industrial switching involves moving materials on rail cars within or between industrial complexes and connecting with other rail carriers. Planning tasks include the making up of trains with a minimum shunting effort, the feasible and timely routing through an in-plant rail network on short paths, and assigning and scheduling of locomotives under safety and network capacity aspects. A human planner must often resort to routine and simple heuristics, not least for the reason of unavailability of computer aided suggestions. In this project we propose mixed integer programming models to capture the whole process at once in order to obtain optimal or provably good solutions. Column generation allows us to work with linear programming relaxations with a huge number of variables. This popular technique has almost attained an industry standard level and usually enables one to set up appropriate models quickly. The challenge hides in the actual implementation which still needs tailoring to the particular application. Our work is based on practical data from a German in-plant railroad.

Francois Margot (Carnegie-Mellon University)
http://wpweb2.tepper.cmu.edu/fmargot/index.html

Symmetry in integer programming
July 27, 2005

This talk is an overview of techniques used to handle problems with symmetries. For problems modeled as integer linear programs (ILP), three essentially different and mutually exclusive approaches have been used: Reformulations, symmetry-breaking inequalities, and isomorphism pruning.

Reformulation is mostly used to handle problems where the symmetries come from the set of all permutations of a set of objects, inducing a permutation group on the variables. Some (or most) symmetries are removed from the formulations and additional branching strategies become available. The price to pay is that the reformulation has an exponential number of variables that must be handled by column generation techniques.

Adding symmetry breaking inequalities is probably the most natural way to try to handle symmetries. Several papers report strong improvements when using the best possible symmetry breaking set of inequalities. Methods for deriving such sets have been devised, but little is known about finding the most efficient set.

Isomorphism pruning is based on the theory of isomorphism-free backtracking procedure for enumeration problems. When coupled with a Branch-and-Cut algorithm, additional options for generating isomorphism-related cuts and setting variables are available. Improvements of several orders of magnitude for running time and enumeration tree size have been observed on highly symmetric 0-1 problems. Extensions of the techniques to ILP with variables bounded to a small set and to ILP corresponding to coloring problems are also available.

Sanjay Mehrotra (Northwestern University)

On generalized branching methods for mixed integer programming
July 29, 2005

We present a restructuring of the computations in Lenstra's methods for solving mixed integer linear programs. A concept of Adjoint lattices is introduced and used for this purpose. This allows us to develop branching on hyperplane algorithms in the space of original variables, without requiring any dimension reduction for pure or mixed integer programs. Reduced lattice basis are also computed in the space of original variables. Based on these results we give a new natural heuristic way of generating branching hyperplanes, and discuss its relationship with recent reformulation techniques of Aardal and Lenstra. We show that the reduced basis available at the root node has useful information on the branching hyperplanes for the generalized branch-and-bound tree. Our development allows us to give algorithms for mixed convex integer programs with properties similar to those for the mixed integer linear programs. Implementation of this algorithm in a prototype software system "IMPACT" is described. Computational results are presented on difficult knapsack and market split problems using this approach.

Gabor Pataki (University of North Carolina)
http://www.unc.edu/~pataki/

Column basis reduction, decomposable knapsack and cascade problems
July 28, 2005

We propose a very simple preconditioning method for integer programming feasibility problems: applying basis reduction to the constraint matrix, to make its columns shorter in euclidean norm, and more orthogonal. Our approach -- termed column basis reduction, and abbreviated as CBR -- simplifies and generalizes the reformulation technique proposed for equality constrained IPs by Aardal, Hurkens, Lenstra and others.

We describe a family of IP instances, called decomposable knapsack problems, that generalize the ones proposed by Jeroslow, Chvatal and Todd, Avis, Aardal and Lenstra, and Wolsey. We prove that 1) they need an exponential number of nodes to solve, when branch-and-bound branching on individual variables is applied; 2) after the application of column basis reduction, a constant number of nodes suffice.

A subclass of decomposable knapsack problems is called cascade problems. They were created to illustrate the surprising fact, that in hard IPs a "thin" direction is sometimes not the best to branch on. Besides having this structure, the cascade problems -- despite having only one dense constraint -- are as difficult for commercial MIP solvers, as the well-known marketshare problems.

Our computational study shows that most difficult IPs recently used to test nontraditional IP algorithms -- subset sum, strongly correlated knapsack problems, the marketshare problems, and our cascade problems -- become easy for a commercial IP solver after our preconditioning is applied.

Joint work with Bala Krishnamoorthy at Washington State University.

Michael Perregaard (Dash Associates)

Constraint branching and disjunctive cuts for mixed integer programs
July 28, 2005
    Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • Slides(pdf)
  • Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • Slides(ppt)

Several disjunctive cuts for mixed integer programs are (directly or indirectly) based on imposing a simple disjunction where a single fractional variable is required to be rounded either up or down to its nearest integer value. Two well-known cut families based on such a disjunction is Gomory's mixed integer cut and the lift-and-project cuts from the 1990s. Both cut classes involves strengthening by considering the integrality of other variables. This strengthening can be interpreted as a modification of the underlying simple disjunction. Later research into disjunctive cuts have taken this idea of strengthening the underlying disjunction even further.

The most common method for solving a mixed integer program is by branch-and-bound. Almost all such available codes branch on a single variable at a time. For general mixed integer programs, where the integer variables are allowed a wider range than simple 0-1 variables, such a simple branching scheme can often lead to an explosion in the number of nodes the code has to search. In this talk I examine the feasibility of applying the ideas for strengthening cuts to the simple branching disjunctions for the purpose of creating better mixed integer branches. Results from computational tests on a variety of public benchmark problems, using an implementation based on the Xpress-MP solver, will be used to demonstrate the effects of such strengthened branches.

Juan-Jose Salazar-Gonzalez (University of La Laguna)

Solving mixed integer programs arising in statistical data editing
July 27, 2005
    Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • Slides(pdf)

National Statistical Agencies needs automatic tools for detecting errors in records not satisfying a set of consistency rules. The topic is known as Statistical Data Editing, and a very interesting Optimization Problem is the so-called Error Localization Problem. It concerns finding the minimum number of fields in an invalid record such that by modifying these values the new record satisfies all the rules. It is an NP-hard problem because the "Minimum Weight Solution to Linear Equations" is a particular case. Also the Error Localization Problem is very important in Signal Processing (the problem is then called "Basis Selection Problem"),

where information must be encoded and sent, or received and decoded, through a Telecommunication Network.

We present an exact method, based on a Benders' decomposition approach, solving instances with up to 100 fields and 40 edits. We also produce a variant of this approach to solve heuristically larger instances. Some procedures of this descending search make use of the Farkas' Lemma in Linear Programming. Computational experience on randomly generated instances shows that the approach can deal with instances of up to 1000 fields and 400 edits.

The generality of the consistency rules makes the Error Localization Problem very close to a general Mixed Integer Programming. Still, there is some structure. Therefore, we will open a discussion to the audience on how new results in Mixed Integer Programming could help solving Error Localization Problems, and viceversa!

This is part of a joint research work with Jorge Riera-Ledesma, University of La Laguna, Tenerife, Spain.

Anureet Saxena (Axioma Inc.)
http://www.andrew.cmu.edu/user/anureets/

Optimizing over the split closure - Modeling and theoretical analysis
December 31, 1969

The polyhedron defined by all the split cuts obtainable directly (i.e. without iterated cut generation) from the LP-relaxation of a mixed integer program (MIP) is termed the split closure of the MIP. This paper deals with the problem of optimizing over the split closure. By the equivalence of optimization and separation, we can restrict our attention to the following separation problem: given a fractional point, say x, find a split cut violated by x or show that none exists. We show that this separation problem can be formulated as a parametric mixed integer linear program (PMILP) with a single parameter in the objective function and the right hand side. We discuss a branch and bound algorithm for PMILP, based on solving a parametric linear program at every node of the search tree, while using warm-start basis information. Further, we recast the PMILP as the problem of minimizing a function that is the infimum of a family of convex functions. As a result, for several sub-classes of split cuts, the PMILP can be deparameterized. Implementation and experimentation is under way.

Joao Luis Cardoso Soares (University of Coimbra)
http://www.mat.uc.pt/~jsoares

Finding the nearest point in a polytope according to any metric
December 31, 1969

A terminating algorithm is developed for the problem of finding the point of smallest norm in the convex hull of a given finite point set in a finite dimensional space. The proposed algorithm mimics Ph. Wolfe's algorithm (Wolfe'76) developed for the Euclidean norm and shares all of its basic properties. The proposed algorithm has great potential as a numerical mechanism to generating consecutive deepest disjunctive cuts in integer programming.

Eduardo Uchoa (Fluminense Federal University)

Robust branch-and-cut-and-price for the capacitated minimum spanning tree problem
July 27, 2005
    Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • slides(pdf)
  • Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • Slides(ppt)

We propose a new formulation for the capacitated minimum spanning tree problem that leads to a robust branch-and- cut-and-price algorithm. The formulation allows the use of cuts expressed over a very large set of variables, without changing the pricing subproblem or increasing the size of LPs that are actually solved. Cuts over those variables can be quite strong, and generalize many previous know families of cuts, including capacity, root cutsets and multistars. Computation results on benchmark instances from the OR-Library show very significant improvements over previously known algorithms, specially on non-unitary weight instances.

Joint work with D.Andrade, R.Fukasawa, J.Lysgaard and M.Poggi de Aragao.

Francois Vanderbeck (Université de Bordeaux I)
http://www.math.u-bordeaux.fr/~fv/

Branching in branch-and-price algorithms
July 25, 2005
    Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • Abstract (pdf)
  • Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • Working Paper(pdf)
  • Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • Slides(pdf)

In Branch-and-Price algorithms, implementing the branching scheme can be challenging. Branching constraints may imply modifications to the pricing problem. This is a main concern for the development of a generic branch-and-price code that should run using only the pricing oracle provided by the user. The issue has not stop people from using Branch-and-Price. Firstly, branching is straightforward for many applications (we shall characterize the class of problem for which this is the case). Then, Ryan and Foster (1981) proposed a scheme for applications that can be reformulated as a set covering problem. Beyond that, a general scheme was presented by Vanderbeck (2000) but it may result in significant modifications to the pricing problem. An alternative is the scheme of Villeneuve et al. (2003) that consists in applying branching in the original formulation, but this introduces symmetry in the Dantzig-Wolfe reformulation when the problem structure involves several identical blocks. The branching scheme presented here builds on the aboves. It can be can be implemented using only the oracle provided for the original pricing problem. Branching constraints are not dualized in a Lagrangian way but are convexified in the subproblem.

Robert Weismantel (Otto-von-Guericke-Universität Magdeburg)
http://www.ifor.math.ethz.ch/staff/weismant

Mixed integer polynomial programming
July 29, 2005

This talk deals with mixed integer optimization problems defined by linear constraints and a polynomial function as the objective function. We present motivating examples, illustrate techniques that reduce the problem to a mixed integer linear program and discuss complexity results. An algorithm is prersented that is based on Barvinok's rational function theory, i.e., lattice points in polyhedra are encoded through rational functions. It turns out that under the assumption that the number of variables is fixed, our algorithm leads to a fully polynomial time approximation scheme. The results of this talk are based on joint work with Raymond Hemmecke, Matthias Koeppe and Jesus De Loera.

Laurence Wolsey (Université Catholique de Louvain)

A basic mixed integer set: the mixing set and its applications
July 26, 2005
    Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 156 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 157 Warning: mkdir(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 162 Warning: chmod(): No such file or directory in /srv/IMAPropel/build/classes/discovery3/Activity.php on line 163
  • Slides(pdf)

Very little is known about the polyhedral structure of even simple mixed integer programs. Here we study a very simple set, called the mixing set. This set and valid inequalities for it were proposed by Gunluk and Pochet in an effort to explain and understand why the same procedure of "mixing mixed integer rounding (MIR) inequalities" gave valid inequalities for many different variants of the constant capacity lot-sizing problem, and subsequently Miller and Wolsey took this abstraction a little further by considering the intersection of mixing sets plus certain additional constraints.

In this talk we pursue this effort at abstraction by considering two "abstract sets" that are generalizations of the mixing set. We show that, modulo a slight restriction, the convex hulls of both sets are obtained with mixing inequalities. This is joint work with Michele Conforti and Marco di Summa.

Turning back to lot-sizing, we show that a constant capacity problem with production time windows, and surprisingly both a multi-item problem with a joint set-up variable, and a class of single item problems with varying capacities can also be solved by mixing. The latter is joint work with Yves Pochet.

PDF file with formulations

Yu Xia (The Institute of Statistical Mathematics)

A cutting algorithm for the minimum sum-of-squared error clustering
December 31, 1969

We give necessary and sufficient conditions for the local optimal solutions of the minimum sum-of-squares clustering problem and its continuous relaxation. Especially, we show that the objective function of the mixed integer program is concave and each local solution of its continuous relaxation is integer. We then adapt Tuy's concavity cuts to the continuous relaxation to search for a global optimal solution of the clustering problem. Numerical results show that our algorithm general gives a better solution than the popular k-means method starting from the same point without increasing computation time too much. (In the proceedings of the 5th SIAM international conference on data mining. http://optlab.mcmaster.ca/~xiay/papers/ssqeproced.pdf Presentation slides available at http://optlab.mcmater.ca/~xiay/papers/ssqeslides.pdf

Connect With Us:
Go