column generation

Robust Branch-Cut-and-Price for the Capacitated Minimum Spanning Tree Problem over a Large Extended Formulation

  • Diogo V. Andrade
  • Ricardo Fukasawa
  • Artur Alves Pessoa
  • Marcus Poggi de Aragão
  • Eduardo Uchoa
  • Jens Lysgaard
    • Categories Cutting Plane Approaches Tags , ,

    This paper presents a robust branch-cut-and-price algorithm for the Capacitated Minimum Spanning Tree Problem (CMST). The variables are associated to $q$-arbs, a structure that arises from a relaxation of the capacitated prize-collecting arborescence probem in order to make it solvable in pseudo-polynomial time. Traditional inequalities over the arc formulation, like Capacity Cuts, are also used. … Read more

    Detecting relevant variables and interactions for classification in Support Vector Machines

  • Emilio Carrizosa
  • Belén Martín-Barragán
  • Dolores Romero Morales
    • Categories Data-Mining Tags , , , ,

    The widely used Support Vector Machine (SVM) method has shown to yield good results in Supervised Classification problems. The Binarized SVM (BSVM) is a variant which is able to automatically detect which variables are, by themselves, most relevant for the classifier. In this work, we extend the BSVM introduced by the authors to a method … Read more

    A Column Generation Approach for Support Vector Machines

  • Emilio Carrizosa
  • Belén Martín-Barragán
  • Dolores Romero Morales
    • Categories Data-Mining Tags , , ,

    The widely used Support Vector Machine (SVM) method has shown to yield good results in Supervised Classification problems. Other methods such as Classification Trees have become more popular among practitioners than SVM thanks to their interpretability, which is an important issue in Data Mining. In this work, we propose an SVM-based method that automatically detects … Read more

    Constraint Reduction for Linear Programs with Many Inequality Constraints

  • Pierre-Antoine Absil
  • André L. Tits
  • William P. Woessner
    • Categories Linear Programming Tags , , , , ,

    Consider solving a linear program in standard form, where the constraint matrix $A$ is $m \times n$, with $n \gg m \gg 1$. Such problems arise, for example, as the result of finely discretizing a semi-infinite program. The cost per iteration of typical primal-dual interior-point methods on such problems is $O(m^2n)$. We propose to reduce … 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

    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

    Decomposition in Integer Programming

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

    Both cutting plane methods and traditional decomposition methods are procedures that compute a bound on the optimal value of an integer linear program (ILP) by constructing an approximation to the convex hull of feasible solutions. This approximation is obtained by intersecting the polyhedron associated with the continuous relaxation, which has an explicit representation, with an … Read more

    Provably Good Solutions for Wavelength Assignment in Optical Networks

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

    In this paper, we study the minimum converter wavelength assignment problem in optical networks. To benchmark the quality of solutions obtained by heuristics, we derive an integer programming formulation by generalizing the formulation of Mehrotra and Trick (1996) for the vertex coloring problem. To handle the exponential number of variables, we propose a column generation … 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

    Interior point methods for large-scale linear programming

  • Kris Farwell
  • John E. Mitchell
  • Daryn Ramsden
    • Categories Linear Programming, Network Optimization, Telecommunications Tags , , ,

    We discuss interior point methods for large-scale linear programming, with an emphasis on methods that are useful for problems arising in telecommunications. We give the basic framework of a primal-dual interior point method, and consider the numerical issues involved in calculating the search direction in each iteration, including the use of factorization methods and/or preconditioned … Read more