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

• Juergen Branke
• Bo Chen
• Vladimir Deineko
• Vinh Doan

Selected Publications

R.E. Burkard, V.G. Deineko, R. Van Dal, J.A.A. Van der Veen, and G.J. Woeginger, Well-solvable special cases of the TSP: A survey, SIAM Review 40 (1998), 496–546.

B. Chen, R. Hassin and M. Tzur. Allocation of bandwidth and storage. IIE Transactions on Scheduling and Logistics 34 (2002). 501–507.

X. Chen and B. Chen. Approximation algorithms for soft-capacitated facility location in capacitated network design. Algorithmica 53(3) (2009), 263–297. [doi]

X. Chen and B. Chen. Cost-effective designs of fault-tolerant access networks in communication System. Networks 53(4) (2009), 382–391.

V.G. Deineko and G.J. Woeginger, A study of exponential neighborhoods for the Travelling Salesman Problem and for the Quadratic Assignment Problem, Mathematical Programming, Ser. A, 78, 2000, 519-542.

M. Stein, J. Branke, Schmeck, H.: “Efficient implementation of an active set algorithm for large-scale portfolio selection”. Computers and Operations Research 35(12), Elsevier, 2008, 3945-3961

J. Zhang, B. Chen, and Y. Ye, A multi-exchange local search algorithm for the capacitated facility location problem. Mathematics of Operations Research 30 (2005). 389–403.