×

zbMATH — the first resource for mathematics

An active set algorithm for robust combinatorial optimization based on separation oracles. (English) Zbl 07168040
Summary: We address combinatorial optimization problems with uncertain coefficients varying over ellipsoidal uncertainty sets. The robust counterpart of such a problem can be rewritten as a second-oder cone program (SOCP) with integrality constraints. We propose a branch-and-bound algorithm where dual bounds are computed by means of an active set algorithm. The latter is applied to the Lagrangian dual of the continuous relaxation, where the feasible set of the combinatorial problem is supposed to be given by a separation oracle. The method benefits from the closed form solution of the active set subproblems and from a smart update of pseudo-inverse matrices. We present numerical experiments on randomly generated instances and on instances from different combinatorial problems, including the shortest path and the traveling salesman problem, showing that our new algorithm consistently outperforms the state-of-the art mixed-integer SOCP solver of Gurobi.

MSC:
90C25 Convex programming
90C27 Combinatorial optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Atamtürk, A., Gómez, A.: Simplex QP-based methods for minimizing a conic quadratic objective over polyhedra. Math. Prog. Comp. (2018). https://doi.org/10.1007/s12532-018-0152-7 · Zbl 1435.90097
[2] Ben-Tal, A., Nemirovski, A.: Robust convex optimization. Math. Oper. Res. 23(4), 769-805 (1998) · Zbl 0977.90052
[3] Ben-Tal, A., Nemirovski, A.: Robust solutions of uncertain linear programs. Oper. Res. Lett. 25, 1-13 (1999) · Zbl 0941.90053
[4] Ben-Tal, A., Nemirovski, A.: Lectures on Modern Convex Optimization. SIAM, Philadelphia (2001) · Zbl 0986.90032
[5] Bertsimas, D., Popescu, I.: Optimal inequalities in probability theory: a convex optimization approach. SIAM J. Optim. 15, 780-804 (2005) · Zbl 1077.60020
[6] Buchheim, C., Kurtz, J.: Robust combinatorial optimization under convex and discrete cost uncertainty. Technical report, Optimization Online (2017) · Zbl 1417.90125
[7] Buchheim, C., De Santis, M., Lucidi, S., Rinaldi, F., Trieu, L.: A feasible active set method with reoptimization for convex quadratic mixed-integer programming. SIAM J. Optim. 26(3), 1695-1714 (2016) · Zbl 1346.90608
[8] Buchheim, C., De Santis, M., Rinaldi, F., Trieu, L.: A Frank-Wolfe based branch-and-bound algorithm for mean-risk optimization. J. Glob. Optim. 70(3), 625-644 (2018) · Zbl 1382.90057
[9] Dolan, E., Moré, J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201-213 (2002) · Zbl 1049.90004
[10] Gurobi Optimization, Inc.: Gurobi optimizer reference manual (2016)
[11] Kouvelis, P., Yu, G.: Robust Discrete Optimization and Its Applications. Springer, Dordrecht (1996) · Zbl 0873.90071
[12] Meyer Jr., C.D.: Generalized inversion of modified matrices. SIAM J. Appl. Math. 24(3), 315-323 (1973) · Zbl 0253.15001
[13] Meyer, C.D.: Matrix Analysis and Applied Linear Algebra. SIAM, Philadelphia (2000)
[14] Mittelmann, H.D.: Latest benchmark results—informs annual conference. http://plato.asu.edu/talks/informs2018.pdf. Accessed 4-7 November 2018
[15] MOSEK ApS: The MOSEK optimization toolbox for MATLAB manual. Version 8.0.0.81 (2017)
[16] Nesterov, Y., Nemirovski, A.: Interior-Point Polynomial Algorithms in Convex Programming. SIAM, Philadelphia (1993)
[17] Nikolova, E.: Approximation algorithms for offline risk-averse combinatorial optimization. Technical report (2010)
[18] Nocedal, J., Wright, S.: Numerical Optimization, 2nd edn. Springer-Verlag, New York (2006) · Zbl 1104.65059
[19] Sturm, J.F.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 11-12, 625-653 (1999). Version 1.05 available from http://fewcal.kub.nl/sturm · Zbl 0973.90526
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.