UC Berkeley

Binary Conic Quadratic Knapsack set is the lower level set of the conic quadratic set functions. They are natural generalizations of linear knapsack sets, and have several applications in several areas, such as, combinatorial optimization, finance, and optimal control. In particular, conic quadratic knapsacks can be used to model the 0-1 linear knapsack sets with uncertain coefficients. In addition to being of theoretical interest, these problems are practically relevant as they can be used to mathematically formulate probabilistic and robust equivalents of the deterministic combinatorial and decision problems.

Although the non-linear binary sets, specifically the quadratic knapsack sets have been studied in the literature, the specific combinatorial structure associated with these sets remains to be explored. Non-linear binary sets involving bilinear terms are at present solved using a combination of lift and project relaxations and a branch-and-bound scheme that solves continuous non-linear relaxations at the nodes of a branch-and-bound search tree. The branch-and-cut methods developed for general integer conic quadratic sets make use of the problem's geometrical structure for removing fractional solutions of conic relaxations can be employed to solve the particular case of 0-1 conic quadratic knapsacks, however these approaches do not utilize the additional combinatorial structure specific to these sets. Motivated by the performance improvement observed by exploring geometrical structure for conic mixed integer programs, and the fact that exploring combinatorial structure has proven extremely useful in addressing the linear $0-1$ knapsack sets, we expect this to work well in the case of conic quadratic knapsacks as well.

In this dissertation, we study pure-binary programs with conic quadratic constraints and develop branch-and-cut algorithms to solve them with applications to robust network design problem. First, we study the combinatorial structure embedded into these problems with assumptions of monotonicity and develop valid inequalities for these problems. In Chapter 2, we consider a more general version of the problem without any monotonicity assumptions on the conic constraint, and derive valid inequalities linear in the space of the original variables. These cuts generalize a well-known class of linear cuts for binary knapsacks, and turn out to be very effective in reducing the computational effort involved in solving some practical problems.

In Chapter 3, we propose a further generalization of the problem without any structural assumptions of the constraint in context and study the binary quadratically constrained set. We show that our results generalize several known results for the 0-1 non-linear constrained sets. We take a detour from combinatorial discussion and develop a geometrical understanding for 0-1 quadratic problems in Chapter 4. We develop convexifications for the non-convex quadratic sets defined over a hypercube and provide strengthening procedures for the same.

Finally, in Chapter 5, we study the problem of robust network design with uncertainties on the arc capacities. We formulate the robust network design problem as a 0-1 conic quadratic program without particular assumptions on the characteristics of uncertainties. We consider the scenarios when the uncertainties on the arc capacities are independent and correlated. We show that the inequalities derived prove to be useful in our computational experiments.