Udvalgte Emner i Kombinatorisk Optimering, Kursus Nr. 448

seneste opdatering: 03.05.04

Lærere:

Jakob Krarup (kursusansvarlig)
David Pisinger
Stefan Røpke
Mikkel Muhldorff Sigurd
Pawel Winter (webmaster)
Martin Zachariasen (supplerende webmaster)

Forelæsninger

Dato	Forelæser	Titel	Link	Opgaver	Andet
06.02	JK	The greedy algorithm: some solvable cases	Abstract		handout
13.02	JK	Ingredients of locational analyses	Abstract		handout
20.02	MZ	Two-connected Steiner networks	Paper		Slides
27.02	PW	Linear Programming with 2 and 3 Variables in Linear Time	Referencer	Gør rede for Chan's O(nlogh) algoritme for konvekse hylstre i planen, gerne støttet af velvalgte eksempler og figurer (højst 5 sider:-). LINK Projektforslag: implementer Jarvis' march og Chan's algoritme bl.a. med henblik på en analyse af deres effektivitet	Plancher-LP med 2 variable Plancher-LP v.h.a. prune & search Plancher-CH v.h.a. prune & search (kun 24-29 er relevant)
05.03	SR	Branch and Cut methods for The Capacitated Vehicle Routing Problem	Slides fra forelæsning - Opdateret Two Commodity Flow Model	Opgaver lp program	Artikel uddelt (kontakt SR hvis du ikke har fået den).
12.03	DP	Interior point methods - an introduction	Slides fra forelæsning (ps pdf)	Opgaver ps pdf Algoritme pdip.m	Illes, Tarlaky "Pivot versus interior point methods" (pdf)
19.03	DP	Semidefinite programming - an introduction	Slides fra forelæsning (ps pdf)	Opgaver ps pdf	(side 1-7, 13-15, 27-29, 34-35, 38-39, 41-42) C. Helmberg. "Semidefinite Programming for Combinatorial Optimization" (pdf)
26.03	MZ+PW	Flexibility of Steiner trees in uniform orientation metrics		Giv et detaljeret bevis af sætning 4.1 i Brazil et al. "Canonical forms and Algorithms for Steiner Trees in Uniform Orientation Metrics". Gør specielt rede for at sætningen gælder når lambda et et multiplum af 3.
02.04	SR	Solving the Vehicle Routing Problem with Time Windows to optimality - recent advances	Slides fra forelæsning pdf - ps (4 slides per side)	Opgaver pdf ps	Jesper Larsens Ph.d. afhandling. Læs kapitel 3 og 4 samt afsnit 2.1. pdf "Solomon problemer" . Tabel over VRPTW problemer løst til optimalitet. Tabellen er ikke helt up-to-date.
16.04	JK	Optimization with push - pull objectives	Abstract		handout
23.04	MMS	Topics in Column Generation	Slides	Exercises
30.04	Seminar	"On Torricelli's geometrical solution ... " (Egil Hauge Larsen, Lone Marner)
14.05	Seminar	"The shortest path problem with resource constraints ... " (Emil Frisendal, Bjørn Petersen) "Lagrangean duality applied on VTPTW" (Mads Jepsen, Simon Spoorendonk) "0.878 approximation algorithms for MAX CUT and MAX 2SAT" (Peter Krogh + ?). Note: Peter Krogh er parat til at optræde alene.
21.05	Seminar	"Simple efficient solutions for semidefinite programming" (Tommy Clausen, Morten Nielsen) "Construction of minimum-weight spanners" (Allan Nordlunde Hjorth, Kenneth Hvam) "Dial-a-ride ..." (Rasmus Resen Amossen)

ret til ændringer forbeholdes

Seminaremner

J.-F. Cordeau, A Branch-and-Cut Algorithm for the Dial-a-Ride Problem, 2003. (ps)
S. Irnich, D. Villeneuve, The Shortest Path Problem with Resource Constraints and k-Cycle Elimination for k>=3, 2003. (ps)

Deltagere, fremmøde og godkendte opgaver

x=tilstede, G=fuld besvarelse, g=halv besvarelse, a=afleveret

Navn

6/2

13/2

20/2

27/2

5/3

12/3

19/3

26/3

2/4

16/4

23/4

30/4

14/5

21/5

Morten Nielsen

x-G

Dennis Hansen

Rasmus Resen Amossen

x-G

Jacob Mads Schmieder Zwicky

Kenneth Lyneborg Hvam

x-G

x-g

x-G

Bjørn Petersen

x-G

x-g

x-G

Egil Hauge Larsen

x-G

Simon Spoorendonk

x-G

x-g

x-G

Emil Soelberg Frisendal

x-G

x-g

x-G

Allan Nordlunde Hjorth

x-G

Malene Nordlund Larsen

Jens Blaabjerg

Tommy Clausen

x-G

Peter Krogh

x-G

x-g

x-G

Mads Jepsen

x-G

Line B. Reinhardt

Morten H. Pagh

x-G

Thomas Antonsen

x-G

Lone Marner

x-G

x-g

Xin Yao

x-G

The greedy algorithm: some solvable cases
-----------------------------------------

The greedy algorithm GREEDY goes in each step for maximum improvement in
some well-defined sense and consists solely of such steps. Depending on the
problem type, however, GREEDY may in some cases be an _exact_ algorithm,
that is, optimality of the solution returned is guaranteed.
     Embarking from a case study dealing with arrangements of apples, a
greedy algorithm for the bipartite cardinality matching problem has been
devised. This O(n^2) algorithm will either find a perfect matching or i-
dentify a so-called 4-block which is a (2x2)-submatrix of ones only.
     A 0-1 matrix is called 4-block-free if a 4-block nowhere appears. For
given n, what is the largest number of ones a 4-block-free (nxn)-matrix
can have? We note initially that a conclusive answer, valid for all n,
would also settle the classical and generally unanswered question as to
the existence of a so-called finite projective plane of a given order. We
investigate furthermore a knapsack-type relaxation of a 0-1 programming
formulation of the problem, account for its solution properties and ad-
dress issues as to the realizability in terms of 0-1 matrices of the solu-
tions found. Along the way, some surprisingly simple proofs of earlier
results are provided. Also a new characterization of finite projective
planes is given.
     The above analysis has been complemented by a series of computational
experiments with various implementations of GREEDY. The most conspicuous
result obtained is a projective plane of order 256 (corresponding to n =
65,793) which can be represented on a single screen picture as a matrix of
colourful submatrices, each of size 16 by 16. Among the by-products are
orthogonal latin squares of orders 2^2^k, k=1,2,..., a nice embroidery
pattern and the rediscovery of certain Moire patterns, a well-studied
phenomenon in optics.

References
----------

J. Clausen, J. Krarup, "Arranging apples in an array", BIT 28 (1988) 552-568.

J. Clausen, J. Krarup, "A family of bipartite cardinality matching problems
solvable in O(n^2) time", Nordic Journal of Computing 2 (1995) 496-501.

T. Illes, J. Krarup, "Maximum 4-block-free matrices and knapsack-type
relaxations", Mathematics in Optimization 8 (1999) 1-17.

**************************************************************************

Ingredients of locational analysis

The four so-called _prototype problems_, p-MEDIAN, p-CENTER, Uncapacitated
Facility Location Problem, and Quadratic Assignment, are reviewed. Also
various extensions are accounted for.

Reference
---------

J. Krarup, P.M. Pruzan, "Ingredients of Locational Analysis", Ch. 1 in (P.
B.Mirchandani og R.L. Francis, eds.) Discrete Location Theory, Wiley-Inter-
science, New York (1990) 1-54.

**************************************************************************
Push-pull objectives in combinatorial optimisation
--------------------------------------------------

The models within operational research concerned with locational decisions
mostly either consider only the positive effects, pulling the facilities
towards demand, or only negative effects, pushing the facilities away from
the places affected by the facilities' nearness. In real-world situations
both of these opposing forces are at work. We present two push-pull mo-
dels incorporating both types of effects simultaneously:

a) Geometrical solution to the Fermat problem with arbitrary weights

The prime motivation for the present study is a famous problem, allegedly
first formulated in 1643 by Fermat, and the so-called Complementary Prob-
lem (CP), proposed but incorrectly solved in 1941 by Courant and Robbins.
For a given triangle, Fermat asks for a fourth point such that the sum of
its euclidean distances, each weighted by +1, to the three given points is
minimized. CP differs from Fermat in that the weight associated with one
of these points is -1 instead of +1.
   The geometrical approach suggested in 1998 by Krarup for solving CP is
here extended to cover any combination of positive and negative weights
associated with the vertices of a given triangle. Among the by-products
are surprisingly simple correctness proofs of the geometrical contruct-
ions of Torricelli (around 1645), Cavalieri (1647), Viviani (1659), Simp-
son (1750), and Martelli (1998). Furthermore, alternative proofs of Ptole-
my's Theorem (around A.D. 150) and an observation by Heinen (1834) are
provided.

b) A linear algorithm for the "pos/neg-weighted" 1-median problem on a
    cactus

The 1-median problem in a network asks for a vertex minimizing the sum of
the weighted shortest path distances from itself to all other vertices,
each associated with a certain positive weight. We allow for negative
weights as well and devise an exact algorithm for the resulting "pos/neg-
weighted" problem defined on a cactus, that is, a network in which no two
cycles have more than one vertex in common. The algorithm appears to run
in linear time since each vertex need only be considered exactly once.

References
----------

R.E. Burkard, J. Krarup, "A linear algorithm for the pos/neg-weighted
1-median problem on a cactus", Computing 60 (1998) 193-215.

G. Jalal, J. Krarup, "Geometrical solution to the Fermat problem with ar-
bitrary weights", Annals of Operations Research 123 (2003) 67-104.

J. Krarup, D. Pisinger, F. Plastria, "Discrete location problems with
push-pull objectives", Discrete Applied Mathematics 123 (2002) 363-378.

**************************************************************************

Linear Programming with 2 and 3 Variables in Linear Time

N. Megiddo, Linear programming in linear time when the dimension is fixed, J.ACM 31 (1984) 114-127
D.G. Kirkpatrick and R. Seidel, The ultimate planar convex hull algorithm?, SIAM J. Comput. 15 (1986) 287-299.
T.M. Chan, Output-sensitive results on convex hulls, extreme points and related problems, Discrete Comput. Geom. 16 (1996) 369-387