Sven de Vries Consider the problem of maximizing a nondecreasing submodular function defined on a set of weighted items under an unknown knapsack capacity. Assume items are packed sequentially into the knapsack and the knapsack capacity is accessed through an oracle that answers whether an item fits into the currently packed knapsack. If an item is tried to … Read more
Linear complementarity problems (LCPs) are an important modeling tool for many practically relevant situations but also have many important applications in mathematics itself. Although the continuous version of the problem is extremely well studied, much less is known about mixed-integer LCPs (MILCPs) in which some variables have to be integer-valued in a solution. In particular, … Read more
For sparse graphs, the odd cycle polytope can be used to compute useful bounds for the maximum stable set problem quickly. Yannakakis introduced an extended formulation for the odd cycle inequalities of the stable set polytope in 1991, which provides a direct way to optimize over the odd cycle polytope in polynomial time, although there … Read more
Cutting planes from the Boolean Quadric Polytope (BQP) can be used to reduce the optimality gap of the NP-hard nonconvex quadratic program with box constraints (BoxQP). It is known that all cuts of the Chvátal-Gomory closure of the BQP are A-odd cycle inequalities. We obtain a compact extended relaxation of all A-odd cycle inequalities, which … Read more
Data quality in population surveys suffers from missing responses. We use combinatorial optimization to create a complete and coherent data set. The methods are based on the widespread nearest neighbor hot deck imputation method that replaces the missing values with observed values from a close unit, the so-called donor. As a repeated use of donors … Read more
When combinatorial bidding is permitted in Spectrum Auctions, such as the upcoming FCC auction #31, the resulting winner-determination problem can be computationally challenging. We present a branch-and-price algorithm based on a set-packing formulation originally proposed by Dietrich and Forrest (2002). This formulation has a variable for every possible combination of winning bids for each bidder. … Read more