[Scip] FARKAS COEFFICIENT
Ambros Gleixner
gleixner at zib.de
Thu Nov 6 06:49:07 CET 2014
Dear Diego,
I do not understand your application enough to see why your Farkas
pricing does not terminate. But changing the objective coefficients is
not a theoretically sound solution, I think.
Ambros
Am 01.11.2014 um 10:35 schrieb dponce at us.es:
> 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 schriebdponce at us.es: <mailto: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:schriebdponce at us.es:>
>>> <mailto:dponce 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:schriebdponce at us.es:
>>> <mailto:schriebdponce at us.es:>>
>>> <mailto:dponce at us.es: <mailto:dponce 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>>
>>> <mailto: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>>>
>>> <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
>>> <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>> <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
>>> http://listserv.zib.de/mailman/listinfo/scip
--
____________________________________________________________
Ambros M. Gleixner
Zuse Institute Berlin - Matheon - Berlin Mathematical School
http://www.zib.de/gleixner
More information about the Scip
mailing list