Combinatorial Optimization: Algorithms and Applications
Abstract
Short Work Statement The proposed research will develop theory and algorithms for solving integer-programming problems based on cutting-plane techniques. Objective The purpose of this project is to obtain new breakthroughs in integer programming. A powerful way of strengthening integer programs is to solve their linear-programming relaxation and then generate cutting planes that cut off the resulting optimal solution whenever it is not feasible to the integer program. The research will focus on cutting-plane techniques for integer linear programming. Extension to integer conic programming will also be investigated. Approach Various cutting planes such as Gomory cuts, mixed-integer rounding cuts, and others are quite effective in practice. These cutting planes are generated using cut-generating functions that can be applied universally to different data. Understanding what makes these functions applicable to all integer linear programming formulations irrespective of the particular data is a fundamental aspect of this research. One direction aims at developing a theory of cut-generating functions for a tighter relaxation than the one currently used in solvers, obtained by strengthening the classical corner polyhedron. Another direction investigates a new cutting plane paradigm: a pool of intersection points is maintained instead of the traditional pool of cuts. The recent success in integer linear programming can be extended to other classes of optimization problems such as integer nonlinear programming and stochastic programming. We propose to investigate several such extensions. In particular, we would like to explore the disjunctive cut framework in the context of conic integer programming. Overall Merits and ONR Mission/Relevance The proposed research will develop state-of-the-art methods for solving integer-programming problems. Integer programming is extremely useful for solving resource-allocation problems that arise in a variety Navy-relevant contexts, such as mission planning. The proposed research will develop greatly improved methods for resource optimization.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Aug 08, 2016
- Source ID
- N000141512082
Entities
People
- Egon Balas
Organizations
- Massachusetts Institute of Technology
- Office of Naval Research
- United States Navy