<div dir="ltr"><div><div><div><div>Dear Gerald,<br><br></div>following your comments, we changed our code, so that only some initial variables are created & added at the beginning. In the pricing process, variables with reduced cost are created and added to the problem. In this way, all created and added variables appear in the solution SCIPprintSol(). The pricing process is now running fine. <br><br></div><div>Before the change of the pricing implementation, the objective <span>SCIPgetSolOrigObj(scip, scipSol) did worsen in some iterations. Now the total objective improves in every iteration. However, i</span>n some iterations the sum of the objective values of the solution variables is smaller than the total objective. This iterations have a relaxed solution, with the solution status "<span>LP was solved to optimality".<br><br></span></div>        SCIP_VAR** pricerSolVars = SCIPgetVars(scip);     <br>        SCIP_Real pricerSolSum   = 0;<br>        for(int vi=0; vi<SCIPgetNVars(scip); vi++){<br>            pricerSolSum += SCIPvarGetLPSol(pricerSolVars[vi]) * SCIPvarGetObj(pricerSolVars[vi]);<br>        }<br><br></div><div>My guess is, that <span>SCIPgetSolOrigObj() always refers to the best overall objective of the solution, wheras </span><br>SCIPvarGetLPSol() gets the solution value of the current relaxation. Is there any way to get the relaxed objective directly? As far as I could see, SCIPgetSolTransObj() always returns the same value as the original objective. <br></div><div><br></div><div>At the end, the solution is optimal. We're just using binary variables in settppc and knapsack constraints with a linear cost function. The log shows, that a scip-supplied branching rule is used. I have disabled the heuristic "shiftandpropagate", because it increases the solution time 10x. How much could be gained from implementing a problem specific branching rule? If have supplied some log information. Unfortunately, it wasn't possible to print the SCIPprintDisplayLine(), probably because of the Matlab-Mex message handler.  <br><br></div><div>All the best & thanks one more time,<br></div></div>Jan<br><br><div><div><div><div><div><div><div class="gmail_extra"><br><div class="gmail_quote">2015-02-06 11:59 GMT+01:00 Gerald Gamrath <span dir="ltr"><<a href="mailto:gamrath@zib.de" target="_blank">gamrath@zib.de</a>></span>:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Dear Jan,<br>
<br>
sorry for the delayed reply. See my comments below.<span><br>
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
My scheduling problem has one set partitioning constraint for every vehicle and binary variables for every possible start-timeslot. All variables are created at the beginning, but only two variables for every vehicle/setppc-constraint are added to the problem and their constraints right away. At the end, the solution must have one binary variable set to one for every vehicle/setppc-constraint.<br>
<br>
In the pricing process, the reduced cost of the other variables (start slots) are calculated and added to the problem with SCIPaddPricedVar() and added to the transformed constraints afterwards. In the iteration process, more and more variables are added to the problem. But sometimes the objective value is rising slightly, which is odd because added variables enlarge the solution space which should lead to a decreasing objective value.<br>
</blockquote></span>
What do you mean with objective value? The optimum of the LP? By which amount (absolute and relative) does the objective change? Really small changes could just be caused by numerics.<span><br>
<br>
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
Unfortunately, some variables don't appear in the solution SCIPprintSol() but in the solution SCIPprintTransSol(). Unsurprisingly, these are all priced variables. The objective value of both solution-files are the same, though. But if the objective value is calculated by all solution variables (SCIPvarGetLPSol(vars(f,d)) == 1)  and their objective function values (SCIPvarGetObj(vars(f,d)), the result is a little bit lower than the printed solution-objective-function-<u></u>values.<br>
</blockquote></span>
Yes, since the priced variables have no equivalent in the original space, they are left out when printing an original solution. The objective, however, is the one of the transformed solution, so solution and objective do not necessarily fit together (on the other hand, printing a wrong objective value would be bad as well). So you need to get the transformed solution when you do branch-and-price. In most of the cases when doing branch-and-price, you even write your own solution printing method, since you rather want to write down the "meaning" of the variables instead of the names.<br>
Your case is very special, because you create all variables in the beginning, but since they are not added to the original problem, they cannot be printed in the original solution.<span><br>
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
To summarize the matter, there is a serious problem in connection with the pricing problem and the transformed problem.<br>
<br>
- Could the error stem from the fact that the variables are added from pricerdata to the problem?<br>
</blockquote></span>
No, this should be ok.<span><br>
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
- Is it necessary to add the priced variables to the original problem, too?<br>
</blockquote></span>
No, this is not possible, since the original problem cannot be changed during the solving process.<span><br>
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
- Is there some presolving/branch&bound/<u></u>relaxation going on, which interferes with the pricing?<br>
</blockquote></span>
If you marked your constraints to be modifiable, no presolving should interfere. Branch-and-bound is of course happening when the root LP was finally solved, and you should implement your problem-specific branching rule when doing branch-and-price.<span><br>
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
- Could numerical inconsistencies lead to such behaviour?<br>
</blockquote></span>
Yes, at least to small changes in the objective.<br>
<br>
<br>
If you send me your log file including statistics, I can have a look to check for problems.<br>
<br>
Best,<br>
Gerald<br>
<br>
<br>
<br>
</blockquote></div><br></div></div></div></div></div></div></div></div>