Optimization Online


An Active Set Algorithm for Robust Combinatorial Optimization Based on Separation Oracles

Christoph Buchheim(christoph.buchheim***at***math.tu-dortmund.de)
Marianna De Santis(mdesantis***at***diag.uniroma1.it)

Abstract: 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.

Keywords: Robust Optimization, Active Set Methods, SOCP

Category 1: Robust Optimization

Category 2: Combinatorial Optimization

Category 3: Global Optimization


Download: [PDF]

Entry Submitted: 04/04/2018
Entry Accepted: 04/04/2018
Entry Last Modified: 04/04/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society