Generating hard instances for robust combinatorial optimization
From MaRDI portal
Publication:2272296
Abstract: While research in robust optimization has attracted considerable interest over the last decades, its algorithmic development has been hindered by several factors. One of them is a missing set of benchmark instances that make algorithm performance better comparable, and makes reproducing instances unnecessary. Such a benchmark set should contain hard instances in particular, but so far, the standard approach to produce instances has been to sample values randomly from a uniform distribution. In this paper we introduce a new method to produce hard instances for min-max combinatorial optimization problems, which is based on an optimization model itself. Our approach does not make any assumptions on the problem structure and can thus be applied to any combinatorial problem. Using the Selection and Traveling Salesman problems as examples, we show that it is possible to produce instances which are up to 500 times harder to solve for a mixed-integer programming solver than the current state-of-the-art instances.
Recommendations
- Generating and measuring instances of hard semidefinite programs
- Measuring instance difficulty for combinatorial optimization problems
- scientific article; zbMATH DE number 2196508
- scientific article; zbMATH DE number 764410
- Random constraint satisfaction: easy generation of hard (satisfiable) instances
- Generating hard test instances with known optimal solution for the rectilinear quadratic assignment problem
- Bulk-robust combinatorial optimization
- On the robustness of optimal solutions for combinatorial optimization problems
- Representative scenario construction and preprocessing for robust combinatorial optimization problems
- scientific article; zbMATH DE number 1256724
Cites work
- A new bound for the midpoint solution in minmax regret optimization with an application to the robust shortest path problem
- Adjustable robust solutions of uncertain linear programs
- Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints
- Exact and heuristic algorithms for the interval data robust assignment problem
- scientific article; zbMATH DE number 5610761 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- Min-max and min-max regret versions of combinatorial optimization problems: A survey
- Min-max-min robust combinatorial optimization
- On scenario aggregation to approximate robust combinatorial optimization problems
- Reduction approaches for robust shortest path problems
- Representative scenario construction and preprocessing for robust combinatorial optimization problems
- Robust discrete optimization and its applications
- The polynomial-time hierarchy
- Where are the hard knapsack problems?
Cited in
(4)
This page was built for publication: Generating hard instances for robust combinatorial optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2272296)
