Duality in Discrete Programming: II. The Quadratic Case

Egon Balas

Management Science, 1969, vol. 16, issue 1, 14-32

Abstract: 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.

Date: 1969
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.16.1.14 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:16:y:1969:i:1:p:14-32

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().