Nested Solution Sequences for Parameterized Problems


Computational Complexity and Optimality Gaps for Nested Solution Sequences in Parameterized Optimization Problems

Many combinatorial optimization problems can be formulated as an integer program whose linear programming relaxation can be used as a bound on the optimal solution value. For example, think about the knapsack problem whose input consists of a knapsack capacity and a set of elements, each associated with a profit and weight. The goal in this problem is to select a subset of the elements at maximum profit which does not exceed the capacity. This problem can also be viewed parameterized by the capacity B. Depending on the capacity value, the optimum solution to the knapsack instance may look different. A solution x is called nested into a solution y if all elements which are present in x are also present in y. Intuitively, a nested solution can be grown over time: As the capacity grows, the solution grows with it. Such solutions can be beneficial in large investment decisions which are implemented over a larger time period.

In this project, we are interested in characterizations of problems such that there exist nested optimum solution sequences for all parameterized values simultaneously. Intuitively, a problem formulation behaves nicely if an optimum solution for larger capacity can be formed from an optimum solution for smaller capacity without revoking decisions. Under certain conditions, a formulation has this property, see for example results due to Topkis [2]. In practical applications, these conditions do not necessarily hold. Hence, we are also interested in conditions which ensure the existence of nested solution sequences whose objective function value is not too bad when compared pointwise to optimum solutions for each capacity value individually. And if such sequences exist, the question of computational tractability arises as well.

Besides our interest from a theoretical point of view, this problem has applications in open pit mine production scheduling [1]. Here, the problem formulation can be viewed as the intersection of a small constant number of knapsack constraints (usually 2 - 5) and a set of precedence constraints on the set of elements.

  • [1] D. Bienstock and M. Zuckerberg. Solving LP Relaxations of Large-Scale Precedence Constrained Problems. 2010
  • [2] D. Topkis. Supermodularity and Complementarity. 2011

This project is contributed by Britta Peis, Tom McCormick, and Andreas Wierz