[Scip] FARKAS COEFFICIENT

[Ambros Gleixner]

Dear Diego,

Am 30.10.2014 um 19:32 schrieb 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 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>
>> http://listserv.zib.de/mailman/listinfo/scip
>
>
> _______________________________________________
> Scip mailing list
> 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