Many problems of combinatorial optimisation, such as those in scheduling, transportation and facility location, are inherently difficult to solve and in practice approximation algorithms and heuristics are often used to obtain near-optimal solutions in reasonable amount of computation time. While approximation algorithms provide a worst-case performance guarantee in both computational time and solution quality, research on heuristics typically focuses on the average empirical behaviour of the algorithms.

Among the intrinsically difficult problems we are interested in on-line problems. In such a problem, full information about the parameters of the problem at hand is not available and only becomes known over time, during which decisions need to be made either irrevocably or at a cost otherwise. We design efficient on-line algorithms and analyse their competitiveness against off-line optimal solutions.

A particular type of heuristics are so-called meta-heuristics, which build on simple problem-specific (local) search algorithms and aim at overcoming local optimality through some general-purpose mechanism. Examples include Evolutionary Algorithms (EAs), Particle Swarm Optimization (PSO) and Ant Colony Optimisation (ACO), which are all based on principles observed in nature but applied to optimisation.

Exponential neighbourhoods that can be searched in polynomial time are being intensively studied recently. We are interested in relationship of the exponential neighbourhoods with polynomially solvable cases of NP-hard problems and in efficiency of related heuristics.

ORMS faculty

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

Selected Publications

Blackwell, T.; Branke, J.: Multi-Swarms, exclusion, and anti-convergence in dynamic environments. IEEE Transactions on Evolutionary Computation, 10(4), 2006, 459-472

J. Branke, Mattfeld, D.: Anticipation and flexibility in dynamic scheduling. International Journal of Production Research 43(15), Taylor & Francis, 2005, 3103-3129

J. Branke, Middendorf, M.; Nöth, G.; Dessouky, M.: Waiting strategies for dynamic vehicle routing. Transportation Science 39(3), INFORMS, 2005, 298-312

J. Branke, Guntsch, M.: Solving the probabilistic TSP with ant colony optimization. Journal of Mathematical Modeling and Algorithms 3(4), Kluwer, 2004, 403-425

B. Chen, C.A. Glass, C.N. Potts and V.A. Strusevich: A new heuristic for three-machine flow shop scheduling. Operations Research 44 (1996), 891–898.

B. Chen, C.N. Potts and V.A. Strusevich: Approximations for two-machine flow shop scheduling with batch setup times. Mathematical Programming 82 (1998), 255–271.

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.

V. 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.

V. Deineko, G.J. Woeginger and B. Klinz, Exponential neighbouhoods and four point conditions for the TSP, ACM/SIAM Symposium on Discrete Algorithms (SODA), Florida, USA, 2006, 544–553.

V. Deineko, G. Steiner and Z. Xui, Robotic-Cell Scheduling: Special polynomially solvable case of the traveling salesman problem on permuted Monge matrices, Journal of Combinatorial Optimization 2005, 391–399.

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.