DUALITY IN DISCRETE PROGRAMMING: II. THE QUADRATIC CASE.

This paper extends the results of "Duality in Discrete Programming" [1] to the case of quadratic objective functions. The paper is, however, self-contained. A pair of symmetric dual quadratic programs is generalized by constraining some of the variables to belong to arbitrary sets of real numbers. Quadratic all-integer and mixed-integer programs are special cases of these problems. The resulting primal problem is shown, subject to a qualification, to have an optimal solution if and only if the dual has one, and in this case the values of their respective objective functions are equal. The dual of a mixed-integer quadratic program can be formulated as a minimax problem whose quadratic objective function is linear in the integer-constrained variables, and whose linear constraint set does not contain the latter. Based on this approach an algorithm is developed for solving integer and mixed-integer quadratic programs. [ABSTRACT FROM AUTHOR]

Copyright of Management Science is the property of INFORMS: Institute for Operations Research and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)