[Scip] FARKAS COEFFICIENT

Sat Nov 1 10:35:44 CET 2014

Hi Gerald, 

I understood active as current. Now I see the difference. In my problem
they are the same just because my removable flag is set to FALSE. 

Let me use following notation. Below there is constraint that I try to
control adding new variables y to avoid an unbounded Farkas Dual. 

u'A - v'B - w'D <= 0 (y)

Hence, in my pricing I get max_y{u'A - v'B - w'D} and it gives me a
variable y to add if it is possitive. Hence, the main problem is that
when I add a variable y that I guessed becaming infeasible Farkas Dual
but really not, the program go into a loop. So, as far as I know, I do
not get wrong results but in some instances the problem will never
finish. 

Variable y are continuous. But implicitly it might be fixed in some
node.

Is there any way to switch coefficient in the objective function from 0
to

u'A_j - v'B_j - w'D_j just for y_j with possitive Farkas coefficient? I
mean in the Farkas procedure.

Best.

Diego.

El 31/10/2014 18:56, Gerald Gamrath escribió: 

> Hi Diego,
> 
>> The removable flag is set to FALSE. Furthermore, I use the functions SCIPgetVars() and SCIPgetNVars(), so I'm considering the problem in the current node.
> This has nothing to do with the current node. All variables are global in SCIP, so you get the list of all variables. The variables with negative dualfarkas value are not fixed, are they?
> 
>> PRICER_DELAY is set to TRUE.
> That's good.
> 
>> Hence I do not delete variables. The only changes that SCIP is doing automatically is changing the bounds. At de begining, my variables are nonnegative with upper lazy bound = 1. 
>> 
>> I have to say that most of times I add more than one variable according with dual values in both PRICERFARKAS and PRICERREDCOST per pricing round.
> This should also not be a problem.
> 
> What is actually the problem that you are facing, except for having unexpected Farkas coefficients for your variables? Do you get wrong results?
> 
> Best,
> Gerald
> 
> Ambros, 
> 
> I use +SCIPgetDualfarkasLinear() because when I define the minimization problem I define the constraints with >= or =. Anyway, with the same sign that the PRICERREDCOST which it seems working.
> 
> Diego. 
> 
> El 31/10/2014 15:17, Ambros Gleixner escribió: 
> 
> Dear Diego,
> 
> Am 31.10.2014 um 15:06 schrieb dponce at us.es:
> Dear Ambros, I have calculated y^T A by means of SCIPgetDualFarkasLinear() values and by means of SCIPgetVarFarkasCoef(). The result is the same, but possitive. What did you mean with "something like" in the previous mail? And with the +/- that you wrote before? 
> 
> I meant either + or -. The positive can be correct depending on how you define the Farkas proof. In one of your earlier e-mails you said that your Farkas dual looks like
> 
> max u'1 - v'b + w'0
> 
> subject to
> 
> w'C <= 0 (x)
> 
> u'A - v'B - w'D <= 0 (y)
> 
> v >= 0
> 
> Is that satisfied if you use SCIPgetDualfarkasLinear() for u,v,w, or if you use negative SCIPgetDualfarkasLinear()?
> 
> If not, where is the violation? As Gerald just wrote, they might correspond to missing variables.
> 
> Ambros
> 
> El 31/10/2014 15:13, Gerald Gamrath escribió: 
> Hi Diego,
> 
> are all your variables in the LP? When you create them, do you set the removable flag to TRUE or FALSE? And is your pricer delayed?
> 
> Best,
> Gerald Thanks. Diego. El 31/10/2014 08:58, Ambros Gleixner escribió: Have you already computed the y^T A manually using SCIPgetDualfarkasLinear() and compared it to the values of SCIPgetVarFarkasCoef()? Ambros Am 31.10.2014 um 02:49 schriebdponce at us.es: <mailto:dponce at us.es:> Dear Ambros, with the PRICERREDCOST I have to take into acount the feastol, but now Farkas coefficient are possitive. For instance, 1.0 in a small instance and bigger in others. Best. Diego. El 30/10/2014 19:53, Ambros Gleixner escribió: Dear Diego, Am 30.10.2014 um 19:32 schriebdponce at us.es: <mailto:schriebdponce at us.es:> <mailto:dponce at us.es: <mailto:dponce at us.es:>> Hello SCIP, The previous problem I had has been solved. Finally, I found a mistake in the code. Now, when the instance is not too small, my procedure is not working in some PRICERFARKAS. I found the function SCIPgetVarFarkasCoef(). Is this the slack of the associated dual constraint? they should be something like +/- y^T A, where A is t!
 he
constraint matrix and y the Farkas ray. My variables are nonnegatives and usually its Farkas coefficient is nonpossitive. But sometimes I have found possitive Farkas coefficient. Is this possible? Are they only slightly positive? This could easily happen due to numerics. You should compare with SCIP's epsilon or feastol. Ambros Thanks. Diego. El 24/10/2014 18:57, dponce at us.es <mailto:dponce at us.es> <mailto:dponce at us.es <mailto:dponce at us.es>> escribió: Dear Gerald, answered to your question, all my constraints are modifiable. I have checked all my constraints are contained in the LP and the problem is infeasible. Let me explain in a different way from my previous e-mail what is happening. In my problem x variables are added from the very begining and y variables are the ones to add. My feasible region is Ay = 1 (u) -By >=-b (v) Cx -Dy = 0 (w) where A,B,C,D>=0 b>0 x,y>=0 in a minimization problem and I guess SCIP is considering Min 0'x+0'y problem since v Farkas multipliers are
possitive. So my Farkas dual is Max u' -v'b +w'0 w'C <= 0 (x) s.t. u'A-v'B -w'D <= 0 (y) v>=0 For the first time I do not have y variables, so the primal is infeasible and SCIP realizes and set my variable isfarkas to TRUE. However, to solve the problem Max u' -v'b +w'0 w'C <= 0 (x) v>=0 I expect for instance w=0,v=0 and u_1+u_2+...+u_n=e99. So I'd add any y_i variable with u_i*a_i>0, I'd see what is happening and so on until feasibility. But what really is happening is that the solution of the sual farkas is u_j=1 for some j and v_k=e99 for some k. Hence the objective function is 1-b_k*e99=-e99 which is not logical solution for a maximization problem. Are there any function to get the dual Farkas objective? Just to verify. Finally, when I set x variables to binary, if I start with a feasible solution, every time that I am in Farkas I do not add any new variable and the node is closed. By the moment the solutions that I got are correct-I have solved the problem by another ap!
 proach-,
but I can't assure. I think if I solve the mistake for getting a first feasible solution in the LP, it will be enough to assure well done my MILP procedure. Best. Diego. El 24/10/2014 12:58, Gerald Gamrath escribió: Dear Diego, I have implemented a branch-and-price-procedure with a pricer which seems working in the PRICERREDCOST. But in the instances that it need to use PRICERFARKAS I am obtaining some farkas multipliers with strange values, like -e99. Indeed this dual variable should be nonnegative. this sounds strange. Can you please check with SCIPgetLPSolstat() that the LP is really infeasible and with SCIProwIsInLP() that the row corresponding to the constraint for which you get the dual farkas multiplier is contained in the LP (you can get the row of a linear constraint with SCIPgetRowLinear()). Did you mark the constraint to be modifiable? Because of this problem, I would like to know if SCIP by itself is able to close an infeasible node since the variables fixed avo!
 id any
feasible solution *and how*. Yes, SCIP can detect the infeasibility of a node in the domain propagation step. For example, if you have a constraint x + y = 1 and x and y were both fixed to 0, SCIP will detect the infeasibility and cut off the node. However, this is only done if the constraint was not marked to be modifiable, since otherwise pricing might add more variables to the constraint and there might still be feasible solutions with x = y = 0. My Farkas pricing is similar to the Reduced cost pricing whith 0 in the coefficients of the objective function and SCIPgetDualfarkasLinear() instead of SCIPgetDualsolLinear(). This is how it should be. Best, Gerald _______________________________________________ Scip mailing list Scip at zib.de <mailto:Scip at zib.de> <mailto:Scip at zib.de <mailto:Scip at zib.de>> <mailto:Scip at zib.de <mailto:Scip at zib.de> <mailto:Scip at zib.de <mailto:Scip at zib.de>>> http://listserv.zib.de/mailman/listinfo/scip [1] ______________________________________________!
 _ Scip
mailing list Scip at zib.de <mailto:Scip at zib.de> <mailto:Scip at zib.de <mailto:Scip at zib.de>> http://listserv.zib.de/mailman/listinfo/scip [1]

_______________________________________________
Scip mailing list
Scip at zib.de
http://listserv.zib.de/mailman/listinfo/scip [1]

Links:
------
[1] http://listserv.zib.de/mailman/listinfo/scip
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20141101/a7fb00ea/attachment.html>