Branch-and-price Algorithm (branch-and-price + algorithm)

Distribution by Scientific Domains
Mathematics and Statistics100%

Selected Abstracts

A branch-and-price algorithm for a targeting problem

NAVAL RESEARCH LOGISTICS: AN INTERNATIONAL JOURNAL, Issue 7 2007
Ojeong Kwon
Abstract In this paper, we consider a new weapon-target allocation problem with the objective of minimizing the overall firing cost. The problem is formulated as a nonlinear integer programming model, but it can be transformed into a linear integer programming model. We present a branch-and-price algorithm for the problem employing the disaggregated formulation, which has exponentially many columns denoting the feasible allocations of weapon systems to each target. A greedy-style heuristic is used to get some initial columns to start the column generation. A branching strategy compatible with the pricing problem is also proposed. Computational results using randomly generated data show this approach is promising for the targeting problem. © 2007 Wiley Periodicals, Inc. Naval Research Logistics, 2007 [source]

A branch-and-price algorithm for parallel machine scheduling with time windows and job priorities

NAVAL RESEARCH LOGISTICS: AN INTERNATIONAL JOURNAL, Issue 1 2006
Jonathan F. Bard
Abstract This paper presents a branch-and-price algorithm for scheduling n jobs on m nonhomogeneous parallel machines with multiple time windows. An additional feature of the problem is that each job falls into one of , priority classes and may require two operations. The objective is to maximize the weighted number of jobs scheduled, where a job in a higher priority class has "infinitely" more weight or value than a job in a lower priority class. The methodology makes use of a greedy randomized adaptive search procedure (GRASP) to find feasible solutions during implicit enumeration and a two-cycle elimination heuristic when solving the pricing subproblems. Extensive computational results are presented based on data from an application involving the use of communications relay satellites. Many 100-job instances that were believed to be beyond the capability of exact methods, were solved within minutes. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2006 [source]

k -Splittable delay constrained routing problem: A branch-and-price approach

NETWORKS: AN INTERNATIONAL JOURNAL, Issue 1 2010
Jérôme Truffot
Abstract Routing problems, which include a QoS-based path control, play a key role in broadband communication networks. We analyze here an algorithmic procedure based on branch-and-price algorithm and on the flow deviation method to solve a nonlinear k -splittable flow problem. The model can support end-to-end delay bounds on each path and we compare the behavior of the algorithm with and without these constraints. The trade-off between QoS guarantees and CPU time is clearly established and we show that minimizing the average delay on all arcs will yield solutions close to the optimal one at a significant computational saving. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010 [source]