Author Description

An optimization problem is trying to minimize or maximize a real objective function such that the input variables satisfies certain constraints. The simplest optimization problem is the linear program (LP), which has been proved to be in the P class and are usually solved by the simplex method or interior point methods. However, imposing integral constraints to an optimization problem can make the problem difficult to solve, and the mixed integer program (MIP) belongs to the NP-hard class. Mixed integer optimization problems have a large number of applications in various fields, such as operations research and machine learning. Although MIP are typically hard to solve, the good news is that researchers are making substantial progress on solving problems more efficiently using better computation powers and more robust algorithms. Cutting plane algorithms, which were first proposed by Gomory and Johnson in the 1960s, are widely used in the state-of-the-art solvers. In the cutting plane algorithms, a family of real functions (so called cut-generating functions) are used to provide valid constraints to the optimization problem so that they can be solved faster. Cut-generating functions are typically piecewise linear functions and satisfy subadditivity. In this dissertation, we study the subadditivity of piecewise linear functions and use a software to verify subadditivity more efficiently. It is important to verify subadditivity of a cut-generating function before applying it to optimization problems. As the structure of the cut-generating function gets complicated, the existing algorithm can take a very long time to verify subadditivity. We develop a spatial branch and bound algorithm to prove or disprove subadditivity of a given piecewise linear function. We use a benchmark work to show that the new algorithm works better for functions with complicated structures. We also address the reproducibility of the benchmark work, and we provide a open sourced repository so th