Discrete optimization (also called combinatorial optimization) deals with optimization problems where decision variables are integers. An instance of a discrete optimization problem is specified by exact values of parameters within its objective function and its constraints. In real-world situations parameter values are often hard to determine since they may depend on unpredictable future circumstances or perhaps cannot be measured accurately. Then we speak about uncertainty in problem formulation.
The traditional approach to optimization tends to ignore uncertainty. It means that parameters are very often given approximate, unreliable or ad-hoc values, which can lead to inferior or even infeasible solutions. A state-of-the-art approach to address the mentioned uncertainty is called robust optimization. It works in the following way. A set of scenarios is defined - each of them specifies a possible combination of parameter values. Only those solutions are considered that are feasible for all scenarios. The “behaviour” of any solution under any scenario is measured in some way. For each solution, its worst behaviour over the whole set of scenarios is recorded. As the optimal solution in the robust sense, the one is chosen whose recorded worst behaviour happens to be the best among all solutions.
A consequence of using the robust approach is that the initial optimization problem transforms into a more complex min-max or max-min problem. The robust solution does not need to be really optimal for any scenario, but it is chosen in order to be acceptable even within the worst scenario. Although conventional (non-robust) variants of some discrete optimization problems can be solved efficiently by polynomial-time algorithms, robust variants of the same problems are usually NP-hard. Consequently, finding efficient algorithms for robust variants is a challenging and important research topic. At this moment, there are not many algorithms for robust optimization found in literature that can be regarded as efficient and suitable for real-world situations.
The aim of this project is to demonstrate that robust discrete optimization problems can be solved efficiently although they are NP-hard. More precisely, the aim is to develop efficient and practically relevant algorithms for robust variants of the following types of problems: optimal paths in graphs, optimal flows in networks, maximum weighted independent sets, traveling salesman and similar problems. Variants will be considered where the set of scenarios is finite and given explicitly. Emphasis will be put on heuristic or meta-heuristic solutions rather than on exact solutions.
Each algorithm produced by this project will be analysed in terms of correctness, accuracy and time complexity. Also, the algorithms will be implemented in software, evaluated on large benchmark problem instances and made available over a web repository to other researchers. All obtained results will be documented in research papers and published in appropriate journals. It is also expected that the youngest team member will complete her doctoral thesis.
