Applications – OR and Management Sciences

Robustness in Combinatorial Optimization and Scheduling Theory: An Extended Annotated Bibliography

  • Yury Nikulin
    • Categories Combinatorial Optimization, Robust Optimization, Scheduling

    This extended annotated bibliography focuses on what has been published during the last ten years in the area of combinatorial optimization and scheduling theory concerning robustness and other similar techniques dealing with worst case optimization under uncertainty and non-accuracy of problem data CitationChristian-Albrechts University in Kiel, Institute of Production and Logistics, Working paper ArticleDownload View … Read more

    Stabilized Branch-and-cut-and-price for the Generalized Assignment Problem

  • Alexandre Pigatti
  • Marcus Poggi de Aragão
  • Eduardo Uchoa
    • Categories Branch and Cut Algorithms, Meta Heuristics, Scheduling Tags , , ,

    The Generalized Assignment Problem (GAP) is a classic scheduling problem with many applications. We propose a branch-and-cut-and-price for that problem featuring a stabilization mechanism to accelerate column generation convergence. We also propose ellipsoidal cuts, a new way of transforming the exact algorithm into a powerful heuristic, in the same spirit of the cuts recently proposed … Read more

    A genetic algorithm for the resource constrained multi-project scheduling problem

  • José Fernando Gonçalves
  • Jorge Magalhaes-Mendes
  • Mauricio G.C. Resende
    • Categories Meta Heuristics, Scheduling Tags , , ,

    This paper presents a genetic algorithm for the Resource Constrained Multi-Project Scheduling Problem (RCMPSP). The chromosome representation of the problem is based on random keys. The schedules are constructed using a heuristic that builds parameterized active schedules based on priorities, delay times, and release dates defined by the genetic algorithm. The approach is tested on … Read more

    Proximal-ACCPM: a versatile oracle based optimization method

  • Frédéric Babonneau
  • Cesar Beltran
  • Jean-Philippe Vial
  • Alain Haurie
  • Claude Tadonki
    • Categories Applications - OR and Management Sciences, Convex and Nonsmooth Optimization, Optimization Software and Modeling Systems Tags , , , , , ,

    Oracle Based Optimization (OBO) conveniently designates an approach to handle a class of convex optimization problems in which the information pertaining to the function to be minimized and/or to the feasible set takes the form of a linear outer approximation revealed by an oracle. We show, through three representative examples, how difficult problems can be … Read more

    Lower bounds for the earliness-tardiness scheduling problem on single and parallel machines

  • Safia Kedad-Sidhoum
  • Yasmin Rios-Solis
  • Francis Sourd
    • Categories Scheduling Tags , , , ,

    This paper addresses the parallel machine scheduling problem in which the jobs have distinct due dates with earliness and tardiness costs. New lower bounds are proposed for the problem, they can be classed into two families. First, two assignment-based lower bounds for the one-machine problem are generalized for the parallel machine case. Second, a time-indexed … Read more

    A Piecewise Linearization Framework for Retail Shelf Space Management Models

  • Faiz Al-Khayyal
  • Jens Irion
  • J-C Lu
    • Categories (Mixed) Integer Nonlinear Programming, Global Optimization Applications, Marketing

    Managing shelf space is critical for retailers to attract customers and to optimize profit. This paper develops a shelf space allocation optimization model that explicitly incorporates essential in-store costs and considers space- and cross-elasticities. The resultant model maximizes a signomial objective function over linear and bilinear constraints in mixed-integer variables. We propose a piecewise linearization … Read more

    Survivable IP network design with OSPF routing

  • Luciana S. Buriol
  • Mauricio G.C. Resende
  • Mikkel Thorup
    • Categories Meta Heuristics, Network Optimization, Telecommunications Tags , , , ,

    Internet protocol (IP) traffic follows rules established by routing protocols. Shortest path based protocols, such as Open Shortest Path First (OSPF), direct traffic based on arc weights assigned by the network operator. Each router computes shortest paths and creates destination tables used for routing flow on the shortest paths. If a router has multiple outgoing … Read more

    Domination between traffic matrices

  • Gianpaolo Oriolo
    • Categories Combinatorial Optimization, Network Optimization, Telecommunications Tags ,

    A traffic matrix $D^1$ dominates a traffic matrix $D^2$ if $D^2$ can be routed on every (capacitated) network where $D^1$ can be routed. We prove that $D^1$ dominates $D^2$ if and only if $D^1$, considered as a capacity vector, supports $D^2$. We show several generalizations of this result. CitationCentro Vito Volterra, Universita’ di Roma Tor … Read more

    Reduction Tests for the Prize-Collecting Steiner Problem

  • Eduardo Uchoa
    • Categories Applications - OR and Management Sciences, Integer Programming, Telecommunications Tags , ,

    The Prize-Collecting Steiner Problem (PCSP) is a generalization of the classical Steiner Problem in Graphs (SPG) where instead of terminal vertices that must be necessarily connected, one have profits associated to the vertices that must be balanced against the connection costs. This problem is gaining much attention in the last years due to its practical … Read more

    Note: A Graph-Theoretical Approach to Level of Repair Analysis

  • Gregory Gutin
  • Anders Yeo
  • A Rafiey
  • M Tso
    • Categories Graphs and Matroids, Network Optimization, Production and Logistics

    Level of Repair Analysis (LORA) is a prescribed procedure for defence logistics support planning. For a complex engineering system containing perhaps thousands of assemblies, sub-assemblies, components, etc. organized into several levels of indenture and with a number of possible repair decisions, LORA seeks to determine an optimal provision of repair and maintenance facilities to minimize … Read more