[Scip] FARKAS COEFFICIENT

Fri Oct 31 15:17:33 CET 2014

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

>
> 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 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> <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 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>> <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
>>>>> _______________________________________________ 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

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