Combinatorial Optimization

Reformulating Linear Programs with Transportation Constraints — with Applications to Workforce Scheduling

  • Tolga Cezik
  • Oktay Gunluk
    • Categories Combinatorial Optimization, Network Optimization Tags , ,

    We study linear programming models that contain transportation constraints in their formulation. Typically, these models have a multi-stage nature and the transportation constraints together with the associated flow variables are used to achieve consistency between consecutive stages. We describe how to reformulate these models by projecting out the flow variables. The reformulation can be more … Read more

    A New Trust Region Technique for the Maximum Weight Clique Problem

  • Stanislav Busygin
    • Categories Approximation Algorithms, Graphs and Matroids Tags , , , , , ,

    A new simple generalization of the Motzkin-Straus theorem for the maximum weight clique problem is formulated and directly proved. Within this framework a new trust region heuristic is developed. In contrast to usual trust region methods, it regards not only the global optimum of a quadratic objective over a sphere, but also a set of … Read more

    Models and Solution Techniques for Frequency Assignment Problems

  • Karen I. Aardal
  • Arie M.C.A. Koster
  • Carlo Mannino
  • Antonio Sassano
  • Stan P.M. van Hoesel
    • Categories Graphs and Matroids, Telecommunications Tags

    Wireless communication is used in many different situations such as mobile telephony, radio and TV broadcasting, satellite communication, and military operations. In each of these situations a frequency assignment problem arises with application specific characteristics. Researchers have developed different modeling ideas for each of the features of the problem, such as the handling of interference … Read more

    The Maximum Box Problem and its Application to Data Analysis

  • Jonathan Eckstein
  • Peter L. Hammer
  • Ying Liu
  • Mikhail S. Nediak
  • Bruno Simeone
    • Categories Combinatorial Optimization, Data-Mining Tags , ,

    Given two finite sets of points $X^+$ and $X^-$ in $\R^n$, the maximum box problem consists in finding an interval (“box”) $B=\{x : l \leq x \leq u\}$ such that $B\cap X^-=\emptyset$, and the cardinality of $B\cap X^+$ is maximized. A simple generalization can be obtained by instead maximizing a weighted sum of the elements … Read more

    Branch and cut based on the volume algorithm: Steiner trees in graphs and max-cut

  • Francisco Barahona
  • Lazslo Ladanyi
    • Categories Branch and Cut Algorithms Tags , , ,

    We present a Branch-and-Cut algorithm where the Volume Algorithm is applied to the linear programming relaxations arising at each node of the search tree. This means we use fast approximate solutions to these linear programs instead of exact but slower solutions given by the traditionally used dual simplex method. Our claim is that such a … Read more

    A Laplace transform algorithm for the volume of a convex polytope

  • Jean-Bernard Lasserre
  • Eduardo Santillan Zeron
    • Categories Polyhedra

    We provide two algorithms for computing the volume of the convex polytope $\Omega:=\{x\in \R^n_+ \,|\,Ax\leq b\}$, for $A\in\R^{m\times n}, b\in\R^n$. The computational complexity of both algorithms is essentially described by $n^m$, which makes them especially attractive for large $n$ and relatively small $m$, when the other methods with $O(m^n)$ complexity fail. The methodology which differs … Read more

    Power transmission network design by a greedy randomized adaptive path relinking approach

  • S. Binato
  • Mauricio G.C. Resende
  • Haroldo Faria Jr.
    • Categories Applications - Science and Engineering, Meta Heuristics

    This paper illustrates results obtained by a new metaheuristic approach, Greedy Randomized Adaptive Path Relinking, applied to solve static power transmission network design problems. This new approach consists of a generalization of GRASP concepts to explore different trajectories between two Citation AT&T Labs Research Report, December 2001 Submitted to PSCC’02. Article Download View Power transmission … Read more

    Using Heuristics to Solve the Dedicated Aircraft Recovery Problem

  • Jens Clausen
  • Kim R. Soerensen
  • Jesper Larsen
  • Michael Loeve
    • Categories Airline Optimization, Meta Heuristics Tags , , , , ,

    The Dedicated Aircraft Recovery Problem (DARP) involves decisions concerning aircraft to flight assignments in situations where unforeseen events have disrupted the existing flight schedule, e.g. bad weather causing flight delays. The dedicated aircraft recovery problem aims to recover these flight schedules through a series of reassignments of aircraft to flights, delaying of flights and cancellations … Read more

    Pivot, Cut, and Dive: A Heuristic for 0-1 Mixed Integer Programming

  • Jonathan Eckstein
  • Mikhail S. Nediak
    • Categories (Mixed) Integer Linear Programming, Meta Heuristics, Parallel Algorithms Tags , ,

    We present a heuristic method for general 0-1 mixed integer programming, intended for eventual incorporation into parallel branch-and-bound methods for solving such problems exactly. The core of the heuristic is a rounding method based on simplex pivots, employing only gradient information, for a strictly concave, differentiable merit function measuring integer feasibility. When local minima of … Read more

    Parallel GRASP with path-relinking for job shop scheduling

  • Renata M. Aiex
  • S. Binato
  • Mauricio G.C. Resende
    • Categories Meta Heuristics, Scheduling Tags , , , , ,

    In the job shop scheduling problem (JSP), a finite set of jobs is processed on a finite set of machines. Each job is required to complete a set of operations in a fixed order. Each operation is processed on a specific machine for a fixed duration. A machine can process no more than one job … Read more