Solving Hard Combinatorial Optimisation Problems with General Purpose Integer Programming Software: A Guide for OR Practitioners

Francis J. Vasko*, Yun Lu and Myung Soon Song
Department of Mathematics, Kutztown University, PA, USA

When OR practitioners are faced with the need to solve and implement industrial applications that can be formulated as combinatorial optimisation problems (COPs), the expense in terms of the personnel time commitment on algorithm development, computer code generation and testing, and solution implementation can be significant and costly. In addition to OR practitioners’ needs for simple, effective, and efficient solution approaches, it is also important for them to guarantee the quality of the solutions presented to management for implementation.

Current research trends in solving COPs involve the use of metaheuristics and heuristics. Unfortunately, metaheuristics and heuristics do not provide guaranteed solution bounds, and need to be tailored to solve a particular COP. Alternately, an OR practitioner could input the COP into general-purpose integer programming software where the best solution found by the software will be guaranteed to be within 0.0001 of the optimum. However, for many industrial applications, the execution time can be excessive before the solution found is proven to be optimum.

What if an OR practitioner could use general-purpose integer programming software to quickly obtain, not necessarily optimal solutions, but solutions guaranteed to be close to the optimal? This is the motivation for the simple sequential increasing tolerance (SSIT) matheuristic. The SSIT matheuristic can use any integer programming software (applications in the literature have used both Gurobi and CPLEX) and systematically loosens the tolerance used to terminate the software. For example, instead of running, say Gurobi, for a maximum of one hour at the default tolerance of 0.0001, the OR practitioner would define a sequence of tolerances and execution times for each tolerance with each tolerance looser than the previous one. Specifically, based on some preliminary experimentation and how quickly a solution was needed for the particular application, the OR practitioner might have set a tolerance of 0.0001 for 60 seconds, if no suitable solution was obtained in 60 seconds, then the tolerance would automatically be loosened to 0.001 for 180 seconds, again if the software did not terminate by the end of 240 total execution time seconds, the tolerance might be loosened to 0.005 and for 180 seconds. Again, if the software does not terminate at the 0.005 tolerance, the tolerance might be increased to 0.01 for 180 seconds. If the software requires the full 600 seconds, only in this case will the guaranteed gap between the best solution found and the optimum exceed 0.01.

A key feature of the SSIT solutions is that they are guaranteed to be within a tight tolerance of the optimum. Another important feature of SSIT is its iterative use of any general-purpose integer programming software. These features combined with a user defined sequence of loosening tolerances and maximum execution times for each tolerance makes SSIT a very flexible yet effective solution methodology. The successful implementation of SSIT to quickly generate bounded solutions for a variety of COPs has been documented in the literature. Results on over 3000 COP instances had solutions bounded, on average, within 0.2% of the optimum and average execution times of under 2 minutes on standard PCs.