AF: Small: Complexity of convex optimization with integer variables

Johns Hopkins University, Baltimore MD

Investigators

Abstract

Mathematical optimization is a key ingredient in quantitative decision making. A wide range of decision-making problems ranging from designing vehicle routes by delivery companies to minimize CO2 impact, to finding most efficient deployment of resources for national security and defense, use mathematical optimization tools. The field of optimization, studied from the times of Newton and Lagrange, has constantly encountered new challenges coming from problems in the natural and social sciences, as well as engineering and technological applications. Broadly speaking, one wishes to find the optimal values of certain parameters that minimize or maximize some objective function of those parameters, while respecting certain constraints on those parameters. In the 20th century, it has become increasingly important to handle constraints that impose the restriction that the parameters can only take discrete values. For example, when designing an optimal inventory plan for a retail store, one must decide on the number of units to stock for a certain product (say a particular type of bottled beverage) which must be a whole number (e.g., one cannot stock 10.5 bottles). While the theory and computational aspects of optimization with continuous valued parameters is very well-developed, handling constraints that model discreteness are notoriously hard. The project will aim to address some of the outstanding questions in this context. A large class of such discrete optimization problems can be modeled by using convex objective functions and constraints, apart from the restriction of integrality on the variables. The algorithmic complexity of this problem is not as well-understood as the complexity of convex optimization with continuous variables, in spite of several breakthroughs since the 1950s. In particular, an outstanding open question is nailing down the precise dependence of the running time for the best possible algorithms, on the number of integer constrained variables. This would involve not only designing an algorithm with provable complexity guarantees, but also establishing lower bounds on any algorithmic approach for the problem. The project will explore both information-theoretical lower bounds, as well as bounds that can be established under standard computational complexity hypotheses. Moreover, the analysis of algorithms that are currently deployed in practice will be undertaken from a rigorous perspective. There is ample scope for strengthening the algorithmic foundations of these methods even though they have received a lot of attention in the literature from a structural and empirical perspective. All of these questions are also known to have intimate connections with computational logic and proof complexity. The resolution of these questions will thus require bringing together techniques from areas like proof complexity, logic, computational complexity and ideas in convex geometry, geometry of numbers and polyhedral theory. Successful resolution will completely or partially resolve questions open for decades in the area, build new connections between pure mathematics and computer science, and contribute to the theoretical foundations of optimization over integers. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.