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.
Year of publication: |
1969
|
---|---|
Authors: | Balas, Egon |
Published in: |
Management Science. - Institute for Operations Research and the Management Sciences - INFORMS, ISSN 0025-1909. - Vol. 16.1969, 1, p. 14-32
|
Publisher: |
Institute for Operations Research and the Management Sciences - INFORMS |
Saved in:
Online Resource
Saved in favorites
Similar items by person
-
The perfectly matchable subgraph polytope of an arbitrary graph
Balas, Egon, (1987)
-
The perfectly matchable subgraph polytope of a bipartite graph
Balas, Egon, (1981)
-
Job shop scheduling with setup times, deadlines and precedence constraints
Balas, Egon, (2008)
- More ...