mixed-integer linear programming

Accelerating Domain Propagation: an Efficient GPU-Parallel Algorithm over Sparse Matrices

  • Ambros Gleixner
  • Sebastian Pokutta
  • Boro Sofranac
    • Categories Integer Programming Tags , , , ,

    Fast domain propagation of linear constraints has become a crucial component of today’s best algorithms and solvers for mixed integer programming and pseudo-boolean optimization to achieve peak solving performance. Irregularities in the form of dynamic algorithmic behaviour, dependency structures, and sparsity patterns in the input data make efficient implementations of domain propagation on GPUs and, … Read more

    The SCIP Optimization Suite 7.0

  • Daniel Anderson
  • Ksenia Bestuzheva
  • Wei-Kun Chen
  • Leon Eifler
  • Gerald Gamrath
  • Maxime Gasse
  • Ambros Gleixner
  • Gregor Hendel
  • Christopher Hojny
  • Thorsten Koch
  • Pierre Le Bodic
  • Stephen J. Maher
  • Frederic Matter
  • Matthias Miltenberger
  • Marc E. Pfetsch
  • Felipe Serrano
  • Dieter Weninger
  • Jakob Witzig
  • Patrick Gemander
  • Leona Gottwald
  • Katrin Halbig
  • Erik Mühmer
  • Benjamin Müller
  • Franziska Schlösser
  • Yuji Shinano
  • Christine Tawfik
  • Stefan Vigerske
  • Fabian Wegscheider
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming Tags , , , , , , , , , , , , ,

    The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 7.0 of the SCIP Optimization Suite. The new version features the parallel presolving library PaPILO as a new addition to the suite. PaPILO 1.0 simplifies … Read more

    A K-Nearest Neighbor Heuristic for Real-Time DC Optimal Transmission Switching

  • Shabbir Ahmed
  • Santanu S. Dey
  • Jean-Paul Watson
  • Emma S. Johnson
    • Categories Applications - OR and Management Sciences Tags , , ,

    While transmission switching is known to reduce power generation costs, the difficulty of solving even DC optimal transmission switching (DCOTS) has prevented optimal transmission switching from becoming commonplace in real-time power systems operation. In this paper, we present a k-nearest neighbors (KNN) heuristic for DCOTS which relies on the insight that, for routine operations on … Read more

    Testing Copositivity via Mixed-Integer Linear Programming

  • Kurt M. Anstreicher
    • Categories (Mixed) Integer Linear Programming, Global Optimization Theory Tags , ,

    We describe a simple method to test if a given matrix is copositive by solving a single mixed-integer linear programming (MILP) problem. This methodology requires no special coding to implement and takes advantage of the computational power of modern MILP solvers. Numerical experiments demonstrate that the method is robust and efficient. Citation Dept. of Business … Read more

    On the propagation of quality requirements for mechanical assemblies in industrial manufacturing

  • Philipp Armbrust
  • Paul Alexandru Bucur
  • Philipp Hungerländer
    • Categories Mechanical Engineering Tags , , , ,

    A frequent challenge encountered by manufacturers of mechanical assemblies consists of the definition of quality criteria for the assembly lines of the subcomponents which are mounted into the final product. The rollout of Industry 4.0 standards paves the way for the usage of data-driven, intelligent approaches towards this goal. In this work, we investigate such … Read more

    Mixed-Integer Linear Programming for Scheduling Unconventional Oil Field Development

  • Jeff Linderoth
  • James R. Luedtke
  • Fabian Rigterink
  • Akhilesh Soni
    • Categories Scheduling Tags , , ,

    The scheduling of drilling and hydraulic fracturing of wells in an unconventional oil field plays an important role in the profitability of the field. A key challenge arising in this problem is the requirement that neither drilling nor oil production can be done at wells within a specified neighborhood of a well being fractured. We … Read more

    A Solution Framework for Linear PDE-Constrained Mixed-Integer Problems

  • Armin Fügenschuh
  • Sven Leyffer
  • Fabian Gnegel
  • Michael Hagel
  • Marcus Stiemer
    • Categories (Mixed) Integer Linear Programming, Control Applications, Network Optimization Tags , , , , ,

    We present a general numerical solution method for control problems with PDE-defined state variables over a finite set of binary or continuous control variables. We show empirically that a naive approach that applies a numerical discretization scheme to the PDEs (and if necessary a linearization scheme) to derive constraints for a mixed-integer linear program (MILP) … Read more

    Exact Methods for the Traveling Salesman Problem with Drone

  • Roberto Roberti
  • Mario Ruthmair
    • Categories (Mixed) Integer Linear Programming, Dynamic Programming, Transportation Tags , , , ,

    Efficiently handling last-mile deliveries becomes more and more important nowadays. Using drones to support classical vehicles allows improving delivery schedules as long as efficient solution methods to plan last-mile deliveries with drones are available. We study exact solution approaches for some variants of the traveling salesman problem with drone (TSP-D) in which a truck and … Read more

    Integer linear programming formulations for the minimum connectivity inference problem and model reduction principles

  • Muhammad Abid Dar
  • Andreas Fischer
  • John Martinovic
  • Guntram Scheithauer
    • Categories (Mixed) Integer Linear Programming, Polyhedra Tags , , , ,

    The minimum connectivity inference (MCI) problem represents an NP-hard generalization of the well-known minimum spanning tree problem. Given a set of vertices and a finite collection of subsets (of this vertex set), the MCI problem requires to find an edge set of minimal cardinality so that the vertices of each subset are connected. Although the … Read more

    Robust Optimal Aiming Strategies in Concentrated Solar Tower Power Plants

  • Christina Büsing
  • Pascal Richter
  • Jeff Cumpston
  • Fynn Kepp
  • Sascha Kuhnke
    • Categories Robust Optimization Tags , , , ,

    A concentrated solar tower power plant consists of a receiver mounted atop of a central tower and a field of movable mirrors called heliostats. The heliostats concentrate solar radiation onto the receiver where a fluid is heated to produce electricity in a conventional thermodynamic cycle. Aiming strategies are used to assign each heliostat to an … Read more