Rolf van der Hulst

Implied Integrality in Mixed-Integer Optimization

  • Rolf van der Hulst
  • Matthias Walter
    • Categories (Mixed) Integer Linear Programming, Integer Programming, Polyhedra Tags , , , ,

    Implied-integer detection is a well-known presolving technique that is used by many Mixed-Integer Linear Programming solvers. Informally, a variable is said to be implied integer if its integrality is enforced implicitly by integrality of other variables and the constraints of a problem. In this work we formalize the definition of implied integrality by taking a … Read more

    A Row-wise Algorithm for Graph Realization

  • Rolf van der Hulst
  • Matthias Walter
    • Categories (Mixed) Integer Linear Programming, Graphs and Matroids, Network Optimization Tags , , , , ,

    Given a \(\{0,1\}\)-matrix \(M\), the graph realization problem for \(M\) asks if there exists a spanning forest such that the columns of \(M\) are incidence vectors of paths in the forest. The problem is closely related to the recognition of network matrices, which are a large subclass of totally unimodular matrices and have many applications … Read more