(Mixed) Integer Linear Programming

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

    n-step cycle inequalities: facets for continuous n-mixing set and strong cuts for multi-module capacitated lot-sizing problem

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

    In this paper, we introduce a generalization of the continuous mixing set (which we refer to as the continuous n-mixing set). This set is closely related to the feasible set of the multi-module capacitated lot-sizing (MML) problem with(out) backlogging. We develop new classes of valid inequalities for this set, referred to as n’-step cycle inequalities, … Read more

    A Parallel Local Search Framework for the Fixed-Charge Multicommodity Network Flow Problem

  • Shabbir Ahmed
  • Lluís-Miquel Munguía
  • George L. Nemhauser
  • David A. Bader
  • Vikas Goel
  • Yufen Shao
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Parallel Algorithms Tags , ,

    We present a parallel local search approach for obtaining high quality solutions to the Fixed Charge Multi-commodity Network Flow problem (FCMNF). The approach proceeds by improving a given feasible solution by solving restricted instances of the problem where flows of certain commodities are fixed to those in the solution while the other commodities are locally … Read more

    The unrooted set covering connected subgraph problem differentiating between HIV envelope sequences

  • Stephen J. Maher
  • John M Murray
    • Categories (Mixed) Integer Linear Programming, Biomedical Applications Tags , , ,

    This paper presents a novel application of operations research techniques to the analysis of HIV env gene sequences, aiming to identify key features that are possible vaccine targets. These targets are identified as being critical to the transmission of HIV by being present in early transmitted (founder) sequences and absent in later chronic sequences. Identifying … Read more

    A new mixed integer linear programming formulation for one problem of exploration of online social networks

  • Aleksandra Petrovic
    • Categories (Mixed) Integer Linear Programming, Marketing, Network Optimization

    Enormous global popularity of online social network sites has initiated numerous studies and methods investigating different aspects of their use, so some concepts from network-based studies in optimization theory can be used for research into online networks. In Gaji\’c (2014) are given a several new mixed integer linear programming formulations for first and second problem … Read more