(Mixed) Integer Linear Programming

An Algorithm-Independent Measure of Progress for Linear Constraint Propagation

  • Ambros Gleixner
  • Sebastian Pokutta
  • Boro Sofranac
    • Categories (Mixed) Integer Linear Programming Tags ,

    Propagation of linear constraints has become a crucial sub-routine in modern Mixed-Integer Programming (MIP) solvers. In practice, iterative algorithms with tolerance-based stopping criteria are used to avoid problems with slow or infinite convergence. However, these heuristic stopping criteria can pose difficulties for fairly comparing the efficiency of different implementations of iterative propagation algorithms in a … Read more

    Optimal Eco-Routing for Hybrid Vehicles with Mechanistic/Data-Driven Powertrain Model Embedded

  • Adrian Caspari
  • Alexander Mitsos
  • Steffen Fahr
    • Categories (Mixed) Integer Linear Programming, Applications - Science and Engineering, Transportation Tags , , , , , ,

    Hybrid Electric Vehicles (HEVs) are regarded as an important (transition) element of sustainable transportation. Exploiting the full potential of HEVs requires (i) a suitable route selection and (ii) suitable power management, i.e., deciding on the split between combustion engine and electric motor usage as well as the mode of the electric motor, i.e., driving or … Read more

    Markov Chain Sampling of Hidden Relay States for Economic Dispatch with Cascading Failures

  • John Birge
  • Arnab Sur
    • Categories (Mixed) Integer Linear Programming, Energy, Stochastic Programming Tags , , , , ,

    Independent system operators (ISO) of electric power networks aim to dispatch electricity economically while maintaining system reliability. NERC (North America Electric Reliability Council) requires the transmission network to be (N-1)-secure, i.e., to have sufficient supply to satisfy demand in the event of the failure of any single resource in the network. Such a policy is … Read more

    On the Polyhedrality of the Chvatal-Gomory Closure

  • Haoran Zhu
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Polyhedra Tags , ,

    In this paper, we provide an equivalent condition for the Chvatal-Gomory (CG) closure of a closed convex set to be finitely-generated. Using this result, we are able to prove that, for any closed convex set that can be written as the Minkowski sum of a compact convex set and a closed convex cone, its CG … Read more

    Nonconvex Equilibrium Models for Energy Markets: Exploiting Price Information to Determine the Existence of an Equilibrium

  • Julia Grübel
  • Olivier Huber
  • Lukas Hümbs
  • Max Klimm
  • Martin Schmidt
  • Alexandra Schwartz
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Constrained Nonlinear Optimization Tags , , , ,

    Motivated by examples from the energy sector, we consider market equilibrium problems (MEPs) involving players with nonconvex strategy spaces or objective functions, where the latter are assumed to be linear in market prices. We propose an algorithm that determines if an equilibrium of such an MEP exists and that computes an equilibrium in case of … Read more

    High quality timetables for Italian schools

  • Claudio Crobu
  • Massimo Di Francesco
  • Enrico Gorgone
    • Categories (Mixed) Integer Linear Programming, Scheduling Tags , ,

    This work introduces a complex variant of the timetabling problem, which is motivated by the case of Italian schools. The new requirements enforce to (i) provide the same idle times for teachers, (ii) avoid consecutive \emph{heavy} days, (iii) limit daily multiple lessons for the same class, (iv) introduce shorter time units to differentiate entry and … Read more

    Single-neuron convexifications for binarized neural networks

  • Andrés Gómez
  • Shaoning Han
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Statistics Tags , , , ,

    Binarized neural networks are an important class of neural network in deep learning due to their computational efficiency. This paper contributes towards a better understanding of the structure of binarized neural networks, specifically, ideal convex representations of the activation functions used. We describe the convex hull of the graph of the signum activation function associated … Read more

    Computational Aspects of Relaxation Complexity: Possibilities and Limitation

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

    The relaxation complexity $\mathrm{rc}(X)$ of the set of integer points $X$ contained in a polyhedron is the smallest number of facets of any polyhedron $P$ such that the integer points in $P$ coincide with $X$. It is a useful tool to investigate the existence of compact linear descriptions of $X$. In this article, we derive … Read more

    Variable and constraint reduction techniques for the temporal bin packing problem with fire-ups

  • Fabio Furini
  • John Martinovic
  • José Valério de Carvalho
  • Nico Strasdat
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences Tags , , ,

    The aim of this letter is to design and computationally test several improvements for the compact integer linear programming (ILP) formulations of the temporal bin packing problem with fire-ups (TBPP-FU). This problem is a challenging generalization of the classical bin packing problem in which the items, interpreted as jobs of given weight, are active only … Read more

    Total Coloring and Total Matching: Polyhedra and Facets

  • Luca Ferrarini
  • Stefano Gualandi
    • Categories (Mixed) Integer Linear Programming, 0-1 Programming, Cutting Plane Approaches Tags , , ,

    A total coloring of a graph G = (V, E) is an assignment of colors to vertices and edges such that neither two adjacent vertices nor two incident edges get the same color, and, for each edge, the end-points and the edge itself receive different colors. Any valid total coloring induces a partition of the … Read more