Algorithms for solving multi-level optimization problems with discrete variables at multiple levels

In this dissertation, we investigate a class of multi-level optimization problems, in which discrete variables are present at multiple stages. Such problems arise in many practical settings, and they are notoriously difficult to optimize. Benders decomposition, which is a well-known decomposition method for solving large-scale mixed-integer programming problems, cannot be utilized for the class of problems that we consider due to the existence of discrete variables at lower levels. Cutting plane algorithms such as those proposed by Laporte and Louveaux have been designed for use in bi-level integer programming problems with binary variables at both levels. However, these are based on generic cuts, which do not utilize any problem specific structures, and hence often result in weak convergence. Our goal in this dissertation is to propose novel formulation and solution strategies for several multi-level optimization problems to solve these problems to optimality within practical computational limits.;We first consider an edge-partition problem. The motivation for this study is provided by a Synchronous Optical Network (SONET) design application. In the SONET context, each edge represents a demand pair between two client nodes, and the weight of each edge represents the number of communication channels needed between the client nodes. We consider a stochastic version of the problem, in which the edge weights are not deterministic, but their underlying probability distribution is known. The problem is to design a set of SONET “rings” at minimum cost, while ensuring that the resulting network can handle the random demand with a prespecified level of service. We first model the problem as a large-scale integer program, and attempt to solve it via a bi-level decomposition approach, in which both levels contain binary variables. We then propose a three-level solution approach for the problem, which is based on a hybrid integer programming/constraint programming decomposition algorithm. We show computationally that the hybrid algorithm significantly outperforms the other approaches.;Next, we focus on a matrix decomposition problem, which arises in Intensity Modulated Radiation Therapy (IMRT) treatment planning. The problem input is a matrix of intensity values that needs to be delivered to a patient, which must be decomposed into a collection of apertures and corresponding intensities. In a feasible decomposition the sum of binary shape matrices multiplied by corresponding intensity values is equal to the original intensity matrix. We consider two variants of the problem: (i) a variant in which the shape matrices used in the decomposition have to satisfy the “consecutive-ones” property, and (ii) a variant in which the shape matrices have to be rectangular. For the first variant, we start by investigating an integer programming model proposed in the literature, and show how the formulation can be strengthened. We then formulate the problem as a bi-level optimization problem that has discrete variables at both stages, and suggest a hybrid integer programming/constraint programming decomposition algorithm similar to our algorithm for the edge-partition problem. Our tests on data obtained from patients show that our algorithm is capable of solving problem instances of clinically relevant dimensions within practical computational limits. We then turn our attention to the second variant of the matrix decomposition problem. We formulate the problem as a mixed-integer program, and investigate a decomposition method for solving it. Unlike the first variant, the second-level problem turns out to be a linear programming problem, and therefore we are able to derive a Benders decomposition algorithm for solving this variant.;Finally, we investigate a class of graph search problems. In this class of problems, an intruder is located at an unknown node on the input graph, and a group of searchers needs to be coordinated to detect the intruder within a limited amount of time. This problem arises in settings such as search-and-rescue and search-and-capture operations, and patrol route design. We investigate three variants of the problem: (i) a hide-and-seek version, in which a stationary intruder is hiding at an unknown node, (ii) a pursuit evasion version, in which the intruder can move across the edges of the graph to avoid being detected, and (iii) a patrol problem, in which the searchers are assigned to recurring patrol routes to protect the graph from intrusion. We model each problem as a large-scale integer program, and propose a branch-cut-price algorithm to find the minimum number of searchers needed, and a route for each searcher. In our formulation, both the master problem and the subproblems corresponding to the searchers and the intruder contain binary variables. We model the master problem as a set covering problem and propose a solution approach that is based on dynamic column and row generation.