Conference Agenda

Hardness of optimization problems has been studied for several decades both theoretically and empirically. In this context, empirical hardness revolves around the observation that the computational tractability of an NP-hard problem can vary significantly between instances depending on their characteristics, even if they are of similar size. Understanding which characteristics drive this computational tractability is of interest from a practical perspective as it can allow to preselect a suitable class of algorithms without investigating significant methodological development or implementation effort.

Against this background, this work tackles the empirical hardness of unrelated parallel machine scheduling problems. First, we introduce a novel hardness measure to quantify the empirical hardness entailed by certain data patterns of an instance. The measure is based on run time, number of cuts explored, and the relative gap of an exact solver within a time limit. Existing benchmark instances are then analyzed and studied to identify the hardness of each instance. Next, a deep descriptive study follows to define complementary order parameters that govern the empirical hardness produced by the resulting instance. We show that the newly generated benchmark contains a higher number of hard instances highlighting the efficiency of the proposed instance generation protocol. Moreover, we introduce a machine-learning-based predictor and show that it efficiently predicts the hardness of instances.

We advance the theoretical study of {0, 1/2}-cuts for integer programming problems. Such cuts are Gomory-Chvátal cuts that only need multipliers of value 0 or 1/2 in their derivation. The intersection of all {0, 1/2}-cuts derived from the inequality description is called the {0,1/2}-closure of the polytope P.

The primal separation problem for {0, 1/2}-cuts is: Given a vertex of the integer hull of P and some fractional point in P, does there exist a {0,1/2}-cut that is tight at the integral vertex and violated by the fractional point? Primal separation is the key ingredient of primal cutting-plane approaches to integer programming. In general, primal separation for {0,1/2}-cuts is NP-hard. We present two cases for which primal separation is solvable in polynomial time. As an interesting side product, we obtain a(nother) simple proof that matching can be solved in polynomial time.

Furthermore, since optimization over the Gomory-Chvátal closure is also NP-hard, there has been recent research on solving the optimization problem over the Gomory-Chvátal closure approximately. In a similar spirit, we show that the optimization problem over the {0,1/2}-closure can be solved in polynomial time up to any fixed precision.

In this talk, we introduce the parametric matroid l-interdiction problem, where l is a fixed natural number. Given a matroid where each element has a parametric weight that depends linearly on a real-valued parameter from a parameter interval, the goal is to compute for every possible parameter value an optimal interdiction strategy. An optimal interdiction strategy is a set of l elements that when removed from the matroid increases the weight of the minimum weight basis as much as possible. The problem can be viewed as a parametric and thus robust extension of the matroid l-interdiction problem, which is a well-studied problem for the special case of graphical matroids. We show different properties of an optimal interdiction strategy to reduce the number of relevant strategies. We further use these properties to construct an exact algorithm to solve the problem in polynomial time.

The Partial Scenario Set Cover problem (PSSC) generalizes the Partial Set Cover problem, which is itself a generalization of the classical Set Cover problem. We are given a finite ground set Q, a collection S of subsets of Q to choose from, each of which is associated with a nonnegative cost, and a second collection U of subsets of Q of which a given number l must be covered. The task is to choose a minimum cost sub-collection from S that covers at least l sets from U. The motivation behind PSSC stems from its application in locating emergency doctors. We explore several graph-theoretic problems within the framework of PSSC. We demonstrate that these problems are as hard to approximate as the Smallest k-Edge Subgraph problem. Additionally, we present simple approximation algorithms tailored to address these challenges. Our findings not only shed light on the inherent difficulty of these problems but also provide practical solutions for their approximation.