Dynamically generated cutting planes for mixed-integer quadratically constrained quadratic programs and their incorporation into GloMIQO 2
Author(s)
Misener, Ruth
Smadbeck, James B
Floudas, Christodoulos A
Type
Journal Article
Abstract
The global mixed-integer quadratic optimizer, GloMIQO, addresses mixed-integer quadratically constrained quadratic programs (MIQCQP) to ε-global optimality. This paper documents the branch-and-cut framework integrated into GloMIQO 2. Cutting planes are derived from reformulation–linearization technique equations, convex multivariable terms, αBB convexifications, and low- and high-dimensional edge-concave aggregations. Cuts are based on both individual equations and collections of nonlinear terms in MIQCQP. Novel contributions of this paper include: development of a corollary to Crama's [Concave extensions for nonlinear 0-1 maximization problems, Math. Program. 61 (1993), pp. 53–60] necessary and sufficient condition for the existence of a cut dominating the termwise relaxation of a bilinear expression; algorithmic descriptions for deriving each class of cut; presentation of a branch-and-cut framework integrating the cuts. Computational results are presented along with comparison of the GloMIQO 2 performance to several state-of-the-art solvers.
Date Issued
2015-02-01
Date Acceptance
2014-04-14
Citation
Optimization Methods and Software, 2015, 30 (1), pp.215-249
ISSN
1029-4937
Publisher
Taylor and Francis
Start Page
215
End Page
249
Journal / Book Title
Optimization Methods and Software
Volume
30
Issue
1
Copyright Statement
© 2014 Taylor & Francis. This is an Accepted Manuscript of an article published by Taylor & Francis in Optimization Methods and Software on 21 May 2014, available online: http://wwww.tandfonline.com/10.1080/10556788.2014.916287
Description
14.05.15 KB. Ok to add accepted version to spiral, subject to 12 months embargo
Identifier
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000345371800009&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=1ba7043ffcc86c417c072aa74d649202
Subjects
Science & Technology
Technology
Physical Sciences
Computer Science, Software Engineering
Operations Research & Management Science
Mathematics, Applied
Computer Science
Mathematics
quadratically constrained quadratic programming
cutting planes
global optimization
GLOBAL OPTIMIZATION METHOD
MAXIMUM CLIQUE PROBLEM
WATER NETWORKS
ALPHA-BB
MULTILINEAR FUNCTIONS
INVENTORY MANAGEMENT
OPERATIONS-RESEARCH
CONVEX RELAXATIONS
ASSIGNMENT PROBLEM
BOX CONSTRAINTS
Publication Status
Published
Date Publish Online
2014-04-22