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

[Markus Leitner]

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
>


-- 
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)