Classical Cuts for Mixed-Integer Programming and Branch-and-Cut

Padberg, Manfred
October 2005
Annals of Operations Research;Oct2005, Vol. 139 Issue 1-4, p321
Academic Journal
We review classical valid linear inequalities for mixed-integer programming, i.e., Gomory’s fractional and mixed-integer cuts, and discuss their use in branch-and-cut. In particular, a generalization of the recent mixed-integer rounding (MIR) inequality and a sufficient condition for the global validity of classical cuts after branching has occurred are derived.


Related Articles

  • Mixed 0-1 Programming by Lift-and-Project in a Branch-and-Cut Framework. Balas, Egon; Ceria, Sebastián; Cornuéjols, Gérard // Management Science;Sep96, Vol. 42 Issue 9, p1229 

    We investigate the computational issues that need to be addressed when incorporating general cutting planes for mixed 0-1 programs into a branch-and-cut framework. The cuts we use are of the lift-and-project variety. Some of the issues addressed have a theoretical answer, but others are of an...

  • AN IMPLICIT ENUMERATION ALGORITHM FOR QUADRATIC INTEGER PROGRAMMING. McBride, R.D.; Yormark, J.S. // Management Science;Mar80, Vol. 26 Issue 3, p282 

    We present an implicit enumeration algorithm for a nonseparable quadratic integer programming problem. We utilize fathoming criteria derived from Lemke's complementary pivot algorithm, and compare the use of pseudo-costs versus generalized penalties as a guide to branching. Computational...

  • A Dual-Bounded Algorithm for the p-Median Problem. Galvão, Roberto O. // Operations Research;Sep/Oct80, Vol. 28 Issue 5, p1112 

    The p-median problem consists of locating p facilities on a network, so that the sum of shortest distances from each of the nodes of the network to its nearest facility is minimized. A dual bound, based on the dual of the LP relaxation of the integer programming formulation of the problem, is...

  • Merging and Sorting Applied to the Zero-One Knapsack Problem. Ahrens, J. H.; Finke, G. // Operations Research;Nov/Dec75, Vol. 23 Issue 6, p1099 

    Branch-and-bound algorithms are adequate for the solution of a wide range of 0-1 knapsack problems. It is shown that the simplest method of branching is as good as any. However, problems with highly correlated large weights and values quickly become unsolvable in a reasonable time. This paper...

  • Towards a closer integration of finite domain propagation and simplex-based algorithms. Hajian, Mozafar T.; El-Sakkout, Hani; Wallace, Mark; Lever, Jonathan M.; Richards, Barry // Annals of Operations Research;1998, Vol. 81 Issue 1-4, p421 

    This paper describes our experience in implementing an industrial application using the finite domain solver of the ECLiPSe constraint logic programming (CLP) system, in conjunction with the mathematical programming (MP) system, FortMP. In this technique, the ECLiPSe system generates a feasible...

  • A BRANCH SEARCH ALGORITHM FOR THE KNAPSACK PROBLEM. Greenberg, Harold; Hegerich, Robert L. // Management Science;Jan1970, Vol. 16 Issue 5, p327 

    This paper presents an algorithm for the solution of the knapsack problem. The method involves searching the nodes of a tree along a single branch at a time. The algorithm eliminates the computational drawbacks inherent in the usual branch and bound schemes.

  • PRACTICAL SOLUTION OF LARGE MIXED INTEGER PROGRAMMING PROBLEMS WITH UMPIRE. Forrest, J.J.H.; Hirst, J.P.H.; Tomlin, J.A. // Management Science;Jan1974, Vol. 20 Issue 5, p736 

    In this paper we discuss some branch and bound methods implemented in the UMPIRE mathematical programming system for solving practical integer programming problems and give details of computational experience with these methods. We have found that the nontrivial integer programming problems we...

  • A NEW BRANCH-AND-BOUND ALGORITHM FOR THE FIXED-CHARGE TRANSPORTATION PROBLEM. Kennington, Jeff; Unger, Ed // Management Science;Jun76, Vol. 22 Issue 10, p1116 

    A new branch-and-bound procedure specialized for the fixed-charge transportation problem has been developed. The technique strongly exploits the underlying transportation structure. The relaxed problem assumes this form and simple penalties are easily constructed from the optimal solution of...

  • Discrete and geometric Branch and Bound algorithms for medical image registration. Pfeuffer, Frank; Stiglmayr, Michael; Klamroth, Kathrin // Annals of Operations Research;Jun2012, Vol. 196 Issue 1, p737 

    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...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics