(Mixed) Integer Linear Programming

Finding the best root node strategy for the approximation of the time-indexed bound in min-sum scheduling

  • Yunpeng Pan
  • Leyuan Shi
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization

    We identify the best root node strategy for the approximation of the time-indexed bound in min-sum scheduling by sorting through various options that involve the primal simplex, dual simplex, and barrier methods for linear programming, the network simplex method for network flow problems, and Dantzig-Wolfe decomposition and column generation. CitationSubmitted for publication.ArticleDownload View PDF

    Facets of Two-Dimensional Infinite Group Problems

  • Santanu S. Dey
  • Jean-Philippe P. Richard
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches

    In this paper, we lay the foundation for the study of the two-dimensional mixed integer infinite group problem (2DMIIGP). We introduce tools to determine if a given continuous and piecewise linear function over the two-dimensional infinite group is subadditive and to determine whether it defines a facet. We then present two different constructions that yield … Read more

    A new model and a computational study for Demand-wise Shared Protection

  • Claus G. Gruber
  • Arie M.C.A. Koster
  • Sebastian Orlowski
  • Adrian Zymolka
  • Roland Wessäly
    • Categories (Mixed) Integer Linear Programming, Network Optimization, Telecommunications Tags , , ,

    This report combines the contributions to INOC 2005 (Wessälly et al., 2005) and DRCN 2005 (Gruber et al., 2005). A new integer linear programming model for the end-to-end survivability concept deman d-wise shared protection (DSP) is presented. DSP is based on the idea that backup capacity is dedicated to a particular demand, but shared within … Read more

    Robust DWDM Routing and Provisioning under Polyhedral Demand Uncertainty

  • Oya Ekin Karasan
  • Mustafa C. Pinar
  • Hande Yaman
    • Categories (Mixed) Integer Linear Programming, Robust Optimization, Telecommunications Tags , , , ,

    We present mixed integer linear programming models that are robust in the face of uncertain traffic demands known to lie in a certain polyhedron for the problem of dense wavelength division multiplexing network routing and provisioning at minimal cost. We investigate the solution of the problem in a set of numerical experiments for two models … Read more

    In Situ Column Generation for a Cutting-Stock Problem

  • Jon Lee
    • Categories (Mixed) Integer Linear Programming, (Mixed) Integer Nonlinear Programming, Production and Logistics Tags , ,

    Working with an integer bilinear programming formulation of a one-dimensional cutting-stock problem, we develop an ILP-based local-search heuristic. The ILPs holistically integrate the master and subproblem of the usual price driven pattern-generation paradigm, resulting in a unified model that generates new patterns in situ. We work harder to generate new columns, but we are guaranteed … Read more

    Manufacturer’s Mixed Pallet Design Problem

  • Alper Sen
  • Hande Yaman
    • Categories (Mixed) Integer Linear Programming, Production and Logistics Tags , , ,

    We study a problem faced by a major beverage producer. The company produces and distributes several brands to various customers from its regional distributors. For some of these brands, most customers do not have enough demand to justify full pallet shipments. Therefore, the company decided to design a number of mixed or “rainbow” pallets so … Read more

    On the equivalence of the max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems

  • Yunpeng Pan
  • Leyuan Shi
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Scheduling

    New observations are made about two lower bound schemes for single-machine min-sum scheduling problems. We find that the strongest bound of those provided by transportation problem relaxations can be computed by solving a linear program. We show the equivalence of this strongest bound and the bound provided by the LP relaxation of the time-indexed integer … Read more

    A branch and cut algorithm for solving the linear and quadratic integer programming problems

  • Fei Pusheng
  • Yan Zizong
  • Wan Zhongping
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Integer Programming Tags , , , ,

    This paper first presents an improve cutting plane method for solving the linear programming problems, based on the primal simplex method with the current equivalent facet technique, in which the increment of objection function is allowed as a pivot variable to decide the search step size. We obtain a strong valid inequality from the objective … Read more

    A Case Study of Joint Online Truck Scheduling and Inventory Management for Multiple Warehouses

  • Christoph Helmberg
  • Stefan Röhl
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Convex Optimization Tags , , , , , , ,

    For a real world problem — transporting pallets between warehouses in order to guarantee sufficient supply for known and additional stochastic demand — we propose a solution approach via convex relaxation of an integer programming formulation, suitable for online optimization. The essential new element linking routing and inventory management is a convex piecewise linear cost … Read more

    Linear Programming Lower Bounds for Minimum Converter Wavelength Assignment in Optical Networks

  • Arie M.C.A. Koster
  • Adrian Zymolka
    • Categories (Mixed) Integer Linear Programming, Graphs and Matroids, Telecommunications Tags , , ,

    In this paper, we study the conflict-free assignment of wavelengths to lightpaths in an optical network with the opportunity to place wavelength converters. To benchmark heuristics for the problem, we develop integer programming formulations and study their properties. Moreover, we study the computational performance of the column generation algorithm for solving the linear relaxation of … Read more