<html><head><meta http-equiv="content-type" content="text/html; charset=ISO-8859-1"><style>body { line-height: 1.5; }blockquote { margin-top: 0px; margin-bottom: 0px; margin-left: 0.5em; }body { font-size: 12pt; font-family: Calibri; color: rgb(0, 0, 0); line-height: 1.5; }</style></head><body>
<div><span></span>Dear Ambros,</div><div><br></div><div>Thanks. </div><div>I do not understand case 3: </div><div><span style="font-size: 12pt; line-height: 1.5; background-color: window;">same for slacks of inequality constraints and their dual multipliers</span></div><div><span style="font-size: 12pt; line-height: 1.5; background-color: window;">Could you please explain it? </span></div><div><span style="font-size: 12pt; line-height: 1.5; background-color: window;"><br></span></div><div><br></div><div><span style="font-size: 12pt; line-height: 1.5; background-color: window;">In my model, all x variables are binary. All z variables are continuous with bounds [0,1].</span></div><div><br></div><div>Do you mean I should use lazy bound for x variables in my branch-and-price? </div><div><br></div><div><br></div><div>Thanks,</div><div><br></div><div>Xiangyong</div>
<blockquote style="margin-top: 0px; margin-bottom: 0px; margin-left: 0.5em;"><div> </div><div style="border:none;border-top:solid #B5C4DF 1.0pt;padding:3.0pt 0cm 0cm 0cm"><div style="PADDING-RIGHT: 8px; PADDING-LEFT: 8px; FONT-SIZE: 12px;FONT-FAMILY:tahoma;COLOR:#000000; BACKGROUND: #efefef; PADDING-BOTTOM: 8px; PADDING-TOP: 8px"><div><b>From:</b> <a href="mailto:gleixner@zib.de">Ambros Gleixner</a></div><div><b>Date:</b> 2014-08-12 16:14</div><div><b>To:</b> <a href="mailto:lixiangyong@163.com">lixiangyong@163.com</a></div><div><b>CC:</b> <a href="mailto:scip@zib.de">scip</a></div><div><b>Subject:</b> Re: [Scip] why the optimal solution has varaible with negative reduced cost</div></div></div><div><div>Dear Xiangyong,</div>
<div> </div>
<div>so this is not a numerical issue. Everything is fine here: your </div>
<div>variable is at its upper bound and hence may have negative reduced cost </div>
<div>in an optimal solution.</div>
<div> </div>
<div>Precisely speaking, an LP solution for a minimization problem is dual </div>
<div>feasible if</div>
<div>- variables not at their upper bound have nonnegative reduced cost</div>
<div>- variables not at their lower bound have nonpositive reduced cost</div>
<div>- same for slacks of inequality constraints and their dual multipliers</div>
<div> </div>
<div>You may want to read about lazy bounds, see the FAQ in the online </div>
<div>documentation:</div>
<div> </div>
<div>http://scip.zib.de/doc/html/FAQ.php</div>
<div> </div>
<div>Kind regards,</div>
<div>Ambros</div>
<div> </div>
<div> </div>
<div>Am 12.08.2014 09:51, schrieb lixiangyong@163.com:</div>
<div>> Dear Ambros:</div>
<div>></div>
<div>> Attached please find the attach node lp.</div>
<div>> The optimal solution has non basic variable z_7_6 =1 with reduced cost</div>
<div>> -0.008333. It is strange!!</div>
<div>> Actually for my model, there several variables with negative reduced cost.</div>
<div>></div>
<div>> Thanks,</div>
<div>></div>
<div>></div>
<div>> Xiangyong</div>
<div>></div>
<div>></div>
<div>> *From:* Ambros Gleixner <mailto:gleixner@zib.de></div>
<div>> *Date:* 2014-08-12 15:45</div>
<div>> *To:* scip <mailto:scip@zib.de></div>
<div>> *Subject:* Re: [Scip] why the optimal solution has varaible with</div>
<div>> negative reduced cost</div>
<div>> Dear Xiangyong,</div>
<div>> Are the reduced costs very negative or only slightly? They are allowed</div>
<div>> to be negative up to minus the value given by the parameter</div>
<div>> numerics/dualfeastol, i.e., -1e-7 by default (in SCIP 3.1).</div>
<div>> This is because standard floating-point LP solvers can in general not</div>
<div>> guarantee exact (primal and dual) feasibility.</div>
<div>> Kind regards,</div>
<div>> Ambros</div>
<div>> Am 12.08.2014 02:14, schrieb lixiangyong@163.com:</div>
<div>> > Dear all,</div>
<div>> ></div>
<div>> ></div>
<div>> > I am using SCIP with cplex to implement the branch and price for</div>
<div>> > minimization problem.</div>
<div>> ></div>
<div>> > I found after several columns were added at each round, the</div>
<div>> resulting</div>
<div>> > model has an optimal solution of which some variables have negative</div>
<div>> > reduced cost (min problem).</div>
<div>> ></div>
<div>> > Thanks,</div>
<div>> ></div>
<div>> > Xiangyong</div>
<div>> ></div>
<div>> ></div>
<div>> > _______________________________________________</div>
<div>> > Scip mailing list</div>
<div>> > Scip@zib.de</div>
<div>> > http://listserv.zib.de/mailman/listinfo/scip</div>
<div>> ></div>
<div>> --</div>
<div>> ____________________________________________________________</div>
<div>> Ambros M. Gleixner</div>
<div>> Zuse Institute Berlin - Matheon - Berlin Mathematical School</div>
<div>> http://www.zib.de/gleixner</div>
<div>> _______________________________________________</div>
<div>> Scip mailing list</div>
<div>> Scip@zib.de</div>
<div>> http://listserv.zib.de/mailman/listinfo/scip</div>
<div>></div>
<div> </div>
<div>-- </div>
<div>____________________________________________________________</div>
<div>Ambros M. Gleixner</div>
<div>Zuse Institute Berlin - Matheon - Berlin Mathematical School</div>
<div>http://www.zib.de/gleixner</div>
</div></blockquote>
</body></html>