Binary integer programs with two variables per inequality. (English) Zbl 0874.90138
Summary: Several recent papers have shown that some properties of the maximum weight stable set problem hold true in the more general setting of binary integer programs with two variables per inequality. In this paper, we show that in fact the two problems are equivalent by using the transitive closure of the binary integer program and (possibly) reducing the number of variables by fixing, complementing, or identifying them. We use this equivalence to prove two conjectures made by Johnson and Padberg regarding the perfection of bidirected graphs.
MSC:
| 90C10 | Integer programming |
References:
| [1] | J.M. Bourjolly, Integral and Fractional Node-Packings, and Pseudo-Boolean Programming, Ph.D. Thesis, University of Waterloo, Waterloo, Ontario (1986). |
| [2] | J.M. Bourjolly, An extension of the König-Egerváry property to node-weighted bidirected graphs.Mathematical Programming 41 (1988) 375–384. · Zbl 0653.90083 · doi:10.1007/BF01580775 |
| [3] | H. Crowder, E.L. Johnson and M. Padberg, Solving large-scale zero-one linear programming problems,Operations Research 31 (5) (1983) 803–834. · Zbl 0576.90065 · doi:10.1287/opre.31.5.803 |
| [4] | M. Guignard and K. Spielberg, Logical reduction methods in zero-one programming. Minimal preferred variables,Operations Research 29 (1) (1981) 49–74. · Zbl 0452.90044 · doi:10.1287/opre.29.1.49 |
| [5] | P.L. Hammer and S. Nguyen. A partial order in the solution space of bivalent programs, in: N. Christofides et al., eds.,Combinatorial Optimization (John Wiley and Sons, New York, 1979) 93–106. · Zbl 0414.90063 |
| [6] | P. Hansen, A cascade algorithm for the logical closure of a set of binary relations,Information Processing Letters 5 (2) (1976) 50–54. · Zbl 0327.90021 · doi:10.1016/0020-0190(76)90079-X |
| [7] | P. Hansen, B. Jaumard and M. Minoux, A linear expected-time algorithm for deriving all logical conclusions implied by a set of boolean inequalities.Mathematical Programming 34 (1986) 223–231. · Zbl 0596.90067 · doi:10.1007/BF01580586 |
| [8] | D.S. Hochbaum, N. Megiddo, J. Naor and A. Tamir, Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality, Technical report. University of California, Berkeley, CA (1992). · Zbl 0802.90080 |
| [9] | K.L. Hoffman and M. Padberg, Improving LP-representations of zero-one linear programs for branchand-cut,ORSA Journal on Computing 3 (2) (1991) 121–134. · Zbl 0755.90062 · doi:10.1287/ijoc.3.2.121 |
| [10] | E.L. Johnson and M.W. Padberg, Degree-two inequalities, clique facets, and biperfect graphs,Annals of Discrete Mathematics 16 (1982) 169–187. · Zbl 0523.52009 |
| [11] | G.L. Nemhauser and L.E. Trotter Jr., Vertex packings: Structural properties and algorithms,Mathematical Programming 8 (1975) 232–248. · Zbl 0314.90059 · doi:10.1007/BF01580444 |
| [12] | A. Tucker, Critical perfect graphs and perfect 3-chromatic graphs,Journal of Combinatorial Theory (Series B) 23 (1977) 143–149. · Zbl 0376.05047 · doi:10.1016/0095-8956(77)90064-8 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
