# Combinatorial Optimisation

Combinatorial optimisation deals with decision-making problems of a discrete nature. Out of a finite or countably infinite number of alternatives, we need to choose the best one according to some quantifiable criterion. Most of the well-known problems of combinatorial optimisation belong to the class of the so-called NP-hard problems and they are intrinsically very difficult in computation. Integer linear programming (ILP) is one of the techniques to approach hard combinatorial optimization problems. State-of-the-art ILP solvers are able to solve many large-scale discrete optimisation problems routinely by branch-and-bound. The algorithms can be further enhanced by the study of the polyhedral structure of the problem (cutting planes, branch-and-cut) as well as by on-the-fly introduction of decision variables (dynamic column generation, branch-and-price). We have applied these techniques to a range of real-life applications, in particular in the area of telecommunication network design. Another direction of our research is identifying polynomially solvable cases of NP-hard problems, which include in particular such well-known problems as TSP and quadratic assignment problems. This helps further understand the nature of the intractable problems in general cases. For generally intractable problems, we are interested in designing efficient approximation algorithms that provide performance guarantee. Among the combinatorial optimisation problems we recently studied are facility location in network design, in which one designs a minimum cost network to serve client demands by opening facilities for service provision and installing cables for service shipment, and developing practical algorithms for computing (almost) optimal tree decompositions as well as to determine lower bounds on the tree-width, since many combinatorial optimisation problems defined on a graph can be solved even in linear (or polynomial) time with a dynamic programming algorithm when the input graph has bounded tree-width. As a research group, we are able to deal with a wide range of challenging problems, both theoretical and practical, for which we formulate the problem as a mathematical model, design efficient algorithms, and implement our solutions in software prototypes. ## ORMS faculty## Selected PublicationsR.E. Burkard,
X. Chen and X. Chen and
M. Stein, J. Zhang, |