Re: Branch & Price

"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.uk