Marc E. Pfetsch

Global optimization of mixed-integer ODE constrained network problems using the example of stationary gas transport

  • Oliver Habeck
  • Marc E. Pfetsch
  • Stefan Ulbrich
    • Categories Global Optimization Tags , , ,

    In this paper we propose a new approach for finding global solutions of mixed-integer nonlinear optimization problems with ordinary differential equation constraints on networks. Instead of using a first discretize then optimize approach, we combine spatial and variable branching with appropriate discretizations of the differential equations to derive relaxations of the original problem. To construct … Read more

    Algorithmic Results for Potential-Based Flows: Easy and Hard Cases

  • Martin Gross
  • Marc E. Pfetsch
  • Lars Schewe
  • Martin Schmidt
  • Martin Skutella
    • Categories Applications - Science and Engineering, Integer Programming, Network Optimization Tags , , , , ,

    Potential-based flows are an extension of classical network flows in which the flow on an arc is determined by the difference of the potentials of its incident nodes. Such flows are unique and arise, for example, in energy networks. Two important algorithmic problems are to determine whether there exists a feasible flow and to maximize … Read more

    Extended Formulations for Column Constrained Orbitopes

  • Christopher Hojny
  • Marc E. Pfetsch
  • Andreas Schmitt
    • Categories 0-1 Programming Tags , , ,

    In the literature, packing and partitioning orbitopes were discussed to handle symmetries that act on variable matrices in certain binary programs. In this paper, we extend this concept by restrictions on the number of 1-entries in each column. We develop extended formulations of the resulting polytopes and present numerical results that show their effect on … Read more

    On the Size of Integer Programs with Bounded Coefficients or Sparse Constraints

  • Christopher Hojny
  • Marc E. Pfetsch
  • Hendrik Lüthen
    • Categories (Mixed) Integer Linear Programming Tags , , ,

    Integer programming formulations describe optimization problems over a set of integer points. A fundamental problem is to determine the minimal size of such formulations, in particular, if the size of the coefficients or sparsity of the constraints is bounded. This article considers lower and upper bounds on these sizes both in the original and in … Read more

    The SCIP Optimization Suite 4.0

  • Tobias Fischer
  • Tristan Gally
  • Gerald Gamrath
  • Ambros Gleixner
  • Robert Lion Gottwald
  • Gregor Hendel
  • Thorsten Koch
  • Marco E. Lübbecke
  • Stephen J. Maher
  • Matthias Miltenberger
  • Marc E. Pfetsch
  • Felipe Serrano
  • Dieter Weninger
  • Jakob Witzig
  • Benjamin Müller
  • Christian Puchert
  • Daniel Rehfeldt
  • Sebastian Schenker
  • Robert Schwarz
  • Yuji Shinano
  • Jonas T. Witt
    • Categories (Mixed) Integer Nonlinear Programming, Optimization Software and Modeling Systems Tags , ,

    The SCIP Optimization Suite is a powerful collection of optimization software that consists of the branch-cut-and-price framework and mixed-integer programming solver SCIP, the linear programming solver SoPlex, the modeling language Zimpl, the parallelization framework UG, and the generic branch-cut-and-price solver GCG. Additionally, it features the extensions SCIP-Jack for solving Steiner tree problems, PolySCIP for solving … Read more

    Polytopes Associated with Symmetry Handling

  • Christopher Hojny
  • Marc E. Pfetsch
    • Categories 0-1 Programming Tags , , ,

    This paper investigates a polyhedral approach to handle symmetries in mixed-binary programs. We study symretopes, i.e., the convex hulls of all binary vectors that are lexicographically maximal in their orbit with respect to the symmetry group. These polytopes turn out to be quite complex. For practical use, we therefore develop an integer programming formulation with … Read more

    On the Structure of Linear Programs with Overlapping Cardinality Constraints

  • Tobias Fischer
  • Marc E. Pfetsch
    • Categories Branch and Cut Algorithms, Integer Programming Tags , , , ,

    Cardinality constraints enforce an upper bound on the number of variables that can be nonzero. This article investigates linear programs with cardinality constraints that mutually overlap, i.e., share variables. We present the components of a branch-and-cut solution approach, including new branching rules that exploit the structure of the corresponding conflict hypergraph. We also investigate valid … Read more

    Computing Restricted Isometry Constants via Mixed-Integer Semidefinite Programming

  • Tristan Gally
  • Marc E. Pfetsch
    • Categories (Mixed) Integer Nonlinear Programming, Semi-definite Programming Tags , ,

    One of the fundamental tasks in compressed sensing is finding the sparsest solution to an underdetermined system of linear equations. It is well known that although this problem is NP-hard, under certain conditions it can be solved by using a linear program which minimizes the 1-norm. The restricted isometry property has been one of the … Read more

    A Framework for Solving Mixed-Integer Semidefinite Programs

  • Tristan Gally
  • Marc E. Pfetsch
  • Stefan Ulbrich
    • Categories (Mixed) Integer Nonlinear Programming, Optimization Software and Modeling Systems, Semi-definite Programming

    Mixed-integer semidefinite programs arise in many applications and several problem-specific solution approaches have been studied recently. In this paper, we investigate a generic branch-and-bound framework for solving such problems. We first show that strict duality of the semidefinite relaxations is inherited to the subproblems. Then solver components like dual fixing, branching rules, and primal heuristics … Read more

    Monoidal Cut Strengthening and Generalized Mixed-Integer Rounding for Disjunctions and Complementarity Constraints

  • Tobias Fischer
  • Marc E. Pfetsch
    • Categories Integer Programming Tags , , ,

    In the early 1980s, Balas and Jeroslow presented monoidal disjunctive cuts exploiting the integrality of variables. This article investigates the relation of monoidal cut strengthening to other classes of cutting planes for general two-term disjunctions. We introduce a generalization of mixed-integer rounding cuts and show equivalence to monoidal disjunctive cuts. Moreover, we demonstrate the effectiveness … Read more