Thesis Title: Exploiting Structure in Mixed Integer Programming: Branching, Cutting Planes and Complexity

Advisors: 

Dr. Martin Savelsbergh, School of Industrial and Systems Engineering, Georgia Tech

Dr. Natashia Boland, School of Industrial and Systems Engineering, Georgia Tech

Committee members:

Dr. Alan Erera, School of Industrial and Systems Engineering, Georgia Tech

Dr. Santanu Dey, School of Industrial and Systems Engineering, Georgia Tech

Dr. Bistra Dilkina, School of Computer Sciences, University of Southern California

Date and Time: 10 - 12 pm ET, Tuesday July 14, 2020

Meeting URL: https://bluejeans.com/1536597757

Meeting ID: 153 659 775 7 (bluejeans)

Passcode: 1025

Abstract:

                As a powerful mathematical modeling framework, mixed integer programming (MIP) has seen many industrial applications in areas such as logistics, scheduling, capital budgeting, etc. Tremendous algorithmic advances have been achieved and state-of-the-art solvers, such as CPLEX and Gurobi, can now solve previously unsolvable instances in just seconds. However, many instances, especially if the underlying problem has a complex structure and the instances are large, can still take a long time to solve. In this dissertation, we take on the challenge of solving MIPs faster through novel branching schemes and novel cutting planes. Via computational complexity analysis, we also justify the usage of MIPs for approaching challenging problems and inspire the design of primal heuristics.

The first part of the thesis focuses on novel branching schemes. We explore the benefits of multi-variable branching schemes in achieving node efficiency, i.e., producing small sized branch and bound search trees. Furthermore, we show that machine learning (ML) techniques can significantly accelerate the selection of sets of variables to branch on and thus turn multi-variable branching schemes into computationally efficient methods. 

                In Chapter 2, we use the 0-1 knapsack problem as an illustrative example. We present examples where multi-variable branching has advantages over single-variable branching, and partially characterize situations in which this happens. For a special class of 0-1 knapsack instances from [Chv 80], we show an LP based branch-and-bound algorithm employing an appropriately chosen multi-variable branching scheme explores either three or seven nodes while it's proved in [Chv 80] that a single-variable branching counterpart must explore exponentially many nodes to arrive at an optimal solution. Furthermore, we investigate the performance of various multi-variable  branching schemes for  0-1 knapsack instances computationally and demonstrate their potential. 

                In Chapter 3, we introduce a multi-variable branching analogy of strong branching (SB), to which we refer as generalized strong branching (GSB). Unfortunately, even though GSB outperforms SB, a straightforward implementation is prohibitively time-consuming. Therefore, we apply extreme gradient boosting to train a model that predicts the ranking of (sets of) candidate variables. To make a branching decision, it now suffices to collect (computationally cheap) features as input to the trained model to efficiently identify a set of variables to branch on. As a result, we achieve a significant time reduction in making the branching decisions and the learned method is able to solve instances of three well-known classes of optimization problems faster than the default branching strategy of commercial solver CPLEX.

                The second part of the dissertation addresses two problems arising in service networks. We approach the first problem of interest from a pure cutting plane perspective and focus on analyzing the theoretical complexity of the second problem.

                In Chapter 4, we consider the service network design problem with in-tree constraints (SNDPITC). We compare the size and strength of three existing Steiner in-tree formulations and introduce three integer programming (IP) formulations for the SNDPITC based on them. We compare the size and strength of linear programming (LP) relaxations for these three IP formulations and provide some simple strengthening inequalities. Then we focus on the most compact of the three, the flow-based formulation, and derive six new classes of cutting planes. We discuss separation challenges and present ideas for separation heuristics. Finally, as a proof-of-concept, we conduct numerical experiments to show that violated inequalities can be identified and that they can improve the dual bound.

                In Chapter 5, we focus on the equipment balancing problem for a package express carrier operating multiple equipment types in its service network. We seek to reduce the imbalance by substituting the equipment types initially assigned to the movements. To the best of our knowledge, the underlying optimization problems, i.e., minimizing network-wide equipment imbalance and minimizing the number of substitutions required to achieve minimum network-wide equipment imbalance have not been studied and thus their computational complexity was unknown. We carefully analyze several simplified cases and prove the possibly discouraging, but not surprising, result that they are NP-hard in general.

Best regards,

Yu Yang