Mixed integer nonlinear programming (MINLP) is a branch of combinatorial optimization which finds a wide range of applications in academics and industry. For example, unit commitment in electric power industry and telecommunication network design are naturally MINLP problems. However, MINLP problems are very difficult to solve, since the number of local optimal solutions tends to grow exponentially as the problem dimension increases.
Currently, branch & bound (B&B) algorithm and its variants (e.g. branch & cut (B&C), hybrid methods integrating B&B or B&C with heuristic searches) are the most viable tools to tackle practical MINLP problems. Despite their popularity, B&B related methods still suffer from some major issues, namely: 1) accuracy of the solutions obtained within limited time is not predictable; 2) a global optimal solution is not guaranteed; and 3) these methods are still very time-consuming. Resolutions to these issues will significantly improve the viability of B&B related methods in solving large-scale MINLP problems.
To this end, we have developed novel methods where the TRUST-TECH methodology is used to enhance and guide the conventional B&B search. The TRUST-TECH-enhanced B&B method and the TRUST-TECH-guided B&B method can bring a substantial improvement in solution quality and robustness, and usually the global-optimal integer solution is achieved. In the meantime, the computational efficiency can also be significantly improved.