(Mixed) Integer Linear Programming

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

    An Exact Extended Formulation for the Unrelated Parallel Machine Total Weighted Completion Time Problem

  • Kerem Bülbül
  • Halil Sen
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Scheduling

    The plethora of research on NP-hard parallel machine scheduling problems is focused on heuristics due to the theoretically and practically challenging nature of these problems. Only a handful of exact approaches are available in the literature, and most of these suffer from scalability issues. Moreover, the majority of the papers on the subject are restricted … Read more

    On the exact separation of rank inequalities for the maximum stable set problem

  • Stefano Coniglio
  • Stefano Gualandi
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches, Polyhedra Tags , , , , ,

    When addressing the maximum stable set problem on a graph G = (V,E), rank inequalities prescribe that, for any subgraph G[U] induced by U ⊆ V , at most as many vertices as the stability number of G[U] can be part of a stable set of G. These inequalities are very general, as many of … Read more

    On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds-Karp to Bland and Beyond

  • Jesús A. De Loera
  • Raymond Hemmecke
  • Jon Lee
    • Categories (Mixed) Integer Linear Programming, Linear Programming Tags , , , , , , , , ,

    Motivated by Bland’s linear-programming generalization of the renowned Edmonds-Karp efficient refinement of the Ford-Fulkerson maximum-flow algorithm, we discuss three closely-related natural augmentation rules for linear and integer-linear optimization. In several nice situations, we show that polynomially-many augmentation steps suffice to reach an optimum. In particular, when using “discrete steepest-descent augmentations” (i.e., directions with the best … Read more

    A Generalization of Benders’ Algorithm for Two-Stage Stochastic Optimization Problems With Mixed Integer Recourse

  • Anahita Hassanzadeh
  • Ted K. Ralphs
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags ,

    We describe a generalization of Benders’ method for solving two-stage stochastic linear optimization problems in which there are both continuous and integer variables in the first and second stages. Benders’ method relies on finding effective lower approximations for the value function of the second-stage problem. In this setting, the value function is a discontinuous, non-convex, … Read more

    On the Value Function of a Mixed Integer Linear Optimization Problem and an Algorithm for its Construction

  • Anahita Hassanzadeh
  • Ted K. Ralphs
    • Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , , ,

    This paper addresses the value function of a general mixed integer linear optimization problem (MILP). The value function describes the change in optimal objective value as the right-hand side is varied and understanding its structure is central to solving a variety of important classes of optimization problems. We propose a discrete representation of the MILP … Read more

    New symmetries in mixed-integer linear optimization

  • Philipp M. Christophel
  • Menal Guzelsoy
  • Imre Pólik
    • Categories (Mixed) Integer Linear Programming Tags , ,

    We present two novel applications of symmetries for mixed-integer linear programming. First we propose two variants of a new heuristic to improve the objective value of a feasible solution using symmetries. These heuristics can use either the actual permutations or the orbits of the variables to find better feasible solutions. Then we introduce a new … Read more

    Solving Bilevel Mixed Integer Program by Reformulations and Decomposition

  • Yu An
  • Bo Zeng
    • Categories (Mixed) Integer Linear Programming, Complementarity and Variational Inequalities Tags , , ,

    In this paper, we study bilevel mixed integer programming (MIP) problem and present a novel computing scheme based on reformulations and decomposition strategy. By converting bilevel MIP into a constrained mathematical program, we present its single-level reformulations that are friendly to perform analysis and build insights. Then, we develop a decomposition algorithm based on column-and-constraint … Read more

    Tight MIP Formulations of the Power-Based Unit Commitment Problem

  • Claudio Gentile
  • Germán Morales-España
  • Andres Ramos
    • Categories (Mixed) Integer Linear Programming, Scheduling Tags , , , , ,

    This paper provides the convex hull description for the basic operation of slow- and quick-start units in power-based unit commitment (UC) problems. The basic operating constraints that are modeled for both types of units are: 1) generation limits and 2) minimum up and down times. Apart from this, the startup and shutdown processes are also … Read more

    A Tight MIP Formulation of the Unit Commitment Problem with Start-up and Shut-down Constraints

  • Claudio Gentile
  • Germán Morales-España
  • Andres Ramos
    • Categories (Mixed) Integer Linear Programming, Scheduling Tags , ,

    This paper provides the convex hull description for the following basic operating constraints of a single power generation unit in Unit Commitment (UC) problems: 1) generation limits, 2) startup and shutdown capabilities, and 3) minimum up and down times. Although the model does not consider some crucial constraints, such as ramping, the proposed constraints can … Read more