branch-and-price

Modeling and Solving Location Routing and Scheduling Problems

  • Z. Akca
  • Ted K. Ralphs
  • R.T. Berger
    • Categories 0-1 Programming, Network Optimization, Production and Logistics Tags , , ,

    This paper studies location routing and scheduling problems, a class of problems in which the decisions of facility location, vehicle routing, and route assignment are optimized simultaneously. For a version with capacity and time restrictions, two formulations are presented, one graph-based and one set-partitioning-based. For the set-partitioning-based formulation, valid inequalities are identified and their effectiveness … Read more

    A Branch-and-Price Algorithm for Combined Location and Routing Problems Under Capacity Restrictions

  • Z. Akca
  • Ted K. Ralphs
  • R.T. Berger
    • Categories (Mixed) Integer Linear Programming, Combinatorial Optimization, Transportation Tags , , ,

    We investigate the problem of simultaneously determining the location of facilities and the design of vehicle routes to serve customer demands under vehicle and facility capacity restrictions. We present a set-partitioning-based formulation of the problem and study the relationship between his formulation and the graph-based formulations that have been used in previous studies of this … Read more

    Provisioning Virtual Private Networks under traffic uncertainty

  • Aysegul Altin
  • Edoardo Amaldi
  • Pietro Belotti
  • Mustafa C. Pinar
    • Categories Network Optimization, Robust Optimization, Telecommunications Tags , , , , , ,

    We investigate a network design problem under traffic uncertainty which arises when provisioning Virtual Private Networks (VPNs): given a set of terminals that must communicate with one another, and a set of possible traffic matrices, sufficient capacity has to be reserved on the links of the large underlying public network so as to support all … Read more

    Finding optimal realignments in sports leagues using a branch-and-cut-and-price approach

  • Xiaoyun Ji
  • John E. Mitchell
    • Categories Applications - OR and Management Sciences, Branch and Cut Algorithms Tags , , , ,

    The sports team realignment problem can be modelled as $k$-way equipartition: given a complete graph $K_{n}=(V,E)$, with edge weight $c_{e}$ on each edge, partition the vertices $V$ into $k$ divisions that have exactly $S$ vertices, so as to minimize the total weight of the edges that have both endpoints in the same division. In this … Read more

    Decomposition and Dynamic Cut Generation in Integer Linear Programming

  • M.V. Galati
  • Ted K. Ralphs
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Cutting Plane Approaches Tags , , , ,

    Decomposition algorithms such as Lagrangian relaxation and Dantzig-Wolfe decomposition are well-known methods that can be used to generate bounds for mixed-integer linear programming problems. Traditionally, these methods have been viewed as distinct from polyhedral methods, in which bounds are obtained by dynamically generating valid inequalities to strengthen the linear programming relaxation. Recently, a number of … Read more

    The Integration of an Interior-Point Cutting-Plane Method within a Branch-and-Price Algorithm

  • Samir Elhedhli
  • Jean-Louis Goffin
    • Categories Applications - OR and Management Sciences, Integer Programming Tags , , , ,

    This paper presents a novel integration of interior point cutting plane methods within branch-and-price algorithms. Unlike the classical method, columns are generated at a “central” dual solution by applying the analytic centre cutting plane method (ACCPM) on the dual of the full master problem. First, we introduce improvements to ACCPM. We propose a new procedure … Read more