[Scip] Column generation method (binpacking example)

[Luigi Malagò]

i think i solved question a)

SCIP_RETCODE<http://scip.zib.de/doc/html/type__retcode_8h.html#ac847f5a370187651fbc1b82d0170b480>SCIPprintSol
( SCIP<http://scip.zib.de/doc/html/type__scip_8h.html#a4792a242d315bf76f05b1f4e0712bc33>*
*scip*,

SCIP_SOL<http://scip.zib.de/doc/html/type__sol_8h.html#a76b0c06e8d5c166fe241cced9564ce90>*
*sol*,

FILE *  *file*,

SCIP_Bool  *printzeros*
)

outputs non-zero variables of solution in original problem space to file
stream
*Parameters:* scipSCIP data structure solprimal solution, or NULL for
current LP/pseudo solution fileoutput file (or NULL for standard output)
printzerosshould variables set to zero be printed?
luigi


On Mon, Aug 22, 2011 at 11:36 AM, Luigi Malagò <luigi.malago at gmail.com>wrote:

> 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/b471902d/attachment.html