Network submatrices in mixed-integer optimization

In mixed-integer linear programming, problems with totally unimodular constraint matrices are an important class of perfect formulations, for which integer solutions can be obtained using linear programming. Network matrices and their transposes form a large subclass of totally unimodular matrices, and are related to graphs. In this dissertation, we study how (transposed) network submatrices present in mixed-integer linear programs can be exploited to reduce the solution time of mixed-integer linear programming problems.

We develop two augmentation algorithms to recognize network submatrices, which can grow a network matrix by one row or column in each step. Iterative usage of these algorithms yields a network submatrix. We show that the worst-case running time of iterative column- and row-augmentation algorithms is almost-linear and almost-quadratic time, respectively. Then we use these augmentation algorithms in two improved presolving routines for mixed-integer linear programs.

First, we study the phenomenon of implied integrality, which occurs if the problem structure implies that the integrality constraints of some variables are implicitly enforced by enforcing the integrality constraints of another set of variables. In software for solving mixed-integer linear programs, algorithms may choose whether they treat these implied integer variables as continuous or integer variables, and can utilize this choice to improve performance. We show that implied integrality can arise from totally unimodular submatrices, and detect these using the network submatrix recognition algorithms. Experimental results on representative benchmark instances show that over 18.8% of the variables in representative benchmark sets is implied integer, compared to 3.3% identified by state-of-the-art detection methods.

Second, we study a symmetry handling method for linear programming known as ``Dimension Reduction via Colour Refinement'' (DRCR) that removes symmetries using variable aggregation. We show that DRCR can be extended to the continuous variables of mixed-integer linear program. By combining implied integrality detection with affine reformulations, we derive mixed-integer programs with fewer integrality constraints that may admit stronger dimension reductions by aggregating integer variables. Using the network matrix recognition algorithms to detect implied integrality, experimental results on representative benchmark instances show that instances affected by DRCR are solved, on average, more than twice as fast.