integer programming

A Stochastic Optimization Approach to Energy-Efficient Underground Timetabling under Uncertain Dwell and Running Times

  • Andreas Bärmann
  • Patrick Gemander
  • Alexander Martin
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming, Transportation Tags , , , , ,

    We consider a problem from the context of energy-efficient underground railway timetabling, in which an existing timetable draft is improved by slightly changing departure and running times. In practice, synchronization between accelerating and braking trains to utilize regenerative braking plays a major role for the energy-efficiency of a timetable. Since deviations from a planned timetable … Read more

    Mathematical models and decomposition methods for the two-bar charts packing problem

  • Barkel Mathijs
  • Maxence Delorme
    • Categories Combinatorial Optimization Tags , , , ,

    We consider the two-bar charts packing (2-BCPP), a recent combinatorial optimization problem whose aim is to pack a set of one-dimensional items into the minimum number of bins. As opposed to the well-known bin packing problem, pairs of items are grouped to form bar charts, and a solution is only feasible if the first and … Read more

    DiversiTree: A New Method to Efficiently Compute Diverse Sets of Near-Optimal Solutions to Mixed-Integer Optimization Problems

  • Izuwa Ahanor
  • Hugh R. Medal
  • Andrew C. Trapp
    • Categories Applications - Science and Engineering, Integer Programming, Other Topics Tags , , ,

    While most methods for solving mixed-integer optimization problems compute a single optimal solution, a diverse set of near-optimal solutions can often lead to improved outcomes. We present a new method for finding a set of diverse solutions by emphasizing diversity within the search for near-optimal solutions. Specifically, within a branch-and-bound framework, we investigated parameterized node … Read more

    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

    Parallel Dual Dynamic Integer Programming for Large-Scale Hydrothermal Unit-Commitment

  • Bruno Colonetti
  • Erlon Finardi
  • Victor M. Zavala
  • Samuel Brito
    • Categories Dynamic Programming, Parallel Algorithms, Scheduling Tags , , ,

    Unit commitment has been at the center of power system operation for well over 50 years. Yet, this problem cannot be considered solved due to its size and complexity. Today, operators rely on off-the-shelf optimization solvers to tackle this challenging problem, and often resort to simplifications to make the problem more tractable and solvable in … Read more

    Solving a Multi-product, Multi-period, Multi-modal Freight Transportation Problem Using Integer Linear Programming

  • Anoop K.P.
  • Meenarli Sharma
    • Categories Applications - OR and Management Sciences, Transportation Tags , , ,

    We consider a real-world multimodal freight transportation problem that arises in a food grain organization in India. This problem aims to satisfy the demand for a set of warehouses for different types of food grains from another set of warehouses with surplus quantities over multiple periods of time by rail and road, while minimizing the … Read more

    A prediction-based approach for online dynamic radiotherapy scheduling

  • Tu-San Pham
  • Antoine Legrain
  • Patrick De Causmaecker
  • Louis-Martin Rousseau
    • Categories Applications - OR and Management Sciences Tags , , ,

    Patient scheduling is a difficult task as it involves dealing with stochastic factors such as an unknown arrival flow of patients. Scheduling radiotherapy treatments for cancer patients faces a similar problem. Curative patients need to start their treatment within the recommended deadlines, i.e., 14 or 28 days after their admission while reserving treatment capacity for … Read more

    Facets of the Total Matching Polytope for bipartite graphs

  • Luca Ferrarini
    • Categories 0-1 Programming, Combinatorial Optimization, Cutting Plane Approaches Tags , , ,

    The Total Matching Polytope generalizes the Stable Set Polytope and the Matching Polytope. In this paper, we give the perfect formulation for Trees and we derive two new families of valid inequalities, the balanced biclique inequalities which are always facet-defining and the non-balanced lifted biclique inequalities obtained by a lifting procedure, which are facet-defining for … Read more

    Recognizing Integrality of Weighted Rectangles Partitions

  • Paul Deuker
  • Ulf Friedrich
    • Categories (Mixed) Integer Linear Programming Tags , ,

    The weighted rectangles partitioning (WRP) problem is defined on a set of active and inactive pixels. The problem is to find a partition of the active pixels into weighted rectangles, such that the sum of their weights is maximal. The problem is formulated as an integer programming problem and instances with an integral relaxation polyhedron … Read more