NSF Award: (Mixed) Integer and Combinatorial Optimization: New Convexification Techniques

A new NSF Award was recently given to Egon Balas on (Mixed) Integer and Combinatorial Optimization: New Convexification Techniques.

The objective of this research project is to investigate new ideas that could potentially further accelerate the revolution in integer programming. This project will investigate more efficient convexification techniques: a new cutting plane paradigm that generates a pool of points from which cuts can be produced, and a theory of cut-generating functions, both aimed at finding deeper cuts more efficiently. Integer programming has experienced a revolution in the last two decades that has greatly advanced our ability to solve practical problems in engineering, manufacturing, transportation, telecommunication, finance, marketing and many other areas of economic activity. According to recently performed extensive testing, integer programming solvers are now close to a billion times faster than they were twenty years ago. Better integer programming algorithms (including their linear programming components) account for a speedup of about half a million times, the rest of the improvement (by a factor of about 1600) coming from faster computers. A key element of this transformation was a breakthrough in the use of cutting planes in the early nineties, including the design of the lift-and-project cuts and the ensuing revival of the Gomory mixed integer cuts, two projects carried out by the principal investigators with previous NSF support.


Progress in the ability to solve large-scale mixed integer linear programs will affect problem solving and improve efficiency of operations in an extremely broad range of activities that include industrial production, supply chain management, logistics, transportation, electricity production, airport operations, telecommunication networks, health care applications such as scheduling intensive care units and determining radiation dosage, combinatorial auctions, finance and economics. The widespread impact of tools developed in this project will contribute to technological excellence and strengthen US technological leadership.

NSF Award: Efficiently Computable Convex Approximation Methods for Non-Convex Optimization Problems

A recent NSF Award is given to Luis Zuluaga on Computable Convex Approximation Methods for Non-Convex Optimization Problems.

This research project takes on the challenge of closing the large gap between the current ability to solve convex or integer-linear optimization problems and the capacity to solve non-convex optimization problems by introducing novel methodologies to solve this class of problems using polynomial optimization techniques. In particular, the research will be focused on the following three main directions. The first direction is the introduction of new polynomial optimization techniques that instead of solving non-convex problems exhaustively, do so dynamically. The second one is the introduction and effective use of polynomial optimization results that beyond semidefinite programming tools make full use of the powerful convex optimization toolkit. The third one is the use of polynomial optimization results, related to the convex reformulation of low-dimensional or low-degree non-convex problems, as the foundation to obtain better reformulations for general non-convex problems. This project's practically oriented research is aimed at solving key and difficult decision-making problems that are now regularly faced in the communications, healthcare, electricity, and oil and gas industries. Many times, the difficulty to solve these problems arises from the use of polynomials to closely model the behavior of real-world systems. Modeling real-world systems more accurately is an overarching need in today's competitive and resource-constrained environment.
The results of this research will substantially improve computer-based solvers for this class of problems. The software developed to achieve this goal will use open source software tools that will be made available to the public. The corresponding positive impact on profits, safety, resource management, client satisfaction, etc., will further broaden the practical successes that make Operations Research the "Science of the Better". Furthermore, the challenging nature of this research will provide ample opportunity to the participating graduate students to excel, and its results will be incorporated into appropriate graduate level courses.