Last update: 02/11/2021 (the original page has been moved to the CommaLAB web site, although a redirect has been kept)
These are 90 random instances of the Mean-Variance (MV) problem with minimum buy-in constraints and cardinality, a Mixed-Integer Quadratic program used in [FrGe06, FrGe07, FrFG16, FrFG17, FRGH20, ZhSL14] to test some approaches based on the “Perspective Reformulation” (PR) to Mixed-Integer Quadratic Problems with specific structure (nonlinear semicontinuous variables). The instances are all contained in a single file (6.6Mb); please refer to the provided file README.txt and the cited references for further details.
To ease life, we now also directly provide .lp files of the instances, besides the raw data to produce them:
Applying PR techniques to MV, which has a convex non-separable quadratic objective with Positive-Semidefinite (SDP) Hessian Q, requires finding a diagonal non-negative matrix D such that Q – D is still SDP. Different ways for finding D, with different trade-offs between the required time and the quality of the corresponding lower bound, are proposed in [FrGe07] and [ZhSL14]. These require the solution of nontrivial SDP problems, in particular for [ZhSL14]. To facilitate reproducing our results, in particular those of [FrFG17], some pre-computed diagonals for the above instances are provided here. Please refer to the included READ_ME.txt file and the cited references for further details.
A possible approach to solve these problems is to first reformulate them with the Approximated Projected Perspective Reformulation technique [FrFG16] (after having extracted the diagonal, see above) prior to sending them to any MIQP solver. We now also provide .lp files of the instances after the reformulation, for all the three types of diagonal; check the readme for more details.
An improvement on the Approximated Projected Perspective Reformulation technique [FrFG17] uses dual information to further improve the bound. We provide the optimal dual values for each instance and diagonal, as well as the .lp files of the instances after the reformulation, for all the three types of diagonal. Check the readme for more details.
Bibliography
[FrGe06] A. Frangioni, C. Gentile “Perspective Cuts for a Class of Convex 0-1 Mixed Integer Programs” Mathematical Programming 106(2), 225—236, 2006
[FrGe07] A. Frangioni, C. Gentile “SDP Diagonalizations and Perspective Cuts for a Class of Nonseparable MIQP”, Operations Research Letters 35(2), 181—185, 2007
[FrFG16] A. Frangioni, F. Furini, C. Gentile “Approximated Perspective Relaxations: a Project&Lift Approach” Computational Optimization and Applications 63(3), 705—735, 2016
[FrFG17] A. Frangioni, F. Furini, C. Gentile “Improving the Approximated Projected Perspective Reformulation by Dual Information” Operations Research Letters 45, 519–524, 2017
[FrGH20] A. Frangioni, C. Gentile, J. Hungerford “Decompositions of Semidefinite Matrices and the Perspective Reformulation of Nonseparable Quadratic Programs” Mathematics of Operations Research 45(1), 15—33, 2020
[ZhSL14] X. Zheng, X. Sun, D. Li. “Improving the Performance of MIQP Solvers for Quadratic Programs with Cardinality and Minimum Threshold Constraints: A Semidefinite Program Approach” INFORMS Journal on Computing 26(4):690—703, 2014