We develop and test linearization and parallelization schemes for convex mixed-integer nonlinear programming. Several linearization approaches are proposed for LP/NLP based branch-and-bound. Some of these approaches strengthen the linear approximation to nonlinear constraints at the root node and some at the other branch-and-bound nodes. Two of the techniques are specifically applicable to commonly found univariate nonlinear functions and are more effective than other general approaches. These techniques have been implemented in the Minotaur toolkit. Tests on benchmark instances show up to 12% improvement in the average time to solve the instances. Shared-memory parallel versions of NLP based branch-and-bound and LP/NLP based branch-and-bound algorithms have also been developed in the toolkit. These implementations solve different nodes of branch-and-bound concurrently. About 44% improvement in the speed and an increase in the number of instances solved within the time limit are observed when the two schemes are used together on a computer with 16 cores. These parallelization methods are compared to alternate approaches that exploit parallelism in existing commercial MILP solvers. The latter approaches are seen to perform better thus highlighting the importance of MILP techniques.
Citation
https://link.springer.com/article/10.1007/s10589-021-00335-x