Efficiency through laziness: an approach to mathematical optimisation

Integer programming is a widely-used tool for solving important and difficult optimisation problems. The number of variables and constraints used in modelling a problem often determines its difficulty, so finding ways of solving problems with fewer variables and/or constraints often leads to great improvements. The most recent innovation in Operations Research to this effect is “lazy constraints”, the ability to add additional constraints to a problem during the solution process.

We have identified three classes of models that benefit from a lazy constraints treatment: models with exponentially-sized sets of constraints, models with constraints which are mostly or completely unnecessary, and models which are suitable for Benders decomposition. We present examples from each of the classes and explain how they benefit from a lazy approach. Computational results demonstrate the power of these methods.

From this, we consider more generally the way people approach problem solving, and how it may be beneficial to take a lazy attitude towards finding solutions to difficult problems.

Short Bio:

Robin Pearce is a PhD student at UQ studying Operations Research with Michael Forbes. Robin specialises in integer programming and Benders decomposition, particularly when applied to network design and facility location problems. Robin enjoys problem solving in many contexts.

Prior to his PhD, Robin completed his BSc (hons) in mathematics at UQ before working at CSIRO for two years as a graduate fellow. He studied the microstructures of porous materials, particularly metallurgical coke, analyzing their properties such as size, shape and connectivity of the pores, and the performance of the material under various stresses and heat.