[Scip] Column generation method (binpacking example)

[Luigi Malagò]

Thanks to both of you for the kind replies,

1) SCIPprintTransProblem solved my problem.
2) and 3) thanks for the clarification

just a comment on this:


>>Constraints in SCIP can be locally (or globally) disabled, e.g. by
>>SCIPdelConsLocal(). In the binpacking example, the set covering
>>constraint which ensures that one item is assigned to at least one bin
>>is disabled whenever one packing containing this item is locally fixed
>>to one.

this is because in that case the constraint is not need anymore. anyway,
disabling the constraint is just to improve performance in this case, right?
i mean if i dont do that, i would obtain the same solution, even if the
number of constraint is bigger..

>>This item is then also not respected in the pricing problem
>>anymore. At the lines that you mentioned, a variable was created for a
>>solution of the pricing problem (packing) and is added to the set
>>partitioning constraints which belong to items contained in the packing.
>>The item corresponding to a disabled constraint is not regarded in the
>>pricing problem and must thus not be contained in the packing,
>>therefore, all the constraints have to be enabled, which is just
>>asserted to ensure correctness.

ok i got this


---------------------------


Now, two other similar questions, about master and pricing ;-)

In the "master problem" / "pricing problem" loop, i stop when i dont find
any other solution with reduced cost. At each iteration I can print the
different pricing problem as expected.

These are my two new questions

a) is there a way to access the objective value of the LP relaxation of the
master program from the callback function where the pricing problem is
solved? i'm not sure, but i guess that using
SCIPprintBestTransSol
binary variables remain binary and i dont see the LP relaxation.
i'm not sure if i should see some real variable during the solution of my
problem, but at a certain point i would expect real values, that i dont see
so far.

b) i'm comparing my SCIP implementation with a previous AMPL implementation
of same the master/pricing loop.
i've notived that stating from iteration 3, the solution of the pricing
problem starts to differ from the SCIP implementation. the reason is that in
the previous iteration of the master, the dual variables associated to the
constraints are different in AMPL and SCIP, even if the solution of the
master problem is the same. i notice that i can change these (dual
solutions) in AMPL for instance by changing the level of presolve tolerances

>>The presolve option specifies the maximum number of passes to be made by
the presolve phase. Thus option
>> presolve 0 turns off all presolving, and option presolve 1 applies only
the more elementary
>> simplifications. The default value is 10.

for instance, in AMPL with presolve 0 i get solutions to the pricing problem
different from SCIP even at the first iteration, with  presolve 10 (default
value) at the first two iterations new variables are the same, but they
change at the third. i would like to obtain for both implementation the same
sequences of variables.

any idea if there are parameters in SCIP that could effect this behavior
(that is the value of the dual solutions associated to the constraints of
the master)?

thanks a lot again for your help,
it is really appreciated!

luigi


On Fri, Aug 19, 2011 at 7:06 PM, Gerald Gamrath <gamrath at zib.de> wrote:

> Hi Luigi,
>
> > what i dont understand, is my when i print the master problem, i dont
> > see the pricing variables i have added (i only see them in the
> > solution, not in the problem definition)
> This is because the original problem is not changed during the solving
> process and the variables that are priced in are only added to the
> transformed problem. Thus, in order to print out the problem, you should
> use the method SCIPprintTransProblem().
> > 2) second question:
> > in my code, in pricerRedcostBinpacking, first i add the new pricing
> > variable, and add it also to an existing constraint of the master
> > problem with
> >
> > SCIP_CALL( SCIPaddPricedVar(scip, var, 1.0) );
> >
> > and
> >
> > for( v = 0; v < nconss; ++v ) {
> >   assert(SCIPconsIsEnabled(conss[consids[v]]));
> >   SCIPprintCons( scip, conss[consids[v]], NULL );
> >   SCIP_CALL( SCIPaddCoefSetppc(scip, conss[consids[v]], var) );
> >   SCIPprintCons( scip, conss[consids[v]], NULL );
> > }
> >
> >
> > but i ALSO add new variables (that are not new packings as in
> > binpacking, but "auxiliary" variables) and new constraints that
> > involve pricing variables and non other variables to the master problem
> > in that case should i use SCIPaddVar and SCIPaddCons?
>
> Yes, in this case, you should use SCIPaddVar() and SCIPaddCons().
> > 3) can somebody explain be a little bit the meaning of SCIPconsIsEnabled.
> > for example, in the for cycle above, why to check the constraint is
> > enabled?
> Constraints in SCIP can be locally (or globally) disabled, e.g. by
> SCIPdelConsLocal(). In the binpacking example, the set covering
> constraint which ensures that one item is assigned to at least one bin
> is disabled whenever one packing containing this item is locally fixed
> to one. This item is then also not respected in the pricing problem
> anymore. At the lines that you mentioned, a variable was created for a
> solution of the pricing problem (packing) and is added to the set
> partitioning constraints which belong to items contained in the packing.
> The item corresponding to a disabled constraint is not regarded in the
> pricing problem and must thus not be contained in the packing,
> therefore, all the constraints have to be enabled, which is just
> asserted to ensure correctness.
>
> Best,
> Gerald
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/mailman/private/scip/attachments/20110822/65b50430/attachment.html