[Scip] [Fwd: Re: Reject "feasible" solutions]

[Gerald Gamrath]

Hi Markus,
> I am following the concept of 5-piecewise linear stabilization functions
> (in the dual) as proposed in
> * Ben Amor, Desrosiers: A proximal trust-region algorithm for column
> generation stabilization, Computers&  Operations Research 33, 910-927, 
> 2006
>
> If any of these additional variables is nonzero when the CG process
> stops, this means that I am not inside the trust regions which then
> needs to be updated.
> All I would like to do is to modify the objective values of the nonzero
> variables.
> Since SCIP tells me that I am not allowed to do this (in this stage), I
> am currently fixing these variables to zero and add new ones.
> So far this workaround seems ok, as there are not too many such updates.
> I am of course open for your suggestions on this ...
As you noticed, it is currently not allowed to change the objective 
value of variables during the solving process, because some presolving 
and propagation steps and also the bounding itself relies on the 
objective function staying unchanged.The workaround you implemented 
should work as long as the updates do not happen to often and you 
implement the special constraint handler proposed in the previous mail.
The clean solution would probably be to implement your own relaxator or 
even your own LP interface, since the artificial variables are just 
needed for the LP solving and can be ignored for the MIP model.
Besides, we are currently thinking about a clean way to allow the user 
to change the objective coefficients during the solving (probably in 
probing mode) in order to provide an easy way to implement stabilization 
in column generation applications.

Best, Gerald


Markus Leitner schrieb:
> Hi Timo and Gerald,
>
> On 02/02/2011 07:04 PM, berthold at zib.de wrote:
>   
>> Hi Markus.
>>
>>     
>>> Is there any way to reject a found solution, e.g. by some event handler?
>>>       
>> Well, you could use a small constraint handler, that only implements the
>> checking and enforcement callbacks and rejects those solutions which you
>> dislike.
>>     
>
> Thanks, I'll try this.
>
>   
>> However, your description sounds like something else is dodgy. How do you
>> add /remove these variables? Are they added to any (and what type of)
>> constraints? Do you change the objective coefficient of any variables? How
>> do you ensure that these variables will be zero at the end of the LP
>> solve? Which heuristic(s) find(s) the unloved solutions? My wild guess is
>> that it might be simple rounding.
>>
>> Cheers,
>> Gerald and Timo
>>
>>     
> I am following the concept of 5-piecewise linear stabilization functions 
> (in the dual) as proposed in
> * Ben Amor, Desrosiers: A proximal trust-region algorithm for column 
> generation stabilization, Computers & Operations Research 33, 910-927, 2006
>
> If any of these additional variables is nonzero when the CG process 
> stops, this means that I am not inside the trust regions which then 
> needs to be updated.
> All I would like to do is to modify the objective values of the nonzero 
> variables.
> Since SCIP tells me that I am not allowed to do this (in this stage), I 
> am currently fixing these variables to zero and add new ones.
> So far this workaround seems ok, as there are not too many such updates.
> I am of course open for your suggestions on this ...
>
> The unloved solutions are indeed found by simple rounding.
> (I do, however, currently not include the more sophisticated primal 
> heuristics).
>
> Regards,
> Markus
>
>   
>>> Hi everyone,
>>>
>>> I am currently developing and comparing various stabilization methods to
>>> accelerate a branch-and-price approach.
>>>
>>> In one of them I need to add further (fractional) variables with
>>> negative objective values (minimization problem).
>>> In any solution feasible in the original model all these variables will
>>> have zero values and I can ensure that this is true for the LP solution
>>> at the end of each node in the branch-and-bound tree.
>>>
>>> It, however, occurs that primal solutions are found by some of the build
>>> in heuristics for which some of these variables have nonzero values.
>>> In this case, the corresponding objective value may be smaller than the
>>> real optimal solution.
>>>
>>> Is there any way to reject a found solution, e.g. by some event handler?
>>> Otherwise, I guess I need to disable all heuristics which might slow
>>> down the whole process.
>>>
>>> Regards,
>>> Markus
>>>
>>>
>>> --
>>> Markus Leitner
>>> Institute of Computer Graphics and Algorithms
>>> Vienna University of Technology
>>> Favoritenstrasse 9-11/1861, 1040 Vienna, Austria, Europe
>>> email: leitner at ads.tuwien.ac.at   |  phone: +43(1)58801/18624
>>> http://www.ads.tuwien.ac.at       |  fax:   +43(1)58801/18699
>>> (DVR: 0005886)
>>>
>>> _______________________________________________
>>> Scip mailing list
>>> Scip at zib.de
>>> http://listserv.zib.de/mailman/listinfo/scip
>>>
>>>       
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> http://listserv.zib.de/mailman/listinfo/scip
>>
>>     
>
>
>