Disjunctive programming and a hierarchy of relaxations for discrete optimization problems.

*(English)*Zbl 0592.90070Summary: We discuss a new conceptual framework for the convexification of discrete optimization problems, and a general technique for obtaining approximations to the convex hull of the feasible set. The concepts come from disjunctive programming and the key tool is a description of the convex hull of a union of polyhedra in terms of a higher dimensional polyhedron. Although this description was known for several years, only recently was it shown by R. G. Jeroslow and J. K. Lowe [Math. Program. Study. 22, 167-184 (1984; Zbl 0554.90081)] to yield improved representations of discrete optimization problems. We express the feasible set of a discrete optimization problem as the intersection (conjunction) of unions of polyhedra, and define an operation that takes one such expression into another, equivalent one, witgh fewer conjuncts. We then introduce a class of relaxations based on replacing each conjunct (union of polyhedra) by its convex hull. The strength of the relaxations increases as the number of conjuncts decreases, and the class of relaxations forms a hierachy that spans the spectrum between the common linear programming relaxation, and the convex hull of the feasible set itself. Instances where this approach has advantages include critical path problems in disjunctive graphs, network synthesis problems, certain fixed charge network flow problems, etc. We illustrate the approach on the first of these problems, which is a model for machine sequencing.

##### MSC:

90C10 | Integer programming |

52Bxx | Polytopes and polyhedra |

90B35 | Deterministic scheduling theory in operations research |

90B10 | Deterministic network models in operations research |

90C35 | Programming involving graphs or networks |

##### Keywords:

convexification of discrete optimization problems; approximations to the convex hull of the feasible set; disjunctive programming; unions of polyhedra; relaxations; critical path problems; network synthesis; fixed charge network flow problems; machine sequencing
PDF
BibTeX
XML
Cite

\textit{E. Balas}, SIAM J. Algebraic Discrete Methods 6, 466--486 (1985; Zbl 0592.90070)

Full Text:
DOI

##### References:

[1] | Balas, Egon, Machine sequencing via disjunctive graphs: an implicit enumeration algorithm, Operations Res., 17, 941, (1969) · Zbl 0183.49404 |

[2] | Balas, Egon; Mangasarian, O.; Meyer, R. R.; Robinson, S., Disjunctive programming: cutting planes from logical conditions, Nonlinear programming, 2 (Proc. Sympos. Special Interest Group on Math. Programming, Univ. Wisconsin, Madison, Wis., 1974), 279, (1974), Academic Press, New York · Zbl 0349.90117 |

[3] | Disjunctive programming: properties of the convex hull of feasible pointsMSRR No. 348Carnegie-Mellon Univ.Pittsburgh, PA1974July |

[4] | Balas, Egon, Disjunctive programming, Ann. Discrete Math., 5, 3, (1979) · Zbl 0409.90061 |

[5] | Balas, Egon, Cutting planes from conditional bounds: a new approach to set covering, Math. Programming Stud., 19, (1980) · Zbl 0435.90073 |

[6] | Balas, Egon; Ho, Andrew, Set covering algorithms using cutting planes, heuristics, and subgradient optimization: a computational study, Math. Programming Stud., 37, (1980) · Zbl 0435.90074 |

[7] | Balas, Egon; Jeroslow, RobertG., Strengthening cuts for mixed integer programs, European J. Oper. Res., 4, 224, (1980) · Zbl 0439.90064 |

[8] | Balas, E.; Pulleyblank, W. R., The perfectly matchable subgraph polytope of a bipartite graph, Networks, 13, 495, (1983) · Zbl 0525.90069 |

[9] | Blair, C., Facial disjunctive programs and sequences of cutting-planes, Discrete Appl. Math., 2, 173, (1980) · Zbl 0459.90054 |

[10] | Campello, R. E.; Maculan, N.; Cottle, W.; Kelmanson, M. L.; Korte, B., On deep disjunctive cutting planes for set partitioning: a computationally oriented research, Mathematical programming (Rio de Janeiro, 1981), 69, (1984), North-Holland, Amsterdam · Zbl 0538.90062 |

[11] | Cutting planes for relaxations of integer programsMSRR No. 347Carnegie-Mellon Univ.Pittsburgh, PA1974 |

[12] | Jeroslow, R. G., Cutting-plane theory: disjunctive methods, Studies in integer programming (Proc. Workshop, Bonn, 1975), (1977), North-Holland, Amsterdam · Zbl 0358.90035 |

[13] | Modeling with integer variablesGeorgia Institute of TechnologyAtlanta1982 |

[14] | Lenstra, J., Sequencing by enumerative methods, (1977) · Zbl 0407.90025 |

[15] | NĂ©meti, L., Das reihenfolgeproblem in der fertigungsprogrammierung und linearplanung mit logischen bedingungen, Mathematics, (Cluj), 6, 87, (1964) · Zbl 0137.38007 |

[16] | Tighter relaxations of fixed charge network flow problemsGeorgia Institute of TechnologyAtlanta1979May |

[17] | Sherali, HanifD.; Shetty, C. M., Optimization with disjunctive constraints, (1980) · Zbl 0437.90052 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.