`a`
Numerical Algebra, Control and Optimization (NACO)
 

Analyzing the computational impact of MIQCP solver components

Pages: 739 - 748, Volume 2, Issue 4, December 2012      doi:10.3934/naco.2012.2.739

 
       Abstract        References        Full Text (176.8K)       Related Articles       

Timo Berthold - Zuse Institute Berlin, Takustr. 7, 14195 Berlin, Germany (email)
Ambros M. Gleixner - Zuse Institute Berlin, Takustr. 7, 14195 Berlin, Germany (email)
Stefan Heinz - Zuse Institute Berlin, Takustr. 7, 14195 Berlin, Germany (email)
Stefan Vigerske - Humboldt-Universit├Ąt, Department of Mathematics, Unter den Linden 6, 10099 Berlin, Germany (email)

Abstract: We provide a computational study of the performance of a state-of-the-art solver for nonconvex mixed-integer quadratically constrained programs (MIQCPs). Since successful general-purpose solvers for large problem classes necessarily comprise a variety of algorithmic techniques, we focus especially on the impact of the individual solver components. The solver SCIP used for the experiments implements a branch-and-cut algorithm based on a linear relaxation to solve MIQCPs to global optimality. Our analysis is based on a set of 86~publicly available test instances.

Keywords:  Mixed-integer quadratically constrained programming, mixed-integer programming, branch-and-cut, nonconvex, global optimization, software engineering.
Mathematics Subject Classification:  Primary: 90C11, Secondary: 90C26, 90C30.

Received: May 2012;      Revised: October 2012;      Available Online: November 2012.

 References