[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
## [Help-glpk] Pricing with dual values

**From**: |
Matteo Fortini |

**Subject**: |
[Help-glpk] Pricing with dual values |

**Date**: |
Wed, 17 Nov 2004 09:56:48 +0100 |

**User-agent**: |
Mozilla Thunderbird 0.9 (Windows/20041103) |

Hi,

`I'm implementing a B&C algorithm for the TSP, and I'm using pricing in
``order to avoid inserting edges in the LP which are not needed.
``I'm thus using get_row_dual() in order to compute the reduced costs of
``the variables.
``My first question is: what sign is the value returned by get_row_dual
``(), i.e. is the auxiliary variable for a constraint introduced always
``with a + sign, or it depends on the sense of the constraint? Moreover,
``are auxiliary variables introduced even for EQ constraints?
``This is to know if the reduced cost of a variable not in the LP has to
``be computed as
`{\bar c_j} = c_j - u^T Aj
or
{\bar c_j} = c_j + u^T Aj
where u is the vector of all the values returned by get_row_dual ()

`My second question regards the case in which the LP is INFEASIBLE. Can I
``use the row duals in order to find the variables which need to be
``included in the LP in order to get it feasible again, i.e. does
``lpx_simplex put in the rows' duals the values for the first phase of the
``primal simplex? I turned off the presolver and the dual opt...
``If this is not the case, is there any other method I could use to find
``which variables are needed to form the initial basis?
`
Thank you very much,
Matteo

[Prev in Thread] |
**Current Thread** |
[Next in Thread] |

**[Help-glpk] Pricing with dual values**,
*Matteo Fortini* **<=**