Deltagere, fremmøde og godkendte opgaver

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.

Pickup and Delivery Problems

Pickup and Delivery Problems are a class of optimization problems that models real life transportation problems. This lecture focuses on solving the problem to optimality using column generation techniques, but other solution approaches will also be described and compared to the column generation technique.