Abstract
Recent work has demonstrated the potential for globally optimizing nonconvex quadratic programs using a reformulation based on the first order optimality conditions. We show how this reformulation may be generalized to account for fixed cost variables. We then extend some of the polyhedral work that has been done for bound constrained QPs to handle such fixed cost variables. We show how to lift known classes of inequalities for the case without fixed cost variables and propose several new classes. These inequalities are incorporated in a branch-and-cut algorithm.
Similar content being viewed by others
References
Aardal K. (1998). Capacitated facility location: separation algorithms and computational experience. Math. Program. 81(2, Ser. B): 149–175
Atamtürk A. (2001). Flow pack facets of the single node fixed-charge flow polytope. Oper. Res. Lett. 29(3): 107–114
Balas E. (1975). Nonconvex quadratic programming via generalized polars. SIAM J. Appl. Math. 28: 335–349
Barany I., Van Roy T.J. and Wolsey L.A. (1984). Strong formulations for multi-item capacitated lotsizing. Manage. Sci. 30: 1255–1261
Bomze I.M. and Danninger G. (1994). A finite algorithm for solving general quadratic problems. GOP 4: 1–16
Christof, T., Löbel, A.: PORTA: a polyhedron representation transformation algorithm.http://www.zib.de/Optimization/Software/Porta/ (1997)
Crowder H., Johnson E.L. and Padberg M.W. (1983). Solving large scale zero-one integer programming problems. Oper. Res. 31: 803–834
Johnson E.L. and Nemhauser G.L. (2002). Facets of the complementarity knapsack polytope. Math. Oper. Res. 27: 210–226
Giannessi, F., Tomasin, E.: Nonconvex quadratic programs, linear complementarity problems, and integer linear programs. In: Proceeding of the 5th Conference on Optimization Techniques (Rome, 1973), Part I. Lecture Notes in Computer Science, vol. 3, pp. 437–449. Springer, Berlin (1973)
Grossmann, I.E., Kravanja, Z.: Mixed-integer nonlinear programming: a survey of algorithms and applications. In: Biegler, L.T., Coleman, T.F., Conn, A.R., Santosa, F.N. (eds.) Large-scale optimization with applications, Part II (Minneapolis, MN, 1995), vol. 93 of IMA Vol. Math. Appl., pp. 73–100. Springer, New York (1997)
Gu Z., Nemhauser G.L. and Savelsbergh M.W.P. (1999). Lifted flow cover inequalities for mixed 0-1 integer programs. Math. Program. 85(3, Ser. A): 439–467
Hansen P., Jaumard B., Ruiz M. and Xiong J. (1993). Global minimization of indefinite quadratic functions subject to box constraints. Nav. Res. Logist. 40: 373–392
Huang H., Pardalos P.M. and Prokopyev O.A. (2006). Lower bound improvement and forcing rule for quadratic binary programming. Comput. Optim. Appl. 33(2–3): 187–208
ILOG, Inc. ILOG CPLEX 9.0, User Manual (2003)
Lin, T.C., Vandenbussche, D.: Box-constrained quadratic programs with fixed charge variables. Technical report, Department of Mechanical and Industrial Engineering, University of Illinois Urbana-Champaign. https://netfiles.uiuc.edu/dieterv/www/publications.html. (2006)
Motzkin T.S. and Straus E.G. (1965). Maxima for graphs and a new proof of a theorem of Turán. Can. J. Math. 17: 533–540
Nemhauser G.L., Savelsbergh M.W.P. and Sigismondi G.S. (1994). MINTO, a mixed INTeger optimizer. Oper. Res. Lett. 15: 47–58
Nowak I. (2000). Dual bounds and optimality cuts for all-quadratic programs with convex constraints. J. Glob. Optim. 18(4): 337–356
Padberg M. (1989). The Boolean quadric polytope: some characteristics, facets and relatives. Math. Program. 45: 139–172
Padberg M.W., Van Roy T.J. and Wolsey L.A. (1985). Valid linear inequalities for fixed charge problems. Oper. Res. 33: 842–861
Pardalos P.M. and Rodgers G.P. (1990a). Computational aspects of a branch and bound algorithm for quadratic zero-one programming. Computing 45(2): 131–144
Pardalos P.M. and Rodgers G.P. (1990b). Parallel branch and bound algorithms for quadratic zero-one programs on the hypercube architecture. Ann. Oper. Res. 22(1–4): 271–292
Pardalos P.M., Chaovalitwongse W., Iasemidis L.D., Sackellares C.J., Shiau D., Carney P.R., Prokopyev O.A. and Yatsenko V.A. (2004). Seizure warning algorithm based on optimization and nonlinear dynamics. Math. Program. 101(2, Ser. B): 365–385
Phillips A.T. and Rosen J.B. (1990). Guaranteed ε-approximate solution for indefinite quadratic global minimization. Nav. Res. Logist. 37(4): 499–514
Revelle C. (1999). Optimizing Reservoir Resources. Wiley, New York
Rosenberg I.G. (1972). 0-1 optimization and nonlinear programming. Rev. Fr. Autom. Inf. Rech. Opérationnelle 6: 95–97
Sahinidis N.V. (1996). BARON: a general purpose global optimization software package. J. Glob. Optim. 8: 201–205
Sahinidis, N.V., Tawarmalani, M.: BARON 7.5: global optimization of mixed-integer nonlinear programs, User’s Manual. Available at http://www.gams.com/dd/docs/solvers/baron.pdf. (2006)
Sherali H.D. and Tuncbilek C.H. (1995). A reformulation-convexification approach for solving nonconvex quadratic programming problems. J. Glob. Optim. 7: 1–31
Vandenbussche D. and Nemhauser G. (2005a). A polyhedral study of nonconvex quadratic programs with box constraints. Math. Program. 102(3): 531–557
Vandenbussche D. and Nemhauser G. (2005b). A branch-and-cut algorithm for nonconvex quadratic programs with box constraints. Math. Program. 102(3): 559–575
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Lin, TC., Vandenbussche, D. Box-constrained quadratic programs with fixed charge variables. J Glob Optim 41, 75–102 (2008). https://doi.org/10.1007/s10898-007-9167-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-007-9167-8