Skip to main content
Department of Information Technology

Optimisation and Learning

Operations research (OR) and machine learning (ML) address problems originating from the real world, by formulating models for representation and then using optimisation for solving the models. From this perspective, optimisation plays a similar role in ML as it does in OR. Optimisation lies at the heart of learning, because training in most ML tasks can be formulated as minimising a loss function that represents the price paid for inaccuracy or maximising some notion of cumulative reward that reflects the gain we obtain during learning. Meanwhile, ML techniques that have been proved to be effective in pattern recognition and decision making etc., could also be used to solve optimisation problems. For example, in the branch-and-bound method for integer programming, ML can be used to select node and variable for branching. In general continuous optimisation, using an ML model (e.g. a neural network) to represent the step vector in the updating formula during iterations may enable an algorithm that automatically improves itself during problem solving.

The interplay between optimisation and ML suggests new research to be done in a closely integrated way between the two. The main emphasis of our research is on using learning techniques for pre-processing input data of optimisation and incorporating learning components in optimisation algorithm design; both can be applied on dealing with real-world tasks like traditional OR as well as deriving new algorithms within the domain of ML.

Research Topics

Learning-assisted Data-driven Optimisation

In mathematical optimisation, a real-world problem is usually mapped to a mathematical formulation such that addressing the problem amounts to solving the formulation. This, however, to some extent generalises the problem with specific input data that we actually want to solve: The optimisation algorithm design is based on the algebraic structure of the formulation and is usually independent of the input data; these data, nevertheless, may possess special patterns that can help reducing efforts to be paid in problem solving. By embedding ML components into the algorithmic framework, the patterns of the data behind the real-world problem can be extracted, to identify appropriate formulations for problem solving as well as to enable a data-driven strategy for self-adaptive algorithm design.

Optimisation with Deep/Reinforcement Learning

So far there has been no more effective way other than state-space search based methods for dealing with hard optimisation problems. A state-space search based algorithm consists in maintaining known states and making decision for exploring new states. Traditional state-space search methods (e.g. heuristic search or branch-and-bound) can be formulated as sequential decision-making processes, which are coherent with the reinforcement learning framework. In addition, the effectiveness of deep learning, as demonstrated in many research fields, suggests that deep learning may serve as a good replacement for hand-engineered features or domain heuristics in algorithm design. A successful example is DeepMind’s AlphaGo Zero for solving the classic combinatorial optimisation problem Go.

Updated  2018-02-07 17:11:22 by Lei You.