(Mixed) Integer Linear Programming

Facets for Continuous Multi-Mixing Set with General Coefficients and Bounded Integer Variables

  • Manish Bansal
  • Kiavash Kianfar
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Integer Programming Tags , , , , ,

    Bansal and Kianfar introduced continuous multi-mixing set where the coefficients satisfy the so-called n-step MIR conditions and developed facet-defining inequalities for this set. In this paper, we first generalize their inequalities for the continuous multi-mixing set with general coefficients (where no conditions are imposed on the coefficients) and show that they are facet-defining in many … Read more

    New Benchmark Instances for the Capacitated Vehicle Routing Problem

  • Diego Pecin
  • Artur Alves Pessoa
  • Marcus Poggi de Aragão
  • Anand Subramanian
  • Eduardo Uchoa
  • Thibaut Vidal
    • Categories (Mixed) Integer Linear Programming, Meta Heuristics, Transportation Tags , ,

    The recent research on the CVRP is being slowed down by the lack of a good set of benchmark instances. The existing sets suff er from at least one of the following drawbacks: (i) became too easy for current algorithms; (ii) are too arti cial; (iii) are too homogeneous, not covering the wide range of characteristics found … Read more

    Efficient approaches for the robust network loading problem

  • Sara Mattia
  • Michael Poss
    • Categories (Mixed) Integer Linear Programming, Network Optimization, Robust Optimization Tags , , , ,

    We consider the Robust Network Loading problem with splittable flows and demands that belong to the budgeted uncertainty set. We compare the optimal solution cost and computational cost of the problem when using static routing, volume routing, affine routing, and dynamic routing. For the first three routing types, we compare the compact formulation with a … Read more

    MILP formulations for the modularity density maximization problem

  • Alberto Costa
    • Categories (Mixed) Integer Linear Programming, Network Optimization

    Cluster analysis refers to finding subsets of vertices of a graph (called clusters) which are more likely to be joined pairwise than vertices in different clusters. In the last years this topic has been studied by many researchers, and several methods have been proposed. One of the most popular is to maximize the modularity, which … Read more

    Gas Network Optimization: A comparison of Piecewise Linear Models

  • Carlos M. Correa-Posada
  • Pedro Sanchez-Martan
    • Categories (Mixed) Integer Linear Programming, Chemical Engineering Tags , , , , ,

    Gas network optimization manages the gas transport by minimizing operating costs and fulfilling contracts between consumers and suppliers. This is an NP- hard problem governed by non-convex and nonlinear gas transport functions that can be modeled by mixed integer linear programming (MILP) techniques. Under these methods, piecewise linear functions describe nonlinearities and bi- nary variables … Read more

    The single-item lot-sizing polytope with continuous start-up costs and uniform production capacity

  • Mariana Escalante
  • Javier Marenco
  • Mara del Carmen Varaldo
    • Categories (Mixed) Integer Linear Programming Tags , ,

    In this work we consider the uniform capacitated single-item single-machine lot-sizing problem with continuous start-up costs. A continuous start-up cost is generated in a period whenever there is a nonzero production in the period and the production capacity in the previous period is not saturated. This concept of start-up does not correspond to the standard … Read more

    Multi-stage adjustable robust mixed-integer optimization via iterative splitting of the uncertainty set

  • Dick den Hertog
  • Krzysztof Postek
    • Categories (Mixed) Integer Linear Programming, Robust Optimization Tags , , , ,

    In this paper we propose a methodology for constructing decision rules for integer and continuous decision variables in multiperiod robust linear optimization problems. This type of problems finds application in, for example, inventory management, lot sizing, and manpower management. We show that by iteratively splitting the uncertainty set into subsets one can differentiate the later-period … Read more

    Integer programming formulations for the elementary shortest path problem

  • Leonardo Taccari
    • Categories (Mixed) Integer Linear Programming, Network Optimization, Polyhedra Tags , , ,

    Given a directed graph G = (V, A) with arbitrary arc costs, the Elementary Shortest Path Problem (ESPP) consists of finding a minimum-cost path between two nodes s and t such that each node of G is visited at most once. If the costs induce negative cycles on G, the problem is NP-hard. In this … Read more

    Tight and Compact MIP Formulation of Configuration-Based Combined-Cycle Units

  • Carlos M. Correa-Posada
  • Germán Morales-España
  • Andres Ramos
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences Tags , , ,

    Private investors, flexibility, efficiency and environmental requirements from deregulated markets have led the existence and building of a significant number of combined-cycle gas turbines (CCGTs) in many power systems. These plants represent a complicated optimization problem for the short-term planning unit commitment (UC) carried out by independent system operators due to their multiple operating configurations. … Read more

    An SDP approach for multiperiod mixed 0–1 linear programming models with stochastic dominance constraints for risk management

  • Laureano F. Escudero
  • Dolores Romero Morales
  • Juan F. Monge
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming, Supply Chain Management

    In this paper we consider multiperiod mixed 0–1 linear programming models under uncertainty. We propose a risk averse strategy using stochastic dominance constraints (SDC) induced by mixed-integer linear recourse as the risk measure. The SDC strategy extends the existing literature to the multistage case and includes both first-order and second-order constraints. We propose a stochastic … Read more