×

Expressing combinatorial optimization problems by linear programs. (English) Zbl 0748.90074

The \({\mathcal P}={\mathcal NP}\) problem is investigated. The known \(\mathcal NP\)- complete problems can be formulated as an optimization of a linear function over a convex hull of feasible solutions of the problem. Such a representation does not provide an advantage because of the exponential size of the obtained linear program (LP). The paper aims at analysing the possibility to reduce the size of the LP. Adding new variables the author proposes to transform a polytope of the LP to a specific form, named symmetric. Roughly, it is a polytope that remains “invariant” under any permutation of the initial variables. The main result is that the travelling salesman problem and the matching problem cannot be expressed by any symmetric LP with a size less than exponential.

MSC:

90C35 Programming involving graphs or networks
52B12 Special polytopes (linear programming, centrally symmetric, etc.)
90C60 Abstract computational complexity for mathematical programming problems
90C27 Combinatorial optimization
90C05 Linear programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0286.68029
[2] Aho, A. V.; Ullman, J. D.; Yannakakis, M., On notions of information transfer in VLSI circuits, (Proceedings, 15th Annual ACM Symp. on Theory of Computing (1983)), 133-139
[3] Berge, C.; Chvatal, V., Topics on Perfect Graphs, (Annals of Discrete Math., Vol. 21 (1984), North-Holland: North-Holland Amsterdam) · Zbl 0546.00006
[4] Balas, E.; Pulleyblank, W., The perfectly matchable subgraph polytope of a bipartite graph, Networks, 13, 486-516 (1983) · Zbl 0525.90069
[5] Dobkin, D.; Lipton, R. J.; Reiss, S., Linear programming is log-space hard for P, Inform. Process. Lett., 8, 96-97 (1979) · Zbl 0402.68042
[6] Edmonds, J., Maximum matching and a polyhedron with 0, 1 vertices, J. Res. Nat. Bur. Standards B, 69, 125-130 (1965) · Zbl 0141.21802
[7] Garey, M. R.; Johson, D. S.; Stockmeyer, L., Some simplified NP-complete graph problems, Theoret. Comput. Sci., 1, 237-267 (1976) · Zbl 0338.05120
[8] Golumbic, M., Algorithmic Graph Theory and Perfect Graphs (1900), Academic Press: Academic Press New York/London
[9] Grotschel, M.; Lovasz, L.; Schruver, A., The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1, 169-197 (1981) · Zbl 0492.90056
[10] Grotchel, M.; Padberg, M. W., Polyhedral theory, and polyhedral computations, (Lawler, E. L.; etal., The Traveling Salesman Problem (1985), Wiley: Wiley New York), 251-360
[11] Jeroslow, R. G., On defining sets of vertices of the hypercube by linear inequalities, Discrete Math., 11, 119-124 (1975) · Zbl 0297.52009
[12] D. S. Johnson, personal communication.; D. S. Johnson, personal communication.
[13] Karmakar, N., A new polynomial time algorithm for linear programming, Combinatorica, 4, 373-395 (1984) · Zbl 0557.90065
[14] Khachian, L. G., Soviet Math. Doki., 20, 191-194 (1979), English translation · Zbl 0409.90079
[15] Lovasz, L., Vertex packing algorithms, (Proceedings, Int. Colloq. Automata, Languages and Programming (1985), Springer-Verlag: Springer-Verlag New York/Berlin), 1-14
[16] Martin, R. K., Using Separation Algorithms to Generate Mixed Integer Model Reformulations (1987), Graduate School of Business, University of Chicago, working paper
[17] Martin, R. K.; Rardin, R. L.; Campbell, B. A., Polyhedral Characterization of Discrete Dynamic Programming, (Technical Report CC-87-24 (1987), Purdue University) · Zbl 0711.90066
[18] Melhorn, K.; Schmidt, E. M., Las Vegas is better than determinism in VLSI and distributed computing, (Proceedings, 14th Annual ACM Symp. on Theory of Computing (1982)), 330-337
[19] Padberg, M.; Rao, M. R., Odd minimum cut-sets and b-matchings, Math. Oper. Res., 7, 67-80 (1982) · Zbl 0499.90056
[20] Padberg, M.; Rinaldi, G., Optimization of a 532-city symmetric traveling salesman problem by Branch and cut, Oper. Res. Lett., 6, 1-7 (1987) · Zbl 0618.90082
[21] Papadimitriou, C. H.; Sipser, M., Communication complexity, (Proceedings, 14th ACM Symp. on Theory of Computing (1982)), 196-200
[22] Papadimitriou, C. H.; Wolfe, D., The complexity of facets resolved, (Proceedings, 26th Annual IEEE Symp. on Foundations of Computer Science (1985)), 74-78
[23] Papadimitriou, C. H.; Yannakakis, M., The complexity of facets (and some facets of complexity), J. Comput. System Sci., 28, 144-259 (1984) · Zbl 0571.68028
[24] Razborov, A. A., A lower bound on the monotone network complexity of the logical permanent, Math. Notes, 37, 485-493 (1985) · Zbl 0584.94026
[25] Schruver, A., Theory of Linear and Integer Programming (1986), New York
[26] Swart, E. R., (“P=NP,” Technical Report (1987), University of Guelph), revision
[27] Valiant, L. G., Reducibility by algebraic projections, Enseign. Math., 28, 253-268 (1982) · Zbl 0493.68045
[28] Wielandt, H., Finite Permutation Groups (1964), Academic Press: Academic Press New York/London · Zbl 0138.02501
[29] Yao, A. C., Some complexity questions related to distributive computing, (Proceedings, 11th Annual ACM Symp. on Theory of Computing (1979)), 209-213
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.