Conference Agenda

For a min-max robust optimization problem with a discrete uncertainty set, a well-known heuristic is to optimize a nominal problem with the average-case scenario. If there uncertainty set contains K scenarios, this approach results in a K-approximate solution. It is equivalent to optimizing the 1-norm of the K-dimensional vector that contains the objective value in each scenario. If we use other p-norms, it is possible to achieve better guarantees that improve when the value of p increases. By using an approximation method for some such p-norm problems, it is possible to achieve approximation guarantees that are logarithmic in K. We also point out how to extend this approach to the more general OWA decision criterion with non-increasing weights, resulting in an approximation guarantee that is in O(log K / w_1) for matroidal problems.

A standard type of uncertainty set in robust optimization is budgeted uncertainty, where an interval of possible values for each parameter is given and the total deviation from their lower bounds is bounded. In the two-stage setting, discrete and continuous budgeted uncertainty have to be distinguished. While two-stage robust selection problems with discrete budgeted uncertainty have been shown to be NP-hard, the complexity of the corresponding problems with continuous budgeted uncertainty has still been open. Only for an alternative version of continuous budgeted uncertainty, where the total absolute deviation of all parameters is bounded instead of the sum of all relative deviations, the two-stage robust selection problem has been shown to be solvable in polynomial time. We close a gap in the knowledge about the complexity of these problems by showing that the two-stage robust representative selection problem with the more common version of continuous budgeted uncertainty is solvable in polynomial time. After applying standard dualization techniques to reformulate the problem as a mixed-integer linear program, we present a combinatorial algorithm to solve the latter.

Consider a binary integer program (BIP) under budgeted objective uncertainty, i.e. the cost of a given number of objective coefficients may deviate within an interval.

The objective of such a BIP consists of a linear nominal and a non-linear robust part. The robust part can be restated as a submodular set function, where the set corresponds to the non-zero solution variables. This set function defines a polymatroid Π.

Using results by Bertsimas and Sim, the BIP can also be reformulated into a mixed integer linear program, with a linear objective function that again consists of a robust and a nominal part.

The nominal parts of the objective functions are identical. Comparing the robust part of the objective functions, it can be shown that the linear robust objective function part is larger than any solution vector x multiplied with a coefficient vector π from the polymatroid Π. Thus, we can derive valid inequalities for any (fractional) solution vector x. The strongest such inequalities are those that maximise πx. Since Π is a polymatroid, we can greedily compute a coefficient vector π from the polymatroid Π that maximises πx using results from Joung and Park (2021), based on work from Edmonds.

In practice, we only need to consider those constraints on the polymatroid that correspond to feasible solutions of the original binary integer program. In this talk, we present ongoing research on to what extent this can be included in the polymatroid optimisation problem to speed computations by strengthening the valid inequalities.