mixed-integer programming

Facets for Single Module and Multi-Module Capacitated Lot-Sizing Problems without Backlogging

  • Manish Bansal
    • Categories Cutting Plane Approaches, Production and Logistics Tags , , , , ,

    In this paper, we consider the well-known constant-batch lot-sizing problem, which we refer to as the single module capacitated lot-sizing (SMLS) problem, and multi-module capacitated lot-sizing (MMLS) problem. We provide sufficient conditions under which the (k,l,S,I) inequalities of Pochet and Wolsey (Math of OR 18: 767-785, 1993), the mixed (k,l,S,I) inequalities, derived using mixing procedure … Read more

    On the Size of Integer Programs with Bounded Coefficients or Sparse Constraints

  • Christopher Hojny
  • Marc E. Pfetsch
  • Hendrik Lüthen
    • Categories (Mixed) Integer Linear Programming Tags , , ,

    Integer programming formulations describe optimization problems over a set of integer points. A fundamental problem is to determine the minimal size of such formulations, in particular, if the size of the coefficients or sparsity of the constraints is bounded. This article considers lower and upper bounds on these sizes both in the original and in … Read more

    Warm-start of interior point methods for second order cone optimization via rounding over optimal Jordan frames

  • Sertalp B. Çay
  • Imre Pólik
  • Tamás Terlaky
    • Categories Branch and Cut Algorithms, Second-Order Cone Programming Tags , , , ,

    Interior point methods (IPM) are the most popular approaches to solve Second Order Cone Optimization (SOCO) problems, due to their theoretical polynomial complexity and practical performance. In this paper, we present a warm-start method for primal-dual IPMs to reduce the number of IPM steps needed to solve SOCO problems that appear in a Branch and … Read more

    Optimizing regular symmetric timetables: a method to reach the best modal split for railway

  • Maurizio Bruglieri
  • Roberto Maja
  • Samuel Tolentino
    • Categories (Mixed) Integer Linear Programming, Scheduling, Transportation Tags , ,

    A regular timetable is a collection of events that repeat themselves every specific time span. This even structure, whenever applied at a whole network, leads to several benefits both for users and the company, although some issues are introduced, especially about dimensioning the service. It is therefore fundamental to properly consider the interaction between the … Read more

    A Branch-and-Cut Algorithm for Mixed Integer Bilevel Linear Optimization Problems and Its Implementation

  • S.T. DeNegre
  • Ted K. Ralphs
  • S. Tahernejad
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Optimization Software and Modeling Systems Tags , , ,

    In this paper, we describe an algorithmic framework for solving mixed integer bilevel linear optimization problems (MIBLPs) by a generalized branch-and-cut approach. The framework presented merges features from existing algorithms (for both traditional mixed integer linear optimization and MIBLPs) with new techniques to produce a flexible and robust framework capable of solving a wide range … Read more

    Generation techniques for linear and integer programming instances with controllable properties

  • Davaatseren Baatar
  • Hans D Mittelmann
  • Simon Bowly
  • Kate Smith-Miles
    • Categories (Mixed) Integer Linear Programming, Optimization Software and Modeling Systems Tags , ,

    This paper addresses the problem of generating synthetic test cases for experimentation in linear programming. We propose a method which maps instance generation and instance space search to an alternative encoded space. This allows us to develop a generator for feasible bounded linear programming instances with controllable properties. We show that this method is capable … Read more

    A Novel Matching Formulation for Startup Costs in Unit Commitment

  • Bernard Knueven
  • James Ostrowski
  • Jean-Paul Watson
    • Categories (Mixed) Integer Linear Programming, Scheduling Tags , ,

    We present a novel formulation for startup cost computation in the unit commitment problem (UC). Both the proposed formulation and existing formulations in the literature are placed in a formal, theoretical dominance hierarchy based on their respective linear programming relaxations. The proposed formulation is tested empirically against existing formulations on large-scale unit commitment instances drawn … Read more

    On the Structure of Linear Programs with Overlapping Cardinality Constraints

  • Tobias Fischer
  • Marc E. Pfetsch
    • Categories Branch and Cut Algorithms, Integer Programming Tags , , , ,

    Cardinality constraints enforce an upper bound on the number of variables that can be nonzero. This article investigates linear programs with cardinality constraints that mutually overlap, i.e., share variables. We present the components of a branch-and-cut solution approach, including new branching rules that exploit the structure of the corresponding conflict hypergraph. We also investigate valid … Read more

    Automated timetabling for small colleges and high schools using huge integer programs

  • Joshua S. Friedman
    • Categories Scheduling Tags , ,

    We formulate an integer program to solve a highly constrained academic timetabling problem at the United States Merchant Marine Academy. The IP instance that results from our real case study has approximately both 170,000 rows and columns and solves to near optimality in 12 hours, using a commercial solver. Our model is applicable to both … Read more

    Generalized average shadow prices and bottlenecks

  • Alejandro Crema
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences Tags , , ,

    We present a generalization of the average shadow price in 0-1-Mixed Integer Linear Programming problems and its relation with bottlenecks including the analysis relative to the coefficients matrix of resource constraints. A mathematical programming approach to find the strategy for investment in resources is presented. Citation Escuela de Computación, Facultad de Ciencias, Universidad Central de … Read more