Integer Programming as Projection
(with J.N. Hooker) LSE0R 13-143, 2014

Abstract: We generalise polyhedral projection (Fourier-Motzkin elimination) to integer programming (IP) and derive from this an alternative perspective on IP that parallels the classical theory. We first observe that projection of an IP yields an IP augmented with linear congruence relations and finite-domain variables, which we term a generalised IP. The projection algorithm can be converted to a branch-and-bound algorithm for generalised IP in which the search tree has bounded depth (as opposed to conventional branching, in which there is no bound). It also leads to valid inequalities that are analogous to Chv´atal-Gomory cuts but are derived from congruences rather than rounding, and whose rank is bounded by the number of variables. Finally, projection provides an alternative approach to IP duality. It yields a value function that consists of nested roundings as in the classical case, but in which ordinary rounding is replaced by rounding to the nearest multiple of an appropriate modulus, and the depth of nesting is again bounded by the number of variables.

---

The Dependency Diagram of a Mixed Integer Linear Programme
LSE0R 13-139, 2013

Abstract: The Dependency Diagram of a Linear Programme (LP) shows how the successive inequalities of an LP depend on former inequalities, when variables are projected out by Fourier-Motzkin Elimination. This is explained in a paper referenced below. The paper, given here, extends the results to the Mixed Integer case (MILP). It is shown how projection of a MILP leads to a …finite disjunction of polytopes. This is expressed as a set of inequalities (mirroring those in the LP case) augmented by correction terms with …finite domains which are subject to linear congruence

---

The General Solution of a Mixed Integer Linear Programme over a Cone
LSE0R 13-140, 2013

Abstract: We give a general method of finding the optimal objective, and solution, values of a Mixed Integer Linear Programme over a Cone (MILPC) as a function of the coefficients (objective, matrix and right-hand side). In order to do this we first convert the matrix of constraint coeffcients to a Normal Form (Modified Hermite Normal Form (MHNF)). Then we project out all the variables leaving an (attainable) bound on the optimal objective value. For (M)IPs, including MILPC, projection is more complex, than in the Linear programming (LP) case, yielding the optimal objective value as a finite disjunction of inequalities The method can also be interpreted as finding the minimal strengthening of the constraints of the LP relaxation which yields an integer solution to the associated LP.

---

The Dependency Diagram of a Linear Programme
LSE0R 13-138, 2013

Abstract: The Dependency Diagram of a Linear Programme (LP) shows how the successive inequalities of an LP depend on former inequalities, when variables are projected out by Fourier-Motzkin Elimination. It is also explained how redundant inequalities can be removed, using the method attributed to Chernikov and to Kohler. The procedure also leads to a transparent explanation of Farkas' Lemma. LP Duality, the dual form of Caratheodory's Theorem as well as generating all vertices and extreme rays of the Dual Polytope.

---

What lies between + and x (and beyond)?
LSE0R 10-119, 2010

Abstract: We attempt to create a continuum of functions between addition and multiplication (and beyond). Such a function could have practical applications. Addition, multiplication, exponentiation, tetration etc. are all particular cases of a generalisation of Ackermann’s function for successive integral values of one of the arguments. Intermediate functions can be viewed as results of a fractional value of this argument. Ways of seeking such functions with given properties are investigated. It is noted that some other integrally defined functions of mathematics can be extended to fractional arguments. Two possible approaches, which are considered here, are (i) to consider Gauss’s Arithmetic-Geometric mean and (ii) to consider solutions of the functional equation ff(x) = ex.

---

The Problem with Integer Programming
LSE0R 10-118, 2010

Abstract: 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 many areas which will be mentioned. However IP demands ingenuity in both building models and solving them. A lot is still not properly understood.

This paper investigates the question. 'Is IP like Linear Programming (LP)?' The mathematical and economic properties of IP will be contrasted with LP. It will be suggested that the mathematics and economics of IP are still not properly understood. Many of the results which apply to LP do not apply to IP. It will be asserted that this lack of understanding reveals inadequacies in both the 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.

IP is essentially concerned with the intersection of two structures:

(i) Linear inequalities giving rise to polytopes.

(ii) Lattices of integer points.

Mathematical and computational methods and results exist for both these structures on their own. 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 Chvátal 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 Chvátal functions can be interpretated as the (non-marginal) valuation of indivisible resources. However a major problem remains as to how to represent them in a transparent and compact way.

---

Combining Equity and Utilitarianism in a Mathematical Programming Model
(with John Hooker) LSE0R 09-117, 2009, Revised November 2011

Abstract: We attempt to create a continuum of functions between addition and multiplication (and beyond). Such a function could have practical applications. Addition, multiplication, exponentiation, tetration etc. are all particular cases of a generalisation of Ackermann’s function for successive integral values of one of the arguments. Intermediate functions can be viewed as results of a fractional value of this argument. Ways of seeking such functions with given properties are investigated. It is noted that some other integrally defined functions of mathematics can be extended to fractional arguments. Two possible approaches, which are considered here, are (i) to consider Gauss’s Arithmetic-Geometric mean and (ii) to consider solutions of the functional equation ff(x) = ex.

---

Convex Hull Representations of the at_least Predicate of Constraint Satisfaction
(with Hong Yan) LSE0R 7.97, 2007

Abstract: The predicate "at_leastm{x1,...,xn} = k" says that "at least m of xi’s take value k". This, and its generalisations, is one of the most commonly used predicates in Constraint Satisfaction. The structure of its feasibility set is exhibited. The facet defining constraints for the convex hull are then described and proved. The differences of the convex hulls are shown when the variables are or are not bounded above.

---

A Method for Finding All Solutions of a Linear Complementarity Problem
LSE0R 7.96, 2007

Abstract: 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 Allocation of Shared Fixed Costs
(with Martin Butler) LSE0R 2.52, October 2002

Abstract: 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 allocations and how such 'fair' costs may be derived.

---

A New Framework for the Solution of DEA Models
(with Gautam Appa)LSEOR 04.70, August 2004

Abstract: When solving Data Envelopment Analysis (DEA) models it is usual to solve a Linear Programme (LP) many times, with different right-hand-side (RHS) vectors: once for each Decision Making Unit (DMU) in the organisation being evaluated. Besides being tedious and involving repeated computation this iterative approach gives little insight into the overall structure of the model for the organisation. Instead, by projecting out all the variables of the LP which are common to all LP runs, we obtain a formula into which we can substitute the inputs and outputs of each DMU in turn in order to obtain its efficiency number and efficient comparators. In addition we also obtain the best weightings which the DMU would choose to put on its inputs and outputs. The method of projection, which we use, is Fourier-Motzkin Elimination. This provides us with a finite number of extreme rays of the elimimation cone. These rays give the dual multipliers which can be interpreted as weights which will apply to the inputs and outputs for particular DMUs. As the approach provides all the extreme rays of the cone, multiple sets of weights, when they exist, are explicitly provided. The method also demonstrates that the same weightings will apply to all DMUs having the same comparators. In addition it is possible to construct the skeleton efficient frontier of efficient DMUs.

---

Fairness Versus Efficiency in Charging for the use of Common Facilities
(with Martin Butler) LSEOR 01.45, Revised May 2002

Abstract: The problem of efficiency versus fairness is considered in relation to the splitting of costs for shared facilities between the users. This is considered as a result of a problem of sharing the cost of the provision of central computing facilities between different faculties in a large university, but the basic problem is widespread. A Linear Programming model is considered in order to minimise cost. The dual of this model is shown to correspond to an efficient allocation of costs. An alternative optimal dual solution is shown to give a 'fair' solution according to criteria resulting from cooperative game theory.

---

A Survey of Different Integer Programming Formulations of the Travelling Salesman Problem
(with Alex Orman) LSEOR 04.67, London School of Economics, Revised May 2004

Abstract: Eight distinct (and in some cases little known) formulations of the Travelling Salesman Problem as an Integer Programme are given. Apart from the standard formulation, all the formulations 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 produce polytopes in the same space. It is then possible to compare the strengths of the Linear Programming relaxations. These results are illustrated by computational results on a small problem.

---

Heuristic Procedures for the 2-Period Travelling Salesman Problem
(with M.Butler) OR74, University of Southampton February 1995

Abstract: The 2-Period Travelling Salesman Problem is defined and its application to the milk industry explained together with other applications. A number of heuristic procedures of solution are described and results given for a number of problems up to 200 cities. Some heuristics are generalisations of those for the standard TSP and some are specific to this generalisation.

---

A Method of Finding all Equilibrium Solutions of a 2-Person Matrix Game
OR22, University of Southampton, October 1989

Abstract: It is shown how all the equilibrium solutions of a 2-person non-cooperative game can be derived from the vertices of two polytopes. Such vertices must be orthogonal in a manner described. A numerical example is used to illustrate the method. Two types of games, zero-sum and evolutionary games are shown to be special cases with special properties. Finally some further areas for investigation are considered.

---

An Alternative Form of the Value Function of an Integer Programme
OR16, University of Southampton, October 1988

Abstract: The value function of an Integer Programme is the optimal objective value expressed as a function of the right-hand-side coefficients. A method of expressing the value function is described which involes non-negative 'correction terms' applied to the right-hand-side coefficients, which must satisfy a series of linear congruences and are restricted to a finite set of values.

---

A Note: Orthogonality in Linear Congruence Duality
OR9, University of Southampton, July 1987

Abstract: A duality result for linear congruences analogous to that for Linear Programming is extended to give an analogous orthogonality result as well.

---

A Duality Relationship for Integer Programmes
University of Edinburgh Working Paper, 1983

Abstract: Two procedures for solving Integer Programmes (IPs) are described. When applied respectively to IPs whose Linear Programming Relaxations are duals a correspondence between the two procedures is maintained. This correspondence is proved and shown to result in two reduced models with the same coefficients. One model (the Primal) reduces to a disjunction of inequalities and congruences. The other model (the Dual) reduces to a single equation and a series of homogeneous linear congruences. A numerical example is given.

---

Decision Procedures in Formal Logic and Mathematical Programming Algorithms
Research Report 73-2 Operational Research Group, University of Sussex, Brighton, UK 1973

Abstract: The relationship between decision procedures in formal logic and algorithms for Linear and Integer Programming are discussed.

---

An Algorithm for the Solution of Linear Programming Problems
Working Paper 1970

Abstract: This paper describes an algorithm for solving Linear Programming problems based on a decision procedure used in logic.

---