(Mixed) Integer Linear 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

    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

    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

    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

    Integer programming column generation: Accelerating branch-and-price using a novel pricing scheme for finding high-quality solutions in set covering, packing, and partitioning problems

  • Stephen J. Maher
  • Elina Rönnberg
    • Categories (Mixed) Integer Linear Programming Tags , , ,

    Large-neighbourhood search (LNS) heuristics are important mathematical programming techniques that search for primal feasible solutions by solving an auxiliary problem with a restricted feasible region. Extending such powerful generic LNS heuristics to the branch- and-price context is inherently challenging. The most prominent challenges arise from the fact that in branch-and-price algorithms, columns are generated with … Read more

    A Novel Model for Transfer Synchronization in Transit Networks and a Lagrangian-based Heuristic Solution Method

  • Zahra Ansarilari
  • Merve Bodur
  • Amer Shalaby
    • Categories (Mixed) Integer Linear Programming, Transportation Tags , ,

    To realize the benefits of network connectivity in transfer-based transit networks, it is critical to minimize transfer disutility for passengers by synchronizing timetables of intersecting routes. We propose a mixed-integer linear programming timetable synchronization model that incorporates new features, such as dwell time determination and vehicle capacity limit consideration, which have been largely overlooked in … Read more

    Theoretical Insights and a New Class of Valid Inequalities for the Temporal Bin Packing Problem with Fire-Ups

  • John Martinovic
  • Nico Strasdat
    • Categories (Mixed) Integer Linear Programming, Scheduling Tags , , , ,

    The temporal bin packing problem with fire-ups (TBPP-FU) is a two-dimensional packing problem where one geometric dimension is replaced by a time horizon. The given items (jobs) are characterized by a resource consumption, that occurs exclusively during an activity interval, and they have to be placed on servers so that the capacity constraint is respected … Read more

    Fleet & tail assignment under uncertainty

  • Lukas Glomb
  • Frauke Liers
  • Florian Rösel
    • Categories (Mixed) Integer Linear Programming, Airline Optimization, Robust Optimization Tags , , ,

    Airlines solve many different optimization problems and combine the resulting solutions to ensure smooth, minimum-cost operations. Crucial problems are the Fleet Assignment, which assigns aircraft types to flights of a given schedule, and the Tail Assignment, which determines individual flight sequences to be performed by single aircraft. In order to find a cost-optimal solution, many … Read more

    Pattern-based ILP models for the one-dimensional cutting stock problem with setup cost

  • Mateus Martin
  • Horacio Hideki Yanasse
  • Luiz Leduíno Salles Neto
    • Categories (Mixed) Integer Linear Programming, Production and Logistics Tags , , , ,

    The One-Dimensional Cutting Stock Problem with Setup Cost (CSP-S) is a cutting problem that seeks a cutting plan with a minimum number of objects and a minimum number of different patterns. This problem gains relevance in manufacturing settings, where time consuming operations to set up the knives of the cutting machine for the new patterns … Read more

    Shattering Inequalities for Learning Optimal Decision Trees

  • Justin Boutilier
  • Carla Michini
  • Zachary Zhou
    • Categories (Mixed) Integer Linear Programming Tags , ,

    Recently, mixed-integer programming (MIP) techniques have been applied to learn optimal decision trees. Empirical research has shown that optimal trees typically have better out-of-sample performance than heuristic approaches such as CART. However, the underlying MIP formulations often suffer from slow runtimes, due to weak linear programming (LP) relaxations. In this paper, we first propose a … Read more