Abstract
This paper shows that any linear disjunctive program with a finite number of constraints can be transformed into an equivalent facial program. Based upon linear programming technique, a new, finite cutting plane method is presented for the facial programs.
Zusammenfassung
Die Arbeit zeigt, daß jedes lineare disjunktive Optimierungsproblem mit endlich vielen Restriktionen in ein äquivalentes Fazetten-Problem transformiert werden kann. Auf der Grundlage von linearer Optimierungstechnik wird für das Fazetten-Problem ein neues, endliches Schnittebenenverfahren vorgestellt.
Similar content being viewed by others
References
Balas E (1974) Disjunctive programming: Properties of the convex hull of feasible points. MSRR 384, GSIA, Carnegie-Mellon University
Balas E (1975) Nonconvex programming via generalized polars. SIAM Journal on Applied Mathematics 28: 335–349
Balas E (1979) Disjunctive programming. Annals of Discrete Mathematics 5: 3–51
Best MJ, Ritter K (1985) Linear Programming: Active Set Analysis and Computer Programs. Prentice-Hall, Englewood Cliffs, New Jersey
Fülöp J (1988) The transformation of the linear disjunctive programming problem into a facial problem. Zeitschrift für Angewandte Mathematik und Mechanik 68: 440–441
Gianessi F, Tomasin E (1974) Nonconvex quadratic programs, linear complementarity problems, and integer linear programs. In: Hammer PL, Zoutendijk G (eds.), Mathematical Programming in Theory and Practice, North-Holland, Amsterdam: 161–199
Jeroslow RG (1978) Cutting planes for the complementarity constraints. SIAM Journal on Control and Optimization 16: 56–62
Jeroslow RG (1980) A cutting plane game for facial disjunctive programs. SIAM Journal on Control and Optimization 18: 264–281
Kough PF (1979) The indefinite quadratic programming problem. Operations Research 27: 516–533
Mattheis TH, Rubin DS (1980) A survey and comparison of methods for finding all vertices of convex polyhedrical sets. Mathematics of Operations Research 5: 167–185
Sherali HD, Shetty CM (1980) Optimization with Disjunctive Constraints. Springer, New York
Sherali HD, Shetty CM (1982) A finitely convergent procedure for facial disjunctive programs. Discrete Applied Mathematics 4: 135–148
Stoer J, Witzgall C (1970) Convexity and Optimization in Finite Dimensions. Springer, New York
Williams HP (1978) Model Building in Mathematical Programming, Wiley, New York
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Fülöp, J. A finite cutting plane method for facial disjunctive programs. ZOR - Methods and Models of Operations Research 35, 1–13 (1991). https://doi.org/10.1007/BF01415956
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01415956