Dual linear program

Optimization Techniques in Routing

Published in Charles J. Alpert, Dinesh P. Mehta, Sachin S. Sapatnekar, Handbook of Algorithms for Physical Design Automation, 2008

Christoph Albrecht

By linear programming duality (a comprehensive overview about linear programming can be found in the books by Chvátal [12] and Schrijver [13]), any feasible solution of the dual linear program provides a lower bound on the optimum solution for the primal linear program, and for the optimum solutions equality holds.

Efficiency drivers in harvesting operations in mixed Boreal stands: a Norwegian case study

View Article

Journal Information

Published in International Journal of Forest Engineering, 2021

Giovanna Ottaviani Aalmo, Pieter Jan Kerstens, Helmer Belbo, Peter Bogetoft, Bruce Talbot, Niels Strange

Here the subscript 0 refers to the DMU under evaluation. The program picks weights u0, v0 for DMU 0 such that DMU 0 appears as best as possible. By construction, (2) cannot be larger than 1. This program is nonlinear because of the unknowns v0 in the denominator. In order to operationalize this, Charnes et al. (1978) normalize the denominator by imposing the extra normalizing constraint v0X0 = 1. This turns the program into a linear programming problem. From duality results of convex analysis, this linear program has an equivalent dual linear program whose objective has the same value (Rockafellar 1970). This dual linear program has a useful connection to the production theory.

Dual linear program

Explore chapters and articles related to this topic

Optimization Techniques in Routing

Efficiency drivers in harvesting operations in mixed Boreal stands: a Norwegian case study