Characterizing Solvable Cases of Quadratic Binary Optimization Problems
Abstract
This project is to develop a framework for identifying and characterizing polynomially-solvable special instances of various NP-hard binary optimization problems. The characterizations will rely on the structure of the objective functions. Of particular interest are problems that are challenging when these functions are quadratic, but are readily solvable when they are linear, such as the quadratic assignment problem (QAP), the quadratic minimum spanning tree problem (QMSTP), and the quadratic shortest path problem (QSPP). Such problems arise in many settings, but state-of-the-art solution techniques lag behind the needs of motivating applications. As a result, researchers have spent much effort 1) developing tight polyhedral approximations, and 2) identifying special instances where the objective coefficients admit a polynomial-timesolution strategy. The proposed effort will merge these two previously unconnected areas of research and, in the process, lead to simplifications, generalizations, and new characterizations of solvable instances.Initial efforts will focus on characterizing instances of 0-1 quadratic programs thatare linearizable, meaning that the quadratic objective function can be equivalently rewritten as linear in such a manner that the functional value is preserved at all feasible binary solutions. Such characterizations will lead to polynomially-solvable instances of such problems as the QAP, QMSTP, and QSPP, since they are all readily solved for linear objectives. The approach isnovel in that it uses the constraints of a reformulation defined in an extended-variable space as a tool for transforming the quadratic objective.Instances of the QAP, QMSTP, and QSPP which are linearizable are clearly polynomiallysolvable. However, the converse is not true. The research will also seek to identify polynomiallysolvable instances that are not linearizable. The literature is rich with such identifications, but these results are presented independently on a case-by-case basis, with no underlying commontheory. We conjecture that many of these seemingly unrelated solvable instances can be subsumed and simplified using a common framework in terms of extended variable spaces. The effort follows a bottom-up approach that draws upon recent successes on the QAP. Investigations will initially be conducted on the QAP, and then be extended to the QMSTP and QSPP.Quadratic combinatorial optimization problems, although generally difficult to solve, play an important role in many decision making processes such as scheduling, logistics, facility location, facility layout, and the design of telecommunications/transportation networks. This effort will significantly advance current theoretical understanding of the identification and classification of readily solvable instances of such problems.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Feb 17, 2020
- Source ID
- N000142012072
Entities
People
- Lucas Waddell
Organizations
- Bucknell University
- Office of Naval Research
- United States Navy