Modelling of augmented makespan assignment problems: Computational experience of applying integer presolve at the modelling stage

An Augmented Makespan Assignment Problem (AMAP), which is a variation of the Generalised Assignment Problem (GAP), is analysed in this paper. In this problem, we minimise the makespan for producing several products with each on one of several machines. The data instances are such that some of the available machines are identical, which in turn leads to mixed integer programming problems that have many optimal integer solutions. Most commercial software for mathematical programming therefore has problems proving that the solution they find is an optimal one. Even optimisation software that does some integer preprocessing on the system of linear relations has problems in solving a straight-forward formulation of the model. Darby-Dowman et al. investigated this model and found it difficult to solve as an IP. We show that if more of the model structure is highlighted at the modelling stage, and these are exploited in preprocessing the formulation before the problem matrix is produced, then we get easily solvable integer programs for the data instances under consideration. We give computational results for five different commercial codes with and without our preprocessing at the modelling stage.