Results 261 to 270 of about 44,963 (303)

CP Based Branch-and-Price

2004
In this chapter, we present an overview of constraint programming based branch-and-price, a combined integer programming-constraint programming algorithm used to solve combinatorial problems formulated with a huge number of variables. We discuss a number of applications and implementation issues.
Kelly Easton, George Nemhauser, Michael Trick   +2 more
openaire   +1 more source

Sorting Permutations by Reversals Through Branch-and-Price

INFORMS Journal on Computing, 2001
We describe an exact algorithm for the problem of sorting a permutation by the minimum number of reversals, originating from evolutionary studies in molecular biology. Our approach is based on an integer linear programming formulation of a graph-theoretic relaxation of the problem, calling for a decomposition of the edge set of a bicolored graph into ...
CAPRARA A., LANCIA, Giuseppe, NG S. K.
openaire   +2 more sources

Branch-and-Price Guided Search

2012
When solving large-scale integer programming (IP) models, there are the conflicting goals of solution quality and solution time. Solving realistic-size instances of many problems to optimality is still beyond the capability of state-of-the-art solvers.
Mike Hewitt, George L. Nemhauser, Martin Savelsbergh   +2 more
openaire   +1 more source

Designing WDM Optical Networks Using Branch-and-Price

Journal of Mathematical Modelling and Algorithms in Operations Research, 2013
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Raghavan, S., Stanojević, Daliborka
openaire   +2 more sources

A Branch-and-Price Algorithm for the Multiple Knapsack Problem

INFORMS Journal on Computing, 2022
The multiple knapsack problem is a well-studied combinatorial optimization problem with several practical and theoretical applications. It consists of packing some subset of n items into m knapsacks such that the total profit of the chosen items is maximum. A new formulation of the problem is presented, where a Lagrangian relaxation is derived, and we
Olivier Lalonde, Jean-François Côté, Bernard Gendron   +2 more
openaire   +2 more sources

Improving Branch-and-Price for Parallel Machine Scheduling

2014
In this paper we present a hybrid exact-heuristic method to improve a branch-and-price algorithm to solve the unrelated parallel machines with sequence-dependent setup times scheduling problem. As most of the computational time in the column generation (CG) process is spent in subproblems, two new heuristics to solve the subproblems are embedded in the
Lopes, Manuel, Alvelos, Filipe Pereira e, Lopes, Henrique Daniel Oliveira   +2 more
openaire   +2 more sources

Accelerating the Branch-and-Price Algorithm Using Machine Learning

European Journal of Operational Research, 2018
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Roman Václavík, Antonín Novák, Přemysl Šůcha, Zdeněk Hanzálek   +3 more
openaire   +2 more sources

A branch‐and‐price algorithm for switch‐box routing

Networks, 2002
AbstractRouting in VLSI design concerns the wiring of a chip after the logical modules have been placed. A subproblem occurring in VLSI design is switch‐box routing. Switch‐box routing can be formulated as the problem of packing Steiner trees in a grid graph. The only previous exact solution method for switch‐box routing uses a branch‐and‐cut approach.
Jørgensen, David Grove, Meyling, Morten
openaire   +2 more sources

A branch-and-price algorithm for scheduling sport leagues

Journal of the Operational Research Society, 2009
Round robin tournaments (RRTs) cover a huge variety of different types of sports league schedules arising in practice. The focus in this paper is on single RRTs where scheduling is temporally constrained, which means that matches have to be scheduled in a given minimum number of periods. We consider a set T of n teams.
D. Briskorn, A. Drexl
openaire   +1 more source

Optimal shift scheduling: A branch-and-price approach

Naval Research Logistics, 2000
Summary: We present a branch-and-price technique for optimal staff scheduling with multiple rest breaks, meal break, and break windows. We devise and implement specialized branching rules suitable for solving the set covering type formulation implicitly, using column generation.
Mehrotra, Anuj, Murphy, Kenneth E., Trick, Michael A.   +2 more
openaire   +2 more sources