Integer Programming

Exact solution methods for the Resource Constrained Project Scheduling Problem with a flexible Project Structure

  • T. Van der Beek
  • J.T. Van Essen
  • J. Pruyn
  • Karen I. Aardal
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , , ,

    The Resource Constrained Project Scheduling Problem with a flexible Project Structure (RCPSP-PS) is a generalization of the Resource Constrained Project Scheduling Problem (RCPSP). The objective of the RCPSP-PS is to find a minimal makespan schedule subject to precedence and resource constraints, while only having to execute a subset of all activities. We present a general … Read more

    A Gauss-Newton-based Decomposition Algorithm for Nonlinear Mixed-Integer Optimal Control Problems

  • Adrian Bürger
  • Clemens Zeile
  • Angelika Altmann-Dieses
  • Sebastian Sager
  • Moritz Diehl
    • Categories (Mixed) Integer Nonlinear Programming, Control Applications, Systems governed by Differential Equations Optimization Tags , ,

    For the fast approximate solution of Mixed-Integer Non-Linear Programs (MINLPs) arising in the context of Mixed-Integer Optimal Control Problems (MIOCPs) a decomposition algorithm exists that solves a sequence of three comparatively less hard subproblems to determine an approximate MINLP solution. In this work, we propose a problem formulation for the second algorithm stage that is … Read more

    Automatic Reformulations for Convex Mixed-Integer Nonlinear Optimization: Perspective and Separability

  • Meenarli Sharma
  • Ashutosh Mahajan
    • Categories (Mixed) Integer Nonlinear Programming, Optimization Software and Modeling Systems Tags , , , ,

    Tight reformulations of combinatorial optimization problems like Convex Mixed-Integer Nonlinear Programs (MINLPs) enable one to solve these problems faster by obtaining tight bounds on the optimal value. We consider two techniques for reformulation: perspective reformulation and separability detection. We develop routines for the automatic detection of problem structures suitable for these reformulations and implement new … Read more

    Advancements in the computation of enclosures for multi-objective optimization problems

  • Gabriele Eichfelder
  • Leo Warnow
    • Categories (Mixed) Integer Nonlinear Programming, Multi-Criteria Optimization, Nonlinear Optimization Tags , , , ,

    A central goal for multi-objective optimization problems is to compute their nondominated sets. In most cases these sets consist of infinitely many points and it is not a practical approach to compute them exactly. One solution to overcome this problem is to compute an enclosure, a special kind of coverage, of the nondominated set. One … Read more

    Benders-type Branch-and-Cut Algorithms for Capacitated Facility Location with Single-Sourcing

  • Dieter Weninger
  • Laurence A. Wolsey
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Facility Planning and Design Tags , , , ,

    We consider the capacitated facility location problem with (partial) single-sourcing (CFLP-SS). A natural mixed integer formulation for the problem involves 0-1 variables x_j indicating whether faclility j is used or not and y_{ij} variables indicating the fraction of the demand of client i that is satisfied from facility j. When the x variables are fixed, … Read more

    A branch-and-prune algorithm for discrete Nash equilibrium problems

  • Stefan Schwarze
  • Oliver Stein
    • Categories (Mixed) Integer Nonlinear Programming, Game Theory Tags , , ,

    We present a branch-and-prune procedure for discrete Nash equilibrium problems with a convex description of each player’s strategy set. The derived pruning criterion does not require player convexity, but only strict convexity of some player’s objective function in a single variable. If satisfied, it prunes choices for this variable by stating activity of certain constraints. … Read more

    An approximation algorithm for optimal piecewise linear approximations of bounded variable products

  • Lukas Hager
  • Robert Burlacu
  • Andreas Bärmann
  • Katja Kutzer
    • Categories (Mixed) Integer Nonlinear Programming, Approximation Algorithms, Quadratic Programming Tags , , ,

    We investigate the optimal piecewise linear interpolation of the bivariate product xy over rectangular domains. More precisely, our aim is to minimize the number of simplices in the triangulation underlying the interpolation, while respecting a prescribed approximation error. First, we show how to construct optimal triangulations consisting of up to five simplices. Using these as … Read more

    Continuous Covering on Networks: Strong Mixed Integer Programming Formulations

  • Mercedes Pelegrín
  • Liding Xu
    • Categories (Mixed) Integer Linear Programming, Facility Planning and Design, Network Optimization Tags , , ,

    Covering problems are well-studied in the domain of Operations Research, and, more specifically, in Location Science. When the location space is a network, the most frequent assumption is to consider the candidate facility locations, the points to be covered, or both, to be discrete sets. In this work, we study the set-covering location problem when … Read more

    A Reciprocity Between Tree Ensemble Optimization and Multilinear Optimization

  • Jongeun Kim
  • Jean-Philippe P. Richard
  • Mohit Tawarmalani
    • Categories (Mixed) Integer Nonlinear Programming Tags , , ,

    In this paper, we establish a polynomial equivalence between tree ensemble optimization and optimization of multilinear functions over the Cartesian product of simplices. We use this insight to derive new formulations for tree ensemble optimization problems and to obtain new convex hull results for multilinear polytopes. A computational experiment on multi-commodity transportation problems with costs … Read more

    Efficient MIP Techniques for Computing the Relaxation Complexity

  • Gennadiy Averkov
  • Christopher Hojny
  • Matthias Schymura
    • Categories (Mixed) Integer Linear Programming Tags , , ,

    The relaxation complexity rc(X) of the set of integer points X contained in a polyhedron is the minimal number of inequalities needed to formulate a linear optimization problem over X without using auxiliary variables. Besides its relevance in integer programming, this concept has interpretations in aspects of social choice, symmetric cryptanalysis, and machine learning. We … Read more