[Scip] Column generation method (binpacking example)

[Gerald Gamrath]

Hi Luigi,
> >>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..
Yes, it would also be correct if the constraint would stay enabled. 
However, the solving process might change, since you have another LP, 
might get other optimal solutions, and also this constraint might have a 
nonzero dual solution value leading to other solutions in the pricing 
problem.

> 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.
Yes, SCIPprintBestTransSol() prints the best feasible solution, i.e. all 
integer variables have to have integer values. But you can use 
SCIPprintTransSol() with parameter sol set to NULL to print the LP 
solution. You could also use SCIPgetSolVal(s)() to get the solution 
values of one or more variables returned as a real if you want to use 
them in your code and not print them.
> 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)?
This is not so easy. Since there are often many optimal primal or dual 
LP solutions, it is not wrong that one solver computes another solution 
than the other. If you use different LP solvers in AMPL and SCIP, it 
would just be by chance if you get the same solution. But even if you 
use the same LP solver, the LP might be built in a different order of 
constraints or variables or some parameters might be different which can 
lead to a different solution process. Does the SCIP presolving change 
the problem? I would assume that it does not. Otherwise, you could 
disable presolving in SCIP. Another thing you could try is to use the 
same epsilon values in SCIP and AMPL. Anyway, I doubt that you get the 
exact same solution behavior in both AMPL and SCIP.

Best,
Gerald