[Scip] About column generation in VRP example

[Benjamin Müller]

Dear Feng,

please note that the master consists of (continuous) tour and (integral) 
arc variables. This brings the advantage that it is sufficient to branch 
on the arc variables only. Of course, you can formulate the master 
problem without arc variables but then you need integrality requirements 
on the tour variables. This brings the problem that branching on the 
tour variables changes the nature of the pricing problem and thus it is 
not solvable with the help of dynamic programming anymore.

In contrast to this, branching on the arc variables does not really 
change the pricing problem. y_e = 0 just removes edge e from the graph 
you use to search for the tour with the most negative reduced cost. y_e 
= 1 does not change anything.

Write me a personal mail if you have more questions about the VRP example.


Best regards,

Benny


On 04/01/2015 02:39 PM, Feng Gao wrote:
> Dear all,
>
> Is there anybody familiar with the VRP example in SCIP?
> When the pricer find a tour with negative reduced cost, why was the 
> column added back in the form of arc variable? Is the problem in the 
> main program master problem or original problem? If it is master 
> problem, adding back arc variable does not make sense.
>
> Sorry if this is a rather easy question. But I heard that the problem 
> should be the master problem in the main program.
>
> Best regards,
>
> Feng Gao
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip

-- 
______________________________
Benjamin Müller
Zuse Institute Berlin
Takustr. 7, 14195 Berlin
benjamin.mueller at zib.de
+49 30 841 85-195

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20150401/44ce5209/attachment.html>