[Scip] FARKAS COEFFICIENT

[Ambros Gleixner]

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 schrieb 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: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 the 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> 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 approach-, 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 avoid 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>> http://listserv.zib.de/mailman/listinfo/scip
>>> _______________________________________________ Scip mailing list
>>> Scip at zib.de <mailto:Scip at zib.de>
>>> http://listserv.zib.de/mailman/listinfo/scip

-- 
____________________________________________________________
Ambros M. Gleixner
Zuse Institute Berlin - Matheon - Berlin Mathematical School
http://www.zib.de/gleixner