[Scip] Providing SCIP with an initial solution for a MIP

Timo Berthold berthold at zib.de
Fri Oct 21 09:29:02 MEST 2011


Hi Sebastian.

This is currently not supported in SCIP.
One could theoretically implement a primal heuristic that fixes variables
to predefined values and solves a sub-SCIP or a branching rule that does
the first branch (left: all variables fixed to the pertial solution,
right: at least one variable takes a different value).

The easiest way, if you use SCIP as a callable library, would be:

...
for( i = 0; i < nfixvars; ++i)
   SCIP_CALL( SCIPchgVarLb(scip, fixvars[i], 1.0) );

SCIP_CALL(SCIPsolve(scip) );

if( SCIPgetNSols(scip) == 0 )
{
   SCIP_CALL( SCIPfreeTransform(scip) );
   for( i = 0; i < nfixvars; ++i)
      SCIP_CALL( SCIPchgVarLb(scip, fixvars[i], 0.0) );
   SCIP_CALL( SCIPsolve(scip) );
}
...

That does not seem to be such a lot of work. ;-)

In the interactive shell, you would just read in the fixed values and
solve again, if necessary.

SCIP> read sebastian.tsp
SCIP> read partial.fix
SCIP> optimize
SCIP> read sebastian.tsp
SCIP> optimize

Cheers, Timo

>   Hello,
>
> I know this thread is about a month old but I would like to reopen it.
> And I would like to answer a question Marc asked:
> "What would you want to do with a partial solution?"
> Suppose you have a TSP and know a partial tour but you are not sure if
> this partial tour is feasible. I want to give this to SCIP and let it
> complete the tour. However, if it can't complete the tour, I want it to
> automatically discard the partial tour and resolve.
>
> Of course you could fix the variables for the partial tour and let it
> solve. Then if it's infeasible unfix and solve again. But that seems to
> be a lot of work for something so intuitive.
>
> Cheers,
> Sebastian
>
> On 19/09/2011 2:34 AM, Timo Berthold wrote:
>> Dear Jörg,
>>
>> if you are using SCIP as a callable library rather than via the
>> interactive shell, please check:
>> http://scip.zib.de/faq.shtml#Q13
>>
>> The same holds: infeasible solutions will be discarded, nothing special
>> is
>> done for partial solutions.
>>
>> Cheers,
>> Timo
>>> Hi Jörg,
>>>
>>> in the command line environment of SCIP you can first load you MIP and
>>> then a solution file - the solution file should end with ".sol".
>>>
>>> If the solution is partial or infeasible, it is discarded, because SCIP
>>> does not know what to do with it. What would you wnat to do with such a
>>> partial/infeasible solution?
>>>
>>> Best,
>>>
>>> Marc
>>>
>>>
>>>
>>> On 09/18/2011 17:57, "Jörg Pfähler" wrote:
>>>> Hi,
>>>>
>>>> Is it possible to give a (partial or full) solution of a MIP to SCIP
>>>> (before the solving process starts)? If so, how would I do that and
>>>> what
>>>> happens if that solution is infeasible or if it is only a partial
>>>> solution?
>>>>
>>>> With best regards,
>>>> Jörg Pfähler
>>> _______________________________________________
>>> 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
>>
>>
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip
>



More information about the Scip mailing list