[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)

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
{\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,

reply via email to

[Prev in Thread] Current Thread [Next in Thread]