No description available.

This thesis examines the Orthogonal Latin Squares (OLS) problem from the viewpoint of Integer and Constraint programming. An Integer Programming (IP) model is proposed and the associated polytope is analysed. We identify several families of strong valid inequalities, namely inequalities arising from cliques, odd holes, antiwebs and wheels of the associated intersection graph. The dimension of the OLS polytope is established and it is proved that certain valid inequalities are facet-inducing. This analysis reveals also a new family of facet-defining inequalities for the polytope associated with the Latin square problem. Separation algorithms of the lowest complexity are presented for particular families of valid inequalities. We illustrate a method for reducing problem's symmetry, which extends previously known results. This allows us to devise an alternative proof for the non-existence of an OLS structure for n = 6, based solely on Linear Programming. Moreover, we present a more general Branch & Cut algorithm for the OLS problem. The algorithm exploits problem structure via integer preprocessing and a specialised branching mechanism. It also incorporates families of strong valid inequalities. Computational analysis is conducted in order to illustrate the significant improvements over simple Branch & Bound. Next, the Constraint Programming (CP) paradigm is examined. Important aspects of designing an efficient CP solver, such as branching strategies and constraint propagation procedures, are evaluated by comprehensive, problem-specific, experiments. The CP algorithms lead to computationally favourable results. In particular, the infeasible case of n = 6, which requires enumerating the entire solution space, is solved in a few seconds. A broader aim of our research is to successfully integrate IP and CP. Hence, we present ideas concerning the unification of IP and CP methods in the form of hybrid algorithms. Two such algorithms are presented and their behaviour is analysed via experimentation. The main finding is that hybrid algorithms are clearly more efficient, as problem size grows, and exhibit a more robust performance than traditional IP and CP algorithms. A hybrid algorithm is also designed for the problem of finding triples of Mutually Orthogonal Latin Squares (MOLS). Given that the OLS problem is a special form of an assignment problem, the last part of the thesis considers multidimensional assignment problems. It introduces a model encompassing all assignment structures, including the case of MOLS. A necessary condition for the existence of an assignment structure is revealed. Relations among assignment problems are also examined, leading to a proposed hierarchy. Further, the polyhedral analysis presented unifies and generalises previous results.

- / -

The thesis argues the case for exploiting certain structures in integer linear programs. Integer linear programs are optimisation problems, where one minimises or maximises a linear function of variables, whose values are required to be integral as well as satisfying certain linear equalities and inequalities. For such an abstract problem, there are very good general-purpose solvers. The state of the art in such solvers is an approach known as “branch and bound”. The performance of such solvers depends crucially on four types of in-built heuristics: primal, improvement, branching, and cut-separation or, more generally, bounding heuristics. However, such heuristics have, until recently, not exploited structure in integer linear programs beyond the recognition of certain types of single-row constraints. Many alternative approaches to integer linear programming can be cast in the following, novel framework. “Structure” in any integer linear program is a class of equivalence among triples of algorithms: deriving combinatorial objects from the input, adapting them, and transforming the adapted object to solutions of the original integer linear program. Many such alternative approaches are, however, inherently incompatible with branch and bound solvers. We, hence, define a structure to be “useful”, only when it extracts submatrices, which allow for the implementation of more than one of the four types of heuristics required in the branch and bound approach. Although the extraction of the best possible submatrices is non-trivial, the lack of a considerable submatrix with a given property can often be recognised quickly, and storing useful submatrices in a “pool” makes it possible to use them repeatedly. The goal is to explore whether the state-of-the-art solvers could make use of the structures studied in the academia. Three examples of useful structures in integer linear programs are presented. A particularly widely applicable useful structure relies on the aggregation of variables. Its application can be seen as a decomposition into three stages: Firstly, we partition variables in the original instance into as small number as possible of support sets of constraints forcing convex combinations of binary variables to be less than or equal to one in the original instance, and one-element sets. Secondly, we solve the “aggregated” instance corresponding to the partition of variables. Under certain conditions, we obtain a valid lower bound. Finally, we fix the solution of the aggregated instance in primal and improvement heuristics for the original instance, and use the partition in hyper-plane branching heuristics. Under certain conditions, the primal heuristics are guaranteed to find a feasible solution to the original instance. We also present structures exploiting mutual-exclusion and precedence constraints, prevalent in scheduling and timetabling applications. Mutual exclusion constraints correspond to instances of graph colouring. For numerous extensions of graph colouring, there are natural primal and branching heuristics. We present lower bounding heuristics for extensions of graph colouring, based on augmented Lagrangian methods for novel semidefinite programming relaxations, and reformulations based on a novel transformation of graph colouring to graph multicolouring. Precedence constraints correspond to an instance of precedence-constrained multi-dimensional packing. For such packing problems, we present heuristics based on an adaptive discretisation and strong discretised linear programming relaxations. On in- stances of packing unit-cubes into a box, the reformulation makes it possible to solve instances that are by five orders of magnitude larger than previously. On instances from complex timetabling problems, which combine mutual- exclusion and packing constraints, the combination of heuristics above can often result in the gap between primal and dual bounds being reduced to under five percent, orders of magnitude faster than using state of the art solvers, without any information being used that is outside of the instance.

In this thesis modelling and solution methods for portfolio optimisation are presented. The investigations reported in this thesis extend the Markowitz mean-variance model to the domain of quadratic mixed integer programming (QMIP) models which are 'NP-hard' discrete optimisation problems. In addition to the modelling extensions a number of challenging aspects of solution algorithms are considered. The relative performances of sparse simplex (SSX) as well as the interior point method (IPM) are studied in detail. In particular, the roles of 'warmstart' and dual simplex are highlighted as applied to the construction of the efficient frontier which requires processing a family of problems; that is, the portfolio planning model stated in a parametric form. The method of solving QMIP models using the branch and bound algorithm is first developed; this is followed up by heuristics which improve the performance of the (discrete) solution algorithm. Some properties of the efficient frontier with discrete constraints are considered and a method of computing the discrete efficient frontier (DEF) efficiently is proposed. The computational investigation considers the efficiency and effectiveness in respect of the scale up properties of the proposed algorithm. The extensions of the real world models and the proposed solution algorithms make contribution as new knowledge.

Ο Ακέραιος Προγραμματισμός είναι κλάδος του Γραμμικού Μαθηματικού Προγραμματισμού, και αποτελεί τμήμα της συνδιαστικής βελτιστοποίησης. Στόχος της χρήσης του είναι η βελτιστοποίηση συστημάτων παραγωγής ή διοίκησης. Ο Ακέραιος Προγραμματισμός χρησιμοποιείται για την επίλυση πρακτικών προβλημάτων, όπως: • Χρονοδιαγράμματα (Scheduling) • Σχεδιασμός παραγωγής • Παράλληλη εκτέλεση εργασιών • Τηλεπικοινωνίες Μπορεί να φαίνεται ότι τα προβλήματα ακεραίου προγραμματισμού είναι εύκολο να λυθούν. Παρ’όλ’αυτά, κάτι τέτοιο δεν ισχύει, διότι οι αστρονομικά μεγάλοι ακέραιοι αριθμοί, καθώς επίσης και η στρογγυλοποίηση και αφαίρεση μη ακεραίων λύσεων από ένα πρόβλημα γραμμικού προγραμματισμού οδηγούν σε προβλήματα και λανθασμένα συμπεράσματα. Οι κυριότερες τεχνικές Ακεραίου Προγραμματισμού είναι οι εξής: • Μέθοδος κλάδου και φραγής (Branch and Bound) • Τεχνικές περιορισμού του εφικτού χώρου (Cutting Planes) • Μέθοδοι απαρίθμησης • Διαμεριστικοί αλγόριθμοι • Αλγόριθμοι βασισμένοι στη θεωρία ομάδων (Gomory) Η προπτυχιακή αυτή διπλωματική εργασία έχει στόχο να παρουσιάσει δύο από αυτές τις τεχνικές λεπτομερώς, την μέθοδο κλάδου και φραγής και τεχνικές περιορισμού του εφικτού χώρου, και να κάνει κατανοητή τη χρησιμότητα των αλγορίθμων αυτών μέσα από παραδείγματα που αφορούν προβλήματα ακέραιου προγραμματισμού. / Integer Programming is a branch of Linear Mathematical Programming, and is part of the combinatorial optimization. The purpose of using the system optimization of production or administration. The Integer Programming is used to solve practical problems, such as: • Timelines (Scheduling) • Production Design • Parallel execution of works • Telecommunications It may seem that the integer programming problems are easy to solve. However, this is not true, because the astronomically large integers, as well as rounding and removing non-integer solutions of a linear programming problem lead to problems and false conclusions. The main technical Integer Programming are: • branch and bound method (Branch and Bound) • Technical limitations of feasible region (Cutting Planes) • Methods of enumeration • Diameristikoi algorithms • Algorithms based on the theory of groups (Gomory) Undergraduate this thesis aims to present two of these techniques in detail, the branch and bound method and techniques to reduce the feasible region, and make understandable the usefulness of these algorithms through examples involving integer programming problems.

Text in Afikaans / In this thesis contributions to the solution of the generalised knapsack problem are given and discussed. Attention is given to problems with functions that are calculable but not necessarily in a closed form. Algorithms and test problems can be used for problems with closed-form functions as well. The focus is on the development of good heuristics and not on exact algorithms. Heuristics must be investigated and good test problems must be designed. A measure of convexity for convex functions is developed and adapted for concave functions. A test problem generator makes use of this measure of convexity to create challenging test problems for the concave, convex and mixed knapsack problems. Four easy-to-interpret characteristics of an S-function are used to create test problems for the S-shaped as well as the generalised knapsack problem. The in uence of the size of the problem and the funding ratio on the speed and the accuracy of the algorithms are investigated. When applicable, the in uence of the interval length ratio and the ratio of concave functions to the total number of functions is also investigated. The Karush-Kuhn-Tucker conditions play an important role in the development of the algorithms. Suf- cient conditions for optimality for the convex knapsack problem with xed interval lengths is given and proved. For the general convex knapsack problem, the key theorem, which contains the stronger necessary conditions, is given and proved. This proof is so powerful that it can be used to proof the adapted key theorems for the mixed, S-shaped and the generalised knapsack problems as well. The exact search-lambda algorithm is developed for the concave knapsack problem with functions that are not in a closed form. This algorithm is used in the algorithms to solve the mixed and S-shaped knapsack problems. The exact one-step algorithm is developed for the convex knapsack problem with xed interval length. This algorithm is O(n). The general convex knapsack problem is solved by using the pivot algorithm which is O(n2). Optimality cannot be proven but in all cases the optimal solution was found and for all practical reasons this problem will be considered as being concluded. A good heuristic is developed for the mixed knapsack problem. Further research can be done on this heuristic as well as on the S-shaped and generalised knapsack problems. / Mathematical Sciences / D. Phil. (Operasionele Navorsing)

Text in Afikaans / In this thesis contributions to the solution of the generalised knapsack problem are given and discussed. Attention is given to problems with functions that are calculable but not necessarily in a closed form. Algorithms and test problems can be used for problems with closed-form functions as well. The focus is on the development of good heuristics and not on exact algorithms. Heuristics must be investigated and good test problems must be designed. A measure of convexity for convex functions is developed and adapted for concave functions. A test problem generator makes use of this measure of convexity to create challenging test problems for the concave, convex and mixed knapsack problems. Four easy-to-interpret characteristics of an S-function are used to create test problems for the S-shaped as well as the generalised knapsack problem. The in uence of the size of the problem and the funding ratio on the speed and the accuracy of the algorithms are investigated. When applicable, the in uence of the interval length ratio and the ratio of concave functions to the total number of functions is also investigated. The Karush-Kuhn-Tucker conditions play an important role in the development of the algorithms. Suf- cient conditions for optimality for the convex knapsack problem with xed interval lengths is given and proved. For the general convex knapsack problem, the key theorem, which contains the stronger necessary conditions, is given and proved. This proof is so powerful that it can be used to proof the adapted key theorems for the mixed, S-shaped and the generalised knapsack problems as well. The exact search-lambda algorithm is developed for the concave knapsack problem with functions that are not in a closed form. This algorithm is used in the algorithms to solve the mixed and S-shaped knapsack problems. The exact one-step algorithm is developed for the convex knapsack problem with xed interval length. This algorithm is O(n). The general convex knapsack problem is solved by using the pivot algorithm which is O(n2). Optimality cannot be proven but in all cases the optimal solution was found and for all practical reasons this problem will be considered as being concluded. A good heuristic is developed for the mixed knapsack problem. Further research can be done on this heuristic as well as on the S-shaped and generalised knapsack problems. / Mathematical Sciences / D. Phil. (Operasionele Navorsing)