Contributions to exact approaches in combinatorial optimization

The focus of this thesis is to contribute to the development of new, exact solution approaches to different combinatorial optimization problems. In particular, we derive dedicated algorithms for a special class of Traveling Tournament Problems (TTPs), the Dial-A-Ride Problem (DARP), and the Vehicle Routing Problem with Time Windows and Temporal Synchronized Pickup and Delivery (VRPTWTSPD). Furthermore, we extend the concept of using dual-optimal inequalities for stabilized Column Generation (CG) and detail its application to improved CG algorithms for the cutting stock problem, the bin packing problem, the vertex coloring problem, and the bin packing problem with conflicts. In all approaches, we make use of some knowledge about the structure of the problem at hand to individualize and enhance existing algorithms. Specifically, we utilize knowledge about the input data (TTP), problem-specific constraints (DARP and VRPTWTSPD), and the dual solution space (stabilized CG). Extensive computational results proving the usefulness of the proposed methods are reported.

Characterisation and optimisation of the new Prompt Gamma-ray Activation Analysis (PGAA) facility at FRM II

At the research reactor Forschungs-Neutronenquelle Heinz Maier-Leibnitz (FRM II) a new Prompt Gamma-ray Activation Analysis (PGAA) facility was installed. The instrument was originally built and operating at the spallation source at the Paul Scherrer Institute in Switzerland. After a careful re-design in 2004–2006, the new PGAA instrument was ready for operation at FRM II. In this paper the main characteristics and the current operation conditions of the facility are described. The neutron flux at the sample position can reach up 6.07×1010 [cm−2 s−1], thus the optimisation of some parameters, e.g. the beam background, was necessary in order to achieve a satisfactory analytical sensitivity for routine measurements. Once the optimal conditions were reached, detection limits and sensitivities for some elements, like for example H, B, C, Si, or Pb, were calculated and compared with other PGAA facilities. A standard reference material was also measured in order to show the reliability of the analysis under different conditions at this instrument.

The Choice of Expedient Regulatory Controls on Housing Market Using Short-Term Equilibria Model

Khutoretsky dealt with the problem of maximising a linear utility function (MUF) over the set of short-term equilibria in a housing market by reducing it to a linear programming problem, and suggested a combinatorial algorithm for this problem. Two approaches to the market adjustment were considered: the funding of housing construction and the granting of housing allowances. In both cases, locally optimal regulatory measures can be developed using the corresponding dual prices. The optimal effects (with the regulation expenditures restricted by an amount K) can be found using specialised models based on MUF: a model M1 for choice of the optimum structure of investment in housing construction, and a model M2 for optimum distribution of housing allowances. The linear integer optimisation problems corresponding to these models are initially difficult but can be solved after slight modifications of the parameters. In particular, the necessary modification of K does not exceed the maximum construction cost of one dwelling (for M1) or the maximum size of one housing allowance (for M2). The result is particularly useful since slight modification of K is not essential in practice.