A unified approach to polynomially solvable cases of integer “non-separable” quadratic optimization. (English) Zbl 0839.90086
Summary: D. S. Hochbaum and J. G. Shanthikumar [J. Assoc. Comput Mach. 37, No. 4, 843-862 (1990; Zbl 0721.90060)] presented in a recent paper “a general-purpose algorithm for converting procedures that solve linear programming problems with…integer variables, to procedures for solving…separable [nonlinear] problems”. Their work showed that “convex separable optimization is not much harder than linear optimization”. In contrast, polynomial algorithms in the literature for “non-separable” integer quadratic problems use qualitatively different techniques. By linearly transforming these problems so that the objective is separable in the transformed reference frame, we provide alternative algorithms for these problems based on Hochbaum and Shanthikumar’s algorithms. Inter alia we introduce a new class of polynomially solvable integer quadratic optimization problems. We also show that a slight generalization of integer linear programming having a non-separable, nonlinear objective and totally unimodular constraints is NP-hard.
MSC:
| 90C10 | Integer programming |
| 90C20 | Quadratic programming |
| 68Q25 | Analysis of algorithms and problem complexity |
Citations:
Zbl 0721.90060References:
| [1] | Baidick, R., Coordination of distribution system capacitors and regulators: an application of integer quadratic optimization, (Leondes, C. T., Control and Dynamic Systems. Control and Dynamic Systems, Analysis and Control System Techniques for Electric Power Systems, Vol. 42 (1991), Academic Press: Academic Press San Diego), 245-291 · Zbl 0729.00024 |
| [2] | R. Baidick, Refined proximity and sensitivity results in linearly-constrained convex separable integer programming, Linear Algebra Appl., to appear.; R. Baidick, Refined proximity and sensitivity results in linearly-constrained convex separable integer programming, Linear Algebra Appl., to appear. · Zbl 0838.90083 |
| [3] | Baldick, R., Generalization of Barahona’s algorithm for cases of integer non-linear programming with box constraints, Oper. Res. Lett., 13, 99-105 (1993) · Zbl 0776.90058 |
| [4] | Baldick, R.; Wu, F. F., Efficient integer optimization algorithms for optimal coordination of capacitors and regulators, IEEE Trans. Power Systems, 5, 805-812 (1990) |
| [5] | Barahona, F., A solvable case of quadratic 0-1 programming, Discrete Appl. Math., 13, 23-26 (1986) · Zbl 0597.90059 |
| [6] | Brylawski, T., Modular construction for combinatorial geometries, Trans. Amer. Math. Soc., 203, 1-44 (1975) · Zbl 0299.05023 |
| [7] | Fischer, K. H.; Hertz, J. A., Spin Glasses (1991), Cambridge University Press: Cambridge University Press Cambridge |
| [8] | Garey, M. R.; Johnson, D. S., (Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman: W.H. Freeman San Francisco, CA) · Zbl 0411.68039 |
| [9] | Gill, P. E.; Murray, W.; Wright, M. H., Numerical Linear Algebra and Optimization (1991), Addison-Wesley: Addison-Wesley Redwood City, CA · Zbl 0714.65063 |
| [10] | Granot, F.; Skorin-Kapov, J., Some proximity and sensitivity results in quadratic integer programming, Math. Programming, 47, 259-268 (1990) · Zbl 0714.90073 |
| [11] | Granot, F.; Skorin-Kapov, J., On polynomial solvability of the high multiplicity total weighted tardiness problem, Discrete Appl. Math., 41, 139-146 (1993) · Zbl 0779.90041 |
| [12] | Grötschel, M.; Lovász, L.; Schrijver, A., Geometric Algorithms and Combinatorial Optimization (1988), Springer: Springer Berlin · Zbl 0634.05001 |
| [13] | Hammer, P. L.; Rubin, A. A., Some remarks on quadratic programming with 0-1 variables, Rev. Française Inform. Rech. Opér 4, V-3, 67-79 (1970) · Zbl 0211.52104 |
| [14] | Hammer(Ivǎnescu), P. L.; Rudeanu, S., Boolean Methods in Operations Research and Related Areas (1968), Springer: Springer Berlin · Zbl 0155.28001 |
| [15] | Hansen, P.; Simeone, B., Unimodular functions, Discrete Appl. Math., 14, 269-281 (1986) · Zbl 0597.90058 |
| [16] | Hochbaum, D. S., On a polynomial class of nonlinear optimization problems, Manuscript, ((August 1989), School of Business Administration and Industrial Engineering and Operations Research, University of California: School of Business Administration and Industrial Engineering and Operations Research, University of California Berkeley, CA), revised |
| [17] | Hochbaum, D. S.; Shamir, R.; Shanthikumar, J. G., A polynomial algorithm for an integer quadratic non-separable transportation problem, Math. Programming, 55, 359-371 (1992) · Zbl 0761.90061 |
| [18] | Hochbaum, D. S.; Shanthikumar, J. G., Convex separable optimization is not much harder than linear optimization, J. ACM, 37, 843-862 (1990) · Zbl 0721.90060 |
| [19] | Johnson, E. L.; Padberg, M. W., Degree-two inequalities, clique facets, and biperfect graphs, Ann. Discrete Math., 16, 169-187 (1982) · Zbl 0523.52009 |
| [20] | Munkres, J. R., Topology: A First Course (1975), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0306.54001 |
| [21] | Nemhauser, G. L.; Wolsey, L. A., Integer and Combinatorial Optimization (1988), Wiley: Wiley New York · Zbl 0469.90052 |
| [22] | Picard, J. C.; Queyranne, M., Selected applications of minimum cuts in networks, INFOR, 20, 394-422 (1982) · Zbl 0501.90069 |
| [23] | Picard, J. C.; Ratliff, H. D., A graph-theoretic equivalence for integer programs, Oper. Res., 21, 261-269 (1973) · Zbl 0263.90021 |
| [24] | Picard, J. C.; Ratliff, H. D., Minimum cuts and related problems, Networks, 5, 357-370 (1975) · Zbl 0325.90047 |
| [25] | Welsh, D. J.A., Matroid Theory (1976), Academic Press: Academic Press London · Zbl 0343.05002 |
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.
