Recent Research Results spring 2003
(course 031019/448)

Course plan

Friday 10.15-12.00 in N037

Teachers

DP: David Pisinger, pisinger@diku.dk

JK: Jakob Krarup, krarup@diku.dk

LMF: Lene M. Favrholdt, lenem@diku.dk

MZ: Martin Zachariasen, martinz@diku.dk

PW: Pawel Winter, pawel@diku.dk

SR: Stefan Røpke, sropke@diku.dk

References

• 14 February
  Introduction Section 1, 2.2, 3.2 (pages 1-5, 7-9, 12-14)
  Paper Section 2 (pages 2-4), moreover Theorem 1 og 2 (pages 7-9), and possibly section 6.1 (pages 14-18).
  Exercises
• T. Achterberg, T. Koch: "Branching on history information" (ps) (pdf)
  
• 28 February
  R. Bent, P. Van Hetenryck: "A two stage hybrid local search for the VRPTW" (ps) (pdf)
  P. Shaw: "Using constraint programming and local search metods for solving VRP" (ps) (pdf)
  Exercises
• 7 March
  J. Clausen and J. Krarup, "Arranging apples in an array", BIT 28 (1988) 552-568.
  J. Clausen and J. Krarup, "A family of bipartite cardinality matching problems solvable in O(n^2) time", Nordic J. Computing 2 (1995) 496- 501.
  T. Illes and J. Krarup, "Maximum C4-free bipartite graphs and knapsack- type relaxations", Pure Mathematics and Applications 10 (1999) 115- 131.
  
• 14 March
  J. Krarup, D. Pisinger, F. Plastria, "Discrete location propblems with push-pull objectives", Discrete Applied Mathematics 123 (2002) 363-378.
  G. Jalal, J. Krarup, "Geometrical solution to the Fermat problem with ar- bitrary weights", August 2002, submitted for publication.
  
• 21 March
  C.L. Monma, B.S. Munson, W.R. Pulleyblank, "Minimum-weight two-connected spanning networks", Mathematical Programming 46 (1990), 153-171.
  E.L. Luebke, J.S. Provan, "On the structure and complexity of the 2-connected Steiner network problem in the plane", Operations Research Letters 26 (2000), 111-116.
  P. Winter, M. Zachariasen, "Structural properties of shortest 2-connected networks in the plane", preliminary draft, 2002.
  
• 28 March
  T. Hagerup "Soring and Searching on the Word RAM.
  Exercises
• 11 April
  P.M. Thompson, H.N. Psaraftis, "Cyclic Transfer Algorithms for Multivehicle Routing and Scheduling Problems", Operations Research 41, No.5 (1993), 935-946.
  I. Dumitrescu, "Constrained Path and Cycle Problems", Ph.D. thesis, Department of Mathematics and Statistics, The University of Melbourne, 2002. --- Only chapter 4 ("The Subset Disjoint Negative Cost Cycle Problems") is relevant for this talk. The chapter can be downloaded using this link.
• 02 May
  D. Pisinger. Dynamic programming on the word RAM, Algorithmica, 35 128-145 (2003).

Seminar topics

• (LMF) L. Favrholdt, M. Nielsen "On-line edge coloring with a fixed number of colors" ps
• (JK) G. Laporte ``m-peripatetic salesman'' pdf
• (JK) S. Pallottino, M.G. Scutella ``A new algorithm for reoptimizing shortest paths when the arc costs change'' pdf
• (DP) M. Crochemore and C. S. Iliopoulos and Y. J. Pinzon and J. F. Reid (2000) ``A fast and practical bit-vector algorithm for the longest common subsequence problem'', ps
• (DP) L. Allison, T.I. Dix (1986), ``A Bit-String Longest-Common-Subsequence Algorithm'' html
• (DGJ) Branch & cut for the vehicle routing problem:
  • Ralphs, Kopman, Pulleyblank & Trotter (2001), "On the Capacitated Vehicle Routing Problem", ps
  • Blasum & Hochstättler (2002), "Application of the Branch and Cut Method to the Vehicle Routing Problem" ps
• (SR) Column generation for the vehicle routing problem with time windows:
  • Desrochers, Desrosiers, Solomon, "A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows", Operations Reasearch 40 No. 2 (1992), 342-354.
• (SR) Well solved set partitioning problem and its application to vehicle routing problems:
  • Ryan, Hjorring, Glover, "Extensions of the Petal Method for Vehicle Routeing",Journal of the Operational Research Society 44 (1993), 289-296
  • Hjorring, "The Vehicle Routing Problem and Local Search Metaheuristics", Ph.D. Thesis, Department of Engineering Science, The University of Auckland, 1995. gzipped ps
• (SR) Heuristics based on subset disjoint negative cost cycle problems:
  • Ahuja, Jha, Orlin, Sharma (2002), "Very Large-Scale Neighborhood Search for the Quadratic Assignment Problem", pdf
  • Frangioni, Necciarai, Scutella, "A multi-exchange neighborhood for minimum makespan machine scheduling problems", Journal of Combinatorial Optimization, to appear, 2003 ps
  • Ahuja, Orlin, Sharma, "A composite very large-scale neighborhood structure for the capacitated minimum spanning tree problem", Operations Research Letters 31 (2003), 185-194, pdf

• Andrea + Lone: S. Pallottino, M.G. Scutella ``A new algorithm for reoptimizing shortest paths when the arc costs change''
• Jack + Oliver + Malene: L. Favrholdt, M. Nielsen "On-line edge coloring with a fixed number of colors"
• Morten: G. Laporte ``m-peripatetic salesman''
• Mads + Jesper: Desrochers, Desrosiers, Solomon, ``A New Optimization Algorithm for the Vehicle Routing Problem with Time Windows''

Credit

• Attend the lectures
• Make 2/3 of the home exercises
• give a seminar at the end of the course

List of attendance

Home Exercises