Alk. Modul előadások

November 8. --- Gál Boglárka

Heurisztikák és egzakt módszerek az Utazó ügynök problémára.

November 15. --- Kovács Márton

C. Barnhart, E. L. Johnson, G. L. Nemhauser, M. W.P. Savelsbergh, P. H. Vance. ''Branch-and-Price: Column Generation for Solving Huge Integer Programs''​

We discuss formulations of integer programs with a huge number of variables and their solution by column generation methods, i.e. implicit pricing of nonbasic variables to generate new columns or to prove LP optimality at a node of the branch-and-bound tree. We present classes of models for which this approach decomposes the problem, provides tighter LP relaxations and eliminates symmetry. We then discuss computational issues and implementation of column generation, branch-and-bound algorithms, including special branching rules and effient ways to solve the LP relaxation.

November 22. --- Hegel Patrik

D. P. Ronconi and M. S. Kawamura. ''The single machine earliness and tardiness scheduling problem: lower bounds and a branch-and-bound algorithm''​

This paper addresses the single machine scheduling problem with a common due date aiming to minimize earliness and tardiness penalties. Due to its complexity, most of the previous studies in the literature deal with this problem using heuristics and metaheuristics approaches. With the intention of contributing to the study of this problem, a branch-and-bound algorithm is proposed. Lower bounds and pruning rules that exploit properties of the problem are introduced. The proposed approach is examined through a computational comparative study with 280 problems involving different due date scenarios. In addition, the values of optimal solutions for small problems from a known benchmark are provided.

November 29.

Naveen Garg, Jochen Konemann. ''Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems''​

This paper considers the problem of designing fast, approximate, combinatorial algorithms for multicommodity flows and other fractional packing problems. We provide a different approach to these problems which yields faster and much simpler algorithms. Our approach also allows us to substitute shortest path computations for min-cost flow computations in computing maximum concurrent flow and min-cost multicommodity flow; this yields much faster algorithms when the number of commodities is large.

December 6.

Alexandre Belloni. ''Lecture Notes for IAP 2005 Course Introduction to Bundle Methods''​

December 13.

Marjan van den Akker, Han Hoogeveen, Steef van de Velde. ''COMBINING COLUMN GENERATION AND LAGRANGEAN RELAXATION --- AN APPLICATION TO A SINGLE-MACHINE COMMON DUE DATE SCHEDULING PROBLEM​

Column generation has proved to be an effective technique for solving the linear programming relaxation of huge set covering or set partitioning problems, and column generation approaches have led to state-of-the-art so-called branch-and-price algorithms for various archetypical combinatorial optimization problems. Usually, if Lagrangean relaxation is embedded at all in a column generation approach, then the Lagrangean bound serves only as a tool to fathom nodes of the branch-and-price tree. We show that the Lagrangean bound can be exploited in more sophisticated and effective ways for two purposes: to speed up convergence of the column generation algorithm and to speed up the pricing algorithm.

Our vehicle to demonstrate the effectiveness of teaming up column generation with Lagrangean relaxation is an archetypical single-machine common due date scheduling problem. Our comprehensive computational study shows that the combined algorithm is by far superior to two existing purely column generation algorithms: it solves instances with up to 125 jobs to optimality, while purely column generation algorithm can solve instances with up to only 60 jobs.

Ez is választható

Edson L. F. Senne, Luiz A. N. Lorena. ''Stabilizing column generation using Lagrangean/surrogate relaxation: an application to p-median location problems''​

The Lagrangean/surrogate relaxation was explored recently as a faster computational alternative to traditional Lagrangean heuristics. We combine the Lagrangean/surrogate and the traditional column generation approaches to accelerate and stabilize primal and dual bounds obtained using the reduced cost selection. The Lagrangean/surrogate multiplier modifies the reduced cost criterion, providing the selection of new productive columns. The p-median problem is the problem of locating p facilities (medians) on a network such as the sum of all the distances from each demand point to its nearest facility is minimized. Computational tests running p-median instances taken from the literature are presented.