Seminar Abstracts

THE PROBLEM WITH INTEGER PROGRAMMING

Integer Programming (IP), also known as Discrete Optimisation, is a way of modelling a very wide range of problems involving indivisibilities (eg. Yes/No investment decisions) and non-convexities (eg. economies of scale and fixed cost allocation). Such problems arise in eg. manufacturing, distribution, and process industries, such as petroleum, as extensions of Linear Programmes (LP). They also arise in facilities location, routing, telecommunication network design and operation, medical radiation treatment, statistical design, molecular biology, genome sequencing, archaeological seriation, the logical analysis of data, computer design, airline and aircrew scheduling to name only some. However IP demands ingenuity in both building models and solving them. A lot is still not properly understood.

Is IP like LP?

This talk will investigate this question. The mathematical and economic properties of IP will be contrasted with LP. It will be suggested that the mathematics and economics of IP is still not properly understood. Many of the results which apply to LP do not apply to IP (eg. relying on vertex solutions to find optimal solutions, the existence of dual values to represent values of resources etc.). It will be asserted that this lack of understanding reveals inadequacies in both mathematics and economics.

It will be shown that in many (but not all) situations the rounding of an LP solution does not produce satisfactory (feasible or optimal) solutions to an IP. A topical example will be given of political apportionment leading to the Alabama Paradox. However rounding, in a more sophisticated manner, is still applicable as discussed below.

IP is essentially concerned with the combination of two structures:

(i) Linear inequalities giving rise to polytopes.

(ii) Lattices of integer points within these polytopes.

Mathematical and computational methods and results exist for both these structures on their own eg. The Simplex algorithm and the Euclidean algorithm and duality theories. However mixing them is like mixing oil and water. Problems arise in both the computation of optimal solutions and the economic interpretation of the results. It will be suggested that the appropriate mathematical structure is an integer monoid. This structure will be explained. Connected with this structure are Chvatal functions which are made up of non-negative combinations of the arguments together with the (nested) integer round-up operation. The use of these functions in place of the conventional non-negative linear combinations of LP allows one to capture many of the classical LP results eg. The Weyl-Minkowski theorems, ‘pricing’ of indivisible resources and the closing of the ‘duality gap’ leading to the optimal IP solution. It will be shown how optimal Chvatal functions can be calculated and their interpretation as the (non-marginal) valuation of indivisible resources given. However a major problem remains as to how to represent them in a transparent and compact way.

A SURVEY OF DIFFERENT INTEGER PROGRAMMING FORMULATIONS OF THE TRAVELLING SALESMAN PROBLEM

Eight distinct (and in some cases little known) formulations of the Travelling Salesman Problem as an Integer Programme will be described. Apart from the standard formulation all are 'compact' in the sense that the number of constraints and variables is a polynomial function of the number of cities in the problem. Comparisons of the formulations are made by projecting out variables in order to compare the strengths of the Linear Programming relaxations. These results are illustrated by computational results on a small problem.

THE ALLOCATION OF SHARED FIXED COSTS

We consider the problem of sharing the fixed costs of facilities among a number of users. Although the problem can be formulated and solved as an Integer Programme this provides limited accounting information. Ways of overcoming this are suggested.

In addition we consider the issue of fairness among different possible cost allocations and how such 'fair' costs may be derived.

THE TWO-PERIOD TRAVELLING SALESMAN PROBLEM APPLIED TO MILK COLLECTION IN IRELAND

A new extension of the Travelling Salesman Problem (TSP) will be described arising from a milk collection problem in Ireland. In this problem some farms require a collection every day and some every other day. A number of Integer Programming (IP) formulations will be described. Predictably these prove prohibitively difficult to solve. A method of solution based on the derivation and use of facets of the convex hull of feasible solutions will be described. This approach proved remarkably successful in solving this problem which is more difficult than the standard TSP.

THE TRAVELLING SALESMAN PROBLEM

We describe what this famous, but difficult, problem is and how it arises in such diverse areas as routeing, job sequencing, computer wiring, wall paper hanging, archaeology and genome sequencing.

Also we briefly describe some important extensions such as vehicle routing.

The current state of the art with regard to solving very large models will be outlined together with different ways of formulating the problem as a mathematical model.

ALLOCATION AND SOCIAL EQUITY

We will look at a number of problems of Allocation, particularly in the area of Social Policy. While these problems are often tackled by techniques from Operational Research (Linear and Integer Programming and Game Theory) a major concern arises as to the 'fairness' of the resulting allocation. We will discuss notions of fairness in contrast to other criteria (efficiency and maximising total 'good').

Problems to be considered are Allocating Scarce Medical Resources among different patients, Allocating Limited Teachers among competing ability groups and Allocating Fixed Costs of facilities between different users.

It will be shown how Linear and Integer Programming can still be used to give possible 'fair' solutions when a criterion of Minimising the Maximum shortfall of any category from its optimum provision is used.

SEARCHING FOR THE DUAL OF AN INTEGER PROGRAMME

Linear Programmes have well-defined Duals. These are of importance for Computational (proof of optimality), Economic (marginal values, opportunity costs, transfer prices etc) and Mathematical (symmetry) reasons.

Integer Programmes (where some of the activities are restricted to discrete values) have many practical applications. There is, however, no totally satisfactory Dual of an Integer Programme. If it existed it would have many important Computational, Economic (eg Fixed Cost allocation) and Mathematical uses.

This talk will survey possible duals and indicate their limitations. The most satisfactory Dual replaces prices by (subadditive) price functions. These take the form of Chvatal functions. They have an interesting structure in their own right. They can be regarded as an extension of the ,economically motivated, Gomory-Baumol prices.

PROJECTION AND INVERSE PROJECTION AS A MEANS OF REFORMULATING LINEAR AND INTEGER PROGRAMMES

We describe how variables can be projected out of a Linear Programme (LP) using Fourier-Motzkin Elimination to produce an equivalent model. This will be illustrated by some formulations of the Travelling Salesman Problem. Inverse Projection (the LP Dual procedure) can also me carried out to eliminate constraints in a model. The procedures can also be extended (at great complexity) to eliminate integer variables or constraints from an Integer Programme.

LOGIC APPLIED TO INTEGER PROGRAMMING AND INTEGER PROGRAMMING APPLIED TO LOGIC

There are many cross connections between the methods of Logic and Artificial Intelligence (Resolution and its extensions) and Integer Programming (IP) (Branch-and-Bound and Cutting Planes). Methods applicable to one are applicable to the other and vice versa. These interrelationships will be discussed.

Logic is also applicable to the automated formulation of IP models with logical constraints. A method of representing and converting problems to Mixed IP models by the use of Predicate Calculus symbolism will be described.

This talk will also include a coverage of the following topics from both the Logic and Mathematical Programming points of view: (I) Decidable Fragments of Mathematics (ii) The Simplified Nature of Horn Clause Systems (iii) The projection of lattices within polytopes to lower dimensions.

WHAT LIES BETWEEN ADDITION AND MULTIPLICATION AND BEYOND

We seek an arithmetic operation between Addition and Multiplication. Such an operation could have practical value if found. In order to do this we investigate (i) a generalisation of Ackermann’s Function, (ii) the solution to the functional equation f f (x) = ex , (iii) Gauss’ Mean which lies between the Arithmetic and Geometric Mean.

This seminar will not use deep mathematics and be easily understood by a non-specialist.

MODELLING FOR INTEGER PROGRAMMING OR CONSTRAINT SATISFACTION

We will compare Integer Programming and Constraint Logic Programming as modelling paradigms and show how typical constraints are modelled by both methods (eg Assignment constraints and the ‘All-different’ constraint).

Solution methods will be outlined briefly and it will be suggested the CLP has features in common with Preprocessing (Presolve) method in IP systems.

Finally we will discuss experience with solving the Progressive Party Problem by both methods.

A METHOD OF FINDING ALL SOLUTIONS OF A LINEAR COMPLEMENTARITY PROBLEM

We define the Linear Complementarity Problem (LCP) and outline its applications including those to Linear Programming (LP), Quadratic Programming (QP), Two Person Non-Zero Sum Games and Evolutionary Games. Then we briefly discuss previous methods of solution emphasising the problem of finding all solutions. A new algorithm is then presented, and illustrated by a numerical example, which finds all solutions. It works by successive transformations of variables in order to eliminate the equations in the model.

THE PROGRESSIVE PARTY PROBLEM: A Difficult Problem of Combinatorial Optimisation

This problem was presented to me by the organiser of a yacht club on the Isle of Wight. I tried to solve it as an Integer Programme (IP) using a number of formulations (and 'ingenious' cuts). Although a good solution was found it was not possible to find the optimum in any reasonable time. It was then successfully solved by Barbara Smith using Constraint Logic Programming (CLP).

This talks compares the relative strengths of IP and CLP on this problem. The problem is to allocate guests to host boats, at a social gathering at successive time intervals during the day, with a variety of restrictions. The objective is to minimise the number of host boats needed. The IP and CLP formulations are explained and computational results given.

THE MODELLING POTENTIAL OF MINIMAX ALGEBRA

MiniMax algebra uses symbols + and +' for Max and Min and x and x' for + and - . It enables many problems in Optimisation and Scheduling to be stated in an analogous fashion to Linear Algebra. Parallels then become apparent between respective algorithms for different types of problem.

YIELD MANAGEMENT FOR AN AIRLINE

This talk is based on a problem in the book "Model Building in Mathematical Programming" (4th edition). The audience will be asked to 'buy' tickets for the future at given prices. A Stochastic Programme will then be run to enable the airline to update its prices based on remaining availability. The procedure will then be repeated for the next period. By running over 3 periods the yield for the airline (and the audience's costs) will be compared with what would have resulted from (i) hindsight and (ii) a policy based on optimising expected yield.