Sensitivity Analysis for Mixed Binary Quadratic Programming
Pages 446 - 459
Abstract
We consider sensitivity analysis for Mixed Binary Quadratic Programs (MBQPs) with respect to changing right-hand-sides (rhs). We show that even if the optimal solution of a given MBQP is known, it is NP-hard to approximate the change in objective function value with respect to changes in rhs. Next, we study algorithmic approaches to obtaining dual bounds for MBQP with changing rhs. We leverage Burer’s completely-positive (CPP) reformulation of MBQPs. Its dual is an instance of co-positive programming (COP), and can be used to obtain sensitivity bounds. We prove that strong duality between the CPP and COP problems holds if the feasible region is bounded or if the objective function is convex, while the duality gap can be strictly positive if neither condition is met. We also show that the COP dual has multiple optimal solutions, and the choice of the dual solution affects the quality of the bounds with rhs changes. We finally provide a method for finding good nearly optimal dual solutions, and we present preliminary computational results on sensitivity analysis for MBQPs.
References
[1]
Anstreicher, K.M.: Testing copositivity via mixed-integer linear programming. Linear Algebra Appl. 609, 218–230 (2021). https://www.sciencedirect.com/science/article/pii/S0024379520304171
[2]
Badenbroek R and de Klerk E An analytic center cutting plane method to determine complete positivity of a matrix INFORMS J. Comput. 2022 34 2 1115-1125
[3]
Bomze IM and De Klerk E Solving standard quadratic optimization problems via linear, semidefinite and copositive programming J. Glob. Optim. 2002 24 163-185
[4]
Brown, R., Neira, D.E.B., Venturelli, D., Pavone, M.: Copositive programming for mixed-binary quadratic optimization via Ising solvers. arXiv preprint arXiv:2207.13630 (2022)
[5]
Burer S On the copositive representation of binary and continuous nonconvex quadratic programs Math. Program. 2009 120 2 479-495
[6]
Burer S and Dong H Representing quadratically constrained quadratic programs as generalized copositive programs Oper. Res. Lett. 2012 40 3 203-206
[7]
Celaya M, Kuhlmann S, Paat J, and Weismantel R Aardal K and Sanitá L Improving the Cook et al. proximity bound given integral valued constraints Integer Programming and Combinatorial Optimization 2022 Cham Springer 84-97
[8]
Conforti M, Cornuéjols G, and Zambelli G Conforti M, Cornuéjols G, and Zambelli G Integer programming models Integer Programming 2014 Cham Springer Springer 45-84
[9]
Cook W, Gerards AMH, Schrijver A, and Tardos É Sensitivity theorems in integer linear programming Math. Program. 1986 34 3 251-264
[10]
Del Pia A and Ma M Proximity in concave integer quadratic programming Math. Program. 2022 194 1–2 871-900
[11]
Eisenbrand F and Weismantel R Proximity results and faster algorithms for integer programming using the Steinitz lemma ACM Trans. Algorithms (TALG) 2019 16 1 1-14
[12]
Feizollahi MJ, Ahmed S, and Sun A Exact augmented Lagrangian duality for mixed integer linear programming Math. Program. 2017 161 365-387
[13]
Granot F and Skorin-Kapov J Some proximity and sensitivity results in quadratic integer programming Math. Program. 1990 47 1–3 259-268
[14]
Gu X, Ahmed S, and Dey SS Exact augmented Lagrangian duality for mixed integer quadratic programming SIAM J. Optim. 2020 30 1 781-797
[15]
Gu, X., Dey, S.S., Xavier, Á.S., Qiu, F.: Exploiting instance and variable similarity to improve learning-enhanced branching. arXiv preprint arXiv:2208.10028 (2022)
[16]
Guo, C., Bodur, M., Taylor, J.A.: Copositive duality for discrete energy markets (2021)
[17]
Johnson, E.S., Ahmed, S., Dey, S.S., Watson, J.P.: A K-nearest neighbor heuristic for real-time DC optimal transmission switching. arXiv preprint arXiv:2003.10565 (2020)
[18]
Kim, S., Kojima, M.: Strong duality of a conic optimization problem with a single hyperplane and two cone constraints. arXiv preprint arXiv:2111.03251 (2021)
[19]
Lee J, Paat J, Stallknecht I, and Xu L Baïou M, Gendron B, Günlük O, and Mahjoub AR Improving proximity bounds using sparsity Combinatorial Optimization 2020 Cham Springer 115-127
[20]
Linderoth, J., Raghunathan, A.: Completely positive reformulations and cutting plane algorithms for mixed integer quadratic programs. INFORMS Annual Meeting (2022)
[21]
Majumdar A, Hall G, and Ahmadi AA Recent scalability improvements for semidefinite programming with applications in machine learning, control, and robotics Ann. Rev. Control Robot. Auton. Syst. 2020 3 331-360
[22]
Nemhauser GL and Wolsey LA Integer and Combinatorial Optimization 1999 Hoboken Wiley
[23]
Shahidehpour M, Yamin H, and Li Z Market Operations in Electric Power Systems: Forecasting, Scheduling, and Risk Management 2003 Hoboken Wiley
[24]
Vavasis, S.A.: Quadratic programming is in NP. Inf. Process. Lett. 36(2), 73–77 (1990). https://www.sciencedirect.com/science/article/pii/002001909090100C
[25]
Xavier ÁS, Qiu F, and Ahmed S Learning to solve large-scale security-constrained unit commitment problems INFORMS J. Comput. 2021 33 2 739-756
Recommendations
Mixed-integer quadratic programming
This paper considers mixed-integer quadratic programs in which the objective function is quadratic in the integer and in the continuous variables, and the constraints are linear in the variables of both types. The generalized Benders' decomposition is a ...
Robust sensitivity analysis of the optimal value of linear programming
We propose a framework for sensitivity analysis SA of linear programs LPs in minimization form, allowing for simultaneous perturbations in the objective coefficients and right-hand sides, where the perturbations are modelled in a compact, convex, and ...
Robust Quadratic Programming with Mixed-Integer Uncertainty
We study robust convex quadratic programs where the uncertain problem parameters can contain both continuous and integer components. Under the natural boundedness assumption on the uncertainty set, we show that the generic problems are amenable to exact ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Jul 2024
473 pages
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 03 July 2024
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 19 Feb 2025