Generating cuts in integer programming with families of special ordered sets

DOI10.1016/0377-2217(90)90302-RMaRDI QIDQ922293zbMATH OpenOpenAlexFDO

Authors John M. Wilson

Publication date 1990

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0377-2217(90)90302-r

zbMATH Keywords

branch-and-boundcuts

Mathematics Subject Classification ID

Computational methods for problems pertaining to operations research and mathematical programming (90-08) Integer programming (90C10)

Review text

The author describes families of cuts which can be added to integer programming problems incorporating special ordered sets. Ways in which the cuts can be used to attempt to narrow the gap between a continuous optimum and a feasible integer solution at any stage in the branch-and- bound method are discussed and some computational experience is presented. The main fault of the paper is the lack of a complete and precise problem formulation as well as any assertion concerning the properties of the described cuts.

Recommendations

• Cutting planes in integer and mixed integer programming
• Spherical cuts for integer programming problems
• Computational Integer Programming and Cutting Planes
• Cutting planes for integer programs with general integer variables
• scientific article; zbMATH DE number 808805

Cites work

• Experimental Results on the New Techniques for Integer Programming Formulations
• scientific article; zbMATH DE number 3617917 (Why is no real title available?)
• Implementations of special ordered sets in MP software
• Linear Programming with Special Ordered Sets
• S3 sets. An extension of the Beale-Tomlin special ordered sets
• Solving 0-1 Integer Programming Problems Arising from Large Scale Planning Models
• Solving Large-Scale Zero-One Linear Programming Problems
• Solving Mixed Integer Programming Problems Using Automatic Reformulation

Cited in

(5)

• Logic cuts for multilevel generalized assignment problems.
• Formulating logical implications in combinatorial optimisation
• Efficient reformulation for 0-1 programs -- methods and computational results
• \(O(n)\) procedures for identifying maximal cliques and non-dominated extensions of consecutive minimal covers and alternates
• Mixed logical-linear programming

Describes a project that uses

Uses Software

• MINOS
• SCICONIC

This page was built for publication: Generating cuts in integer programming with families of special ordered sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q922293)