Sven de Vries

Recoverable Robust Cardinality Constrained Maximization with Commitment of a Submodular Function

  • Sabine Münch
  • Sven de Vries
    • Categories Approximation Algorithms, Combinatorial Optimization Tags , , ,

    We consider a game-theoretic variant of maximizing a monotone increasing, submodular function under a cardinality constraint. Initially, a solution to this classical problem is determined. Subsequently, a predetermined number of elements from the ground set, not necessarily contained in the initial solution, are deleted, potentially reducing the solution’s cardinality. If any deleted elements were part … Read more

    On Packing a Submodular Knapsack of Unknown Capacity

  • Sabine Münch
  • Sven de Vries
    • Categories Approximation Algorithms, Combinatorial Optimization Tags , , ,

    Consider the problem of maximizing a monotone-increasing submodular function defined on a set of weighted items under an unknown knapsack capacity. Assume that items are packed sequentially into the knapsack and that the capacity of the knapsack is accessed through an oracle that answers whether an item fits into the currently packed knapsack. If an … Read more

    A Penalty Branch-and-Bound Method for Mixed-Binary Linear Complementarity Problems

  • Marianna De Santis
  • Sven de Vries
  • Martin Schmidt
  • Lukas Winkel
    • Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Complementarity and Variational Inequalities Tags , , , ,

    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

    A smaller extended formulation for the odd cycle inequalities of the stable set polytope

  • Sven de Vries
  • Bernd Perscheid
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Graphs and Matroids Tags , , , ,

    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

    Tight compact extended relaxations for nonconvex quadratic programming problems with box constraints

  • Sven de Vries
  • Bernd Perscheid
    • Categories (Mixed) Integer Nonlinear Programming, Graphs and Matroids, Quadratic Programming Tags ,

    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

    Exact solution of the donor-limited nearest neighbor hot deck imputation problem

  • Jan Pablo Burgard
  • Sven de Vries
  • Ulf Friedrich
  • Dennis Kreber
    • Categories Graphs and Matroids, Network Optimization, Statistics Tags , , , ,

    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

    A Branch-and-Price Algorithm and New Test Problems for Spectrum Auctions

  • Sven de Vries
  • Oktay Gunluk
  • Lazslo Ladanyi
    • Categories Applications - OR and Management Sciences, Integer Programming Tags , , ,

    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