Topic: The Use of Linear Programming in Combinatorial Optimization

- Sequential insertion algorithm
- Parallel insertion algorithm
- Savings algorithm

Topic: Scheduling with deadlines

In this presentation, we concentrate on deterministic on-line algorithms for scheduling problems where jobs arrive over time, and all job characteristics become known at their arrival. For several machine environments we present lower bounds on the worst-case ratio of any on-line algorithm. Furthermore, for some of these problems we present on-line algorithms with a worst-case ratio equal to the lower bound.

No seminar due to ALCOM-IT workshop and WG Najaarssymposium.

Topic: Beautiful and Fast: New Minimum Cut Algorithms

The technical report NECI-TR-96-132 describing these results in detail is available via URL http://www.neci.nj.nec.com/homepages/avg.html. It is joint work with Chandra Chekuri, David Karger, Matt Levine, and Cliff Stein.

- Applying Savings with more restrictions. We present techniques how to adapt the well known Savings Heuristic for the VRP such that it can cope with different restrictions.
- Scheduling and Vehicle Routing. We consider the problem of vehicle routing between a number of sites, where only one vehicle at a time is allowed to (un)load at a location.
- HUB-problem. We consider the problem of having a number of locations with a matrix with amounts, to be transported between them, and a number of side-constraints.

Traditionally, vehicle and crew scheduling have been dealt with in a sequential manner, were vehicle schedules are determined before the crew schedules. We discuss potential benefits of integration and provide an overview on the scarce literature which considers only partial integration. Our approach is new in the sense that we consider complete integration of vehicle and crew scheduling. Concerning the vehicle scheduling aspect of our approaches, we only consider the basic single depot vehicle scheduling problem. This makes our approach in principle applicable for bus and driver scheduling.

We also propose a new approach for scheduling crews independent of vehicles. This approach can serve as a measure of the potential benefit of integration, that is, it may be beneficial to integrate if the solution value of the traditional sequential approach differs much from the solution value of the independent approach. We discuss several new mathematical formulations for the approaches considered in this chapter, and consider corresponding relaxations and optimization based heuristic algorithms. These algorithms rely on column generation applied to set partitioning type of models. The talk is concluded with a computational study which shows the applicability of the proposed techniques in practice, and addresses the effectiveness of integration when compared to a sequential approach.

*** EXTRA SEMINAR ***

(Joint work with Danny Raz.)

In de voordracht wordt ingegaan op diverse problemen die men hierbij ontmoet, zoals het formuleren van veiligheidscriteria, het kwantificeren van informatieverlies, het optimaal modificeren van de data. Voor een belangrijk deel betreft het problemen die momenteel onderwerp van studie zijn. Het doel van de voordracht is om het - buiten de wereld van statistische bureau's - betrekkelijk onbekende terrein van de statistische beveiliging te schetsen, en daarbij in het bijzonder te wijzen op het multidisciplinaire karakter van een aantal kernproblemen.

Topic: On an integer multicommodity flow problem from the airplane industry

This is joint work with Han Hoogeveen and Gerhard Woeginger.

Topic: An Optimization Algorithm for Maximum Independent Set with Applications in Map Labelling

We present an optimization algorithm for finding maximum independent sets and apply it to independent set instances arising from map labelling. The algorithm uses a new technique for setting variables in the branch and bound tree that implicitly exploits the Euclidean nature of the independent set problems arising from map labelling. Computational experiments show that this technique is very successful in controlling the size of the branch and bound tree.

This is a C code for computing the complex of maximal lattice free bodies for an n+1 by n matrix.

This problem can be modelled as a integer program (IP).
The standard integer programming formulation of this
problem has the property that the ratio between the
optimal IP solution and the optimal solution to the
linear program (LP) obtained by removing the integrality
constraints on the variables can be as bad as
min *(|E|, D)/2*. (This is in contrast to the
problem with uniform capacities, for which a 2-approximation
is obtainable using the LP relaxation).
We introduce additional inequalities
to the linear program that are satisfied by all integer
solutions and show that, for a special
class of graph, these improve the worst case
IP/LP ratio to 2 if there is only one communicating
pair, and to at least 3 if there is more than one communicating
pair. We also show that these inequalities reduce the
ratio in general graphs. Our proof technique extends
to some more general covering problems.

We also describe approximate separation algorithms for these inequalities to obtain polynomial time approximation algorithms with a guarantee that matches our improved bound on the IP/LP ratio. Our algorithms extend to the multicover problem (the generalization of the set cover problem when each element must be covered multiple times) and improve upon the best previous approximation guarantees for this problem.

This is work in progress joint with Bob Carr, Cindy Phillips, and Vitus Leung, all of Sandia National Laboratories, Albuquerque, USA.

In deze voordracht zal ik ingaan op een specifiek dienstrooster probleem, wiskundige modelleringen geven, en in gaan op het ontwerp van heuristieken.

The point labeling problem can be formulated as a special case of the independent set problem. For general graphs there does not exist an approximation scheme for the independent set problem. However, for the point labeling problem we can give a polynomial-time approximation scheme and a simple and efficient factor-½ approximation algorithm for the slider and fixed position models. Finally we present experimental results of the factor-½ approximation algorithm to compare the different models in practice and to compare this algorithm to other algorithms suggested in the literature.

We develop a randomized algorithm for the *k*-level facility location
problem that is guaranteed to find a feasible solution of expected cost
within a factor of 3 of the optimum cost. The algorithm is a randomized
rounding procedure that uses an optimal solution of a linear
programming relaxation and its dual to make a random choice of
facilities to be opened.
We show how this algorithm can be derandomized to yield a
3-approximation algorithm.

This is joint work with F. Chudak and D.B. Shmoys

Topic: | Linkage Information Processing In Distribution Estimation Algorithms |

Room: | CGN B205a, Uithof Campus |

Speaker: | Peter Bosman |

Topic: | Minimizing Total Weighted Tardiness in a Generalized Job Shop |

Room: | CGN B205a, Uithof Campus |

Speaker: | Koen de Bontridder, Eindhoven University of Technology |

We use a tabu search algorithm to search for the order in which the operations are processed on each machine. Given an execution order of the operations on each machine, we determine optimal starting times by solving a maximum cost flow problem. The starting times could also be determined by solving a single source longest path tree in an acyclic graph. We show that it only costs a small amount of extra computation time to determine the solution of the maximum cost flow problem.

The solution of the maximum cost flow problem is used to determine the neighborhood for our tabu search algorithm. All sequences in our neighborhood are obtained by swapping certain pairs of adjacent operations. We show that only swaps that possess a certain property can improve the current solution; if no such swap is available in the neighborhood, then the current solution is optimal. We finally give extensive computational results.

Topic: | Proactieve Veiligheid |

Room: | CGN C009, Uithof Campus |

Speaker: | Gerard Tel |

Topic: | Restarts can help in on-line scheduling |

Room: | CGN C009, Uithof Campus |

Speaker: | Han Hoogeveen |

Topic: | Pathwidth of planar graphs |

Room: | CGN B205a, Uithof Campus |

Speaker: | Fedor Fomin, St.Petersburg State University |

Topic: | Route planning in the CARiN system: Simple algorithms in a complex environment |

Room: | CGN C006, Uithof Campus |

Speaker: | Jacques Verriet, CQM |

Topic: | Development of exact algorithms for frequency assignment problems |

Room: | CGN C006, Uithof Campus |

Speaker: | Stan van Hoesel, Universiteit Maastricht |

The problem is modeled with a graph of vertices (stations) and edges (if choices of frequencies have interference, for the endvertices of an edge. The amount of interference for each choice of combinations is measured with a penalty.

We can formulate this problem as a binary constraint satisfaction problem. A first technique to solve this problem is by use of a cutting plane algorithm (in a branch-and-cut framework). We present valid inequalities, lifting theorems and computational results. A second technique makes use of a structural property of the graph, namely its tree width. By use of dynamic programming techniques this can be used to solve some of the instances we have. A third technique is also based an a structural property but now on the penalty of the edges. The corresponding algorithm leads to even better results than the previous techniques.

Topic: | Bepalen de deelnemers zelf |

Room: | CGN C006, Uithof Campus |

Speaker: | Gerard Tel |

Topic: | Scheduling Jobs On-Line, Selecting the Execution Time in Advance |

Room: | CGN C009, Uithof Campus |

Speaker: | Rob van Stee, CWI |

Topic: | Subspace Methods in Large Scale Semidefinite Optimization |

Room: | CGN C009, Uithof Campus |

Speaker: | Mischja van Bossum, Universiteit Utrecht |

Nesterov and Nemirovskii have extended interior-point algorithms for linear programming (such as Karmarkar's) to handle convex problems. As a result a broad class of convex programming problems can now be solved by using interior-point algorithms in a number of steps that depends polynomial on the problem size. In this class the semidefinite programming problems form a very interesting subclass, from a theoretical, a practical point of view, and an applications minded view. In the last few years several impressive applications of semidefinite programming have been obtained in various fields such as, stability in control and system theory, structural optimization, combinatorial optimization, geometry, and linear algebra.

"Real-life" optimization problems are usually high dimensional and it takes much computational effort to solve them. My research focuses on identifying faster ways solving such problems by means of stable numerical methods, in the interior-point algorithms.

Topic: | Implicit Enumeration Algorithms for the Maximization of Submodular Functions |

Room: | CGN C009, Uithof Campus |

Speaker: | Boris Goldengorin, Department of Econometrics and Operations Research, Groningen University |

**References**

[1] B. Goldengorin, G. Sierksma, G. A. Tijssen, M. Tso. The Data-Correcting
Algorithm for
Minimization of Supermodular Functions.
Management Science 1999 45(11) 1539-1551.

[2] B. Goldengorin, G. A. Tijssen.The Maximization of Submodular Functions:
Old and New Proofs
for the Correctness of the
Dichotomy Algorithm (submitted to Mathematics of OR).

[3] B. Goldengorin. Correcting Algorithm for the Solution of Some
Discrete Optimization Problems, Soviet Math. Dokl.1983 27(3)
620-623.

[4] H. Lee, G.L. Nemhauser, Y. Wang. Maximizing a Submodular Function by
Integer Programming:
Polyhedral Results for the Quadratic Case. European J. Oper. Res. 94 154-156.

All papers are available: B.Goldengorin@eco.rug.nl

Topic: | On a spectral graph invariant and geometric representations of graphs |

Room: | CGN C009, Uithof Campus |

Speaker: | Rudi Pendavingh, Technische Universiteit Eindhoven |

Following this general introduction to *µ* we will present in more
detail some results about the relationship between *µ* and geometric
representations of a graph.

Topic: | The Merchant Subtour Problem |

Room: | CGN C009, Uithof Campus |

Speaker: | Bram Verweij |

The MSP models certain aspects of a multi-depot vehicle routing problem with split deliveries that occurs at Van Gend & Loos, The Netherlands. Apart from this, the MSP is related to several problems that are reported on in the literature. It has a very rich structure, making it an interesting problem to study in its own right. We consider the computational complexity of the MSP, a special case that is solvable in polynomial time, heuristic algorithms and an optimization algorithm.

Topic: | Lambda-kleuring |

Room: | CGN C009, Uithof Campus |

Speaker: | Hans Bodlaender |

Topic: | Planning of production and distribution in the newspaper industry |

Room: | CGN C009, Uithof Campus |

Speaker: | Geert Teeuwen of CQM |

Topic: | Packing connectors |

Room: | CGN C009, Uithof Campus |

Speaker: | Judith Keijsper of the University of Twente |

Both the problem of finding a maximum number of disjoint spanning trees in a
graph and the problem of finding a maximum number of disjoint edge covers in
a bipartite graph can be solved in polynomial time.
In this talk, we explain how the algorithms for these two packing problems
can be combined to obtain an algorithm for packing *S-T* connectors.

We derive a min-max relation for the maximum number of *S-T* connectors
in a graph.
We also sketch how the result can be viewed as a special case of a packing
theorem for matroids.

Topic: | Maximizing Job Completions Online |

Room: | CGN C009, Uithof Campus |

Speaker: | Kirk Pruhs, Department of Computer Science, University of Pittsburgh |

This is joint work with Bala Kalyanasundaram.

Topic: | Multi-depot Vehicle Routing with Integrally Split Deliveries |

Room: | CGN C009, Uithof Campus |

Speaker: | Bram Verweij |

We develop a heuristic for the problem that is based on LP column generation. On medium-size problem instances with real-life characteristics our computational study shows that the algorithm is capable of finding solutions that are on average within a factor of 1.65 from optimal.

Topic: | Slot allocation for flight departures |

Room: | CGN C009, Uithof Campus |

Speaker: | Marjan van den Akker of the National Aerospace Laboratory (NLR) |

We discuss a solution method for a basic version of the European slot allocation problem. The approach is based on integer linear programming and column generation. Computational results are encouraging, because they indicate both possibilities for real-time applications and nearly optimal solutions.

Our current research on slot allocation focuses on Collaborative Decision Making (CDM). Key issue in CDM is improvement of the information exchange and co-operation between different actors in air traffic handling (Air Traffic Control, airlines, airport authorities). We briefly discuss possible applications of CDM in slot allocation.