column generation

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

    Algorithms over Arc-time Indexed Formulations for Single and Parallel Machine Scheduling Problems

  • Artur Alves Pessoa
  • Marcus Poggi de Aragão
  • Eduardo Uchoa
  • Rosiane Rodrigues
    • Categories Integer Programming, Scheduling Tags , , ,

    This paper presents algorithms for single and parallel identical machine scheduling problems. While the overall algorithm can be viewed as a branch-cut-and-price over a very large extended formulation, a number of auxiliary techniques are necessary to make the column generation effective. Those techniques include a powerful fixing by reduced costs and a new proposed dual … 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

    A conjugate-gradient based approach for approximate solutions of quadratic programs

  • Fredrik Carlsson
  • Anders Forsgren
    • Categories Biomedical Applications, Quadratic Programming Tags , , ,

    This paper deals with numerical behaviour and convergence properties of a recently presented column generation approach for optimization of so called step-and-shoot radiotherapy treatment plans. The approach and variants of it have been reported to be efficient in practice, finding near-optimal solutions by generating only a low number of columns. The impact of different restrictions … Read more

    Adaptive Constraint Reduction for Convex Quadratic Programming

  • Jin Hyuk Jung
  • Dianne P. O'Leary
  • André L. Tits
    • Categories Quadratic Programming Tags , , ,

    We propose an adaptive, constraint-reduced, primal-dual interior-point algorithm for convex quadratic programming with many more inequality constraints than variables. We reduce the computational e ort by assembling, instead of the exact normal-equation matrix, an approximate matrix from a well chosen index set which includes indices of constraints that seem to be most critical. Starting with a … Read more

    Adaptive Constraint Reduction for Training Support Vector Machines

  • Jin Hyuk Jung
  • Dianne P. O'Leary
  • André L. Tits
    • Categories Data-Mining, Quadratic Programming Tags , , ,

    A support vector machine (SVM) determines whether a given observed pattern lies in a particular class. The decision is based on prior training of the SVM on a set of patterns with known classification, and training is achieved by solving a convex quadratic programming problem. Since there are typically a large number of training patterns, … Read more

    Combining segment generation with direct step-and-shoot optimization in intensity-modulated radiation therapy

  • Fredrik Carlsson
    • Categories Biomedical Applications, Constrained Nonlinear Optimization Tags , , ,

    A method for generating a sequence of intensity-modulated radiation therapy step-and-shoot plans with increasing number of segments is presented. The objectives are to generate high-quality plans with few, large and regular segments, and to make the planning process more intuitive. The proposed method combines segment generation with direct step-and-shoot optimization, where leaf positions and segment … Read more

    Selective Gram-Schmidt orthonormalization for conic cutting surface algorithms

  • Vasile L. Basescu
  • John E. Mitchell
    • Categories Linear, Cone and Semidefinite Programming, Nonsmooth Optimization Tags , , ,

    It is not straightforward to find a new feasible solution when several conic constraints are added to a conic optimization problem. Examples of conic constraints include semidefinite constraints and second order cone constraints. In this paper, a method to slightly modify the constraints is proposed. Because of this modification, a simple procedure to generate strictly … Read more

    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