From: Andrew Eremin <a.eremin_at_icparc.ic.ac.uk>

Date: Wed 05 Feb 2003 12:19:12 PM GMT

Message-ID: <3E410140.C926A0BC@icparc.ic.ac.uk>

Date: Wed 05 Feb 2003 12:19:12 PM GMT

Message-ID: <3E410140.C926A0BC@icparc.ic.ac.uk>

"Jesper Hansen Ph.D.Student (jc 1/2002)" wrote: > > Hi > > I'm doing a Branch & Price algorithm. Instead of solving the primal > master problem, I'm solving the dual master problem, adding rows instead > of columns. In this way, I can simply post the generated columns as rows > and resolve instead of setting up the entire problem at every resolve. > > Now, to do branching, I need to access the primal variables or when > solving the dual problem the values of the dual variables, in order to > check if the solution is integral and if not find constraints to branch > on. What sort of branching scheme are you using? Do you mean that you are finding a fractional primal variable and branching on its implicit bound constraints by altering the objective coefficients of the corresponding dual variables? If this is the case I would point out that branching on master problem variables will in general be rather inefficient and will also require adding constraints to the subproblems that destroy any special structural properties. Or do you mean that you have integer coefficients and convert all primal constraints to ranged constriants, then by examining the values of the primal variables you find primal constraints with fractional slack/excess that can be branched on by altering the objective coefficient of the corresponding dual variable? If this is the case you can more easily determine potential branching constraints by examining the reduced costs of the dual variables which correspond to the slack/excess of the primal constraints. Of course neither of these observations helps the fact that you will still need to obtain the optimal primal solution. > I notice that fewer dual values are returned by eplex than added > rows. This is unfortunate since I don't know which, and what the values > are of the remaining. A way around this is to setup and solve the primal > master problem in each master iteration, but again I cannot be sure to > get all the dual variables to send to the pricing problem. I hope the > conclusion is NOT that I'll have to solve both the primal and the dual > problem in each iteration, which seems a bit inefficient and cumbersome. > Alternatively, if I could be sure that all posted rows were actually > sent to the solver without any reductions from ECLiPSe, then I would > receive all dual variables of the dual master problem (the primal > variables of the primal master problem). Is that possible or do you have > any other suggestions? Eplex performs propagation before passing constraints to the external solver. The only constraints that eplex doesn't pass to the external solver are those that are ground or involve a single variable bound update after propagation. I suppose this could happen e.g. if you generate a primal variable with 0 objective coefficient for a minimization primal master problem so the dual constraint is sum uA =< 0. The constraint simplification can be avoided by adding an unrestricted dummy variable to all dual constraints before posting them to eplex, and then simply setting it to 0 before solving the lp. The external solver may also remove some constraints during presolve. You can tell which constraints are present using lp_get(+Handle, constraints, -Constraints) or EplexInstance:eplex_get(constraints, -Constraints) and the order they are returned in should correspond to the order of the dual values. The simplification of constraints by the external solver can be avoided by either calling lp_set(presolve, 0) before setting up the solver or by specifying presolve(no) in the ListOfOptions argument of EplexInstance:eplex_solver_setup(+Objective, ?Cost, ++ListOfOptions, ++Priority, +TriggerModes) Finally, I've been working on a column generation library which allows adding new columns to existing constraints. When this is included in the eclipse distribution the necessity to work with the dual to avoid repeated lp setups will be removed. -- Andrew Eremin Research Assistant Tel: +44 (0)20 7594 8299 IC-Parc, Imperial College London Fax: +44 (0)20 7594 8432 London SW7 2AZ Email: a.eremin@icparc.ic.ac.ukReceived on Wed Feb 05 12:19:52 2003

*
This archive was generated by hypermail 2.1.8
: Wed 16 Nov 2005 06:07:21 PM GMT GMT
*