[Scip] update constraint

Mon Jul 19 16:20:13 MEST 2010

On 19 July 2010 10:49, Tobias Achterberg <achterberg at zib.de> wrote:

> Please wait a second before you implement those hacks. There must be some
> conceptually clean solution, and this is what you should implement.
>
> Could you please explain a bit more in detail what you want to do? For
> example, what is the penalty function that should be used at the root node
> of the solving process, and how is this penalty function updated in local
> nodes?
>
My problem is basically the same as the following "*Stabilized column
generation for highly degenerate multiple-depot vehicle scheduling
problems*- Oukil, Amor, Desrosiers, Gueddari, 2006", except that in my
case the
maximum number of vehicle leaving each depot is 1. No better way to explain
the problem of generate an update the penalty function that read pages
824-828 of this article (I can send you the PDF, if you ask me).

>
> The only thing that you can do when going to a more local node is to
> *restrict* the feasibile region of your problem. Everything else will result
> either in an error or a wrong answer to your problem. In particular, you
> cannot modify the objective function.
>
I understood that I can't modify the objective function, so I tried to
create a dummy variable, linked with a constraint expressing the penalty
function. Adding such columns on the master problem will limit the region of
the dual, because they translate into more constraints in the dual. Is this
right?

> But please note that "the problem" is not equivalent to "the LP relaxation
> of the problem". You need to think about the full problem (as if all
> variables that you could ever add in by pricing be already part of the
> problem). Leaving some variables out of the LP relaxation and adding them
> only if their reduced costs become non-negative (or non-positive) is just a
> trick to restrict the size of the LP.
>
>
> I hope that you would spend a bit of your time to understand/read my
problem, otherwise I will try to explain it in my own words, but I think
that the article suggested is surely clearer than my attempt to summarize
it.

> Tobias
>
>
>
> Thanks a lot!

>
>
> Stefan Vigerske wrote:
>
>> Hi,
>>
>> Mattia Barbieri wrote:
>>
>>> On 16 July 2010 11:57, Stefan Vigerske<stefan at math.hu-berlin.de>  wrote:
>>>
>>>  Hi,
>>>>
>>>>  A dirty way could be to construct your penalty term as an SCIP_ROW, add
>>>>>> this one to the LP with the flag that it should not be removed, and
>>>>>> then
>>>>>> modify this row as you like. Changes in the row should be passed to
>>>>>> the
>>>>>> LP.
>>>>>>
>>>>> What does this mean? I understand this:
>>>>>  create an initial row:
>>>>>    *SCIPcreateEmptyRow* (...flag it removable..);
>>>>>
>>>> Better flag it *not* removable, so that it will stay always in the LP.
>>>>
>>>>   add variables and their coefficients (penalty terms):
>>>>>    *SCIPaddVarsToRow*(...);
>>>>> then tell the LP this changes:
>>>>>    *???*
>>>>>
>>>> If the row is in the LP and then changes, then SCIP passes these changes
>>>> into the LP, so there is no need to tell the LP.
>>>>
>>>> I do this:
>>>>
>>>
>>> //trickRow
>>>     SCIP_CALL(SCIPcreateEmptyRow(scip,&sp->*trickRow*, "trickRow", 0.0,
>>> 0.0, FALSE, TRUE, FALSE));
>>>
>>> *//sp is a struct to mantain some data like penalties, ecc.*
>>>
>>>     SCIP_VAR* transVar;
>>>     for (int p = 0; p<  Qdim; p++) {
>>>
>>> *//z_m[ ], y_m[ ], y_p[ ], z_p[ ] are the variables associated with the
>>> penalties*
>>> *//g_m[ ], d.., are the coefficients associated with the penalties*
>>>
>>>         SCIP_CALL(*SCIPtransformVar*(scip, sp->z_m[p],&transVar));
>>>
>>
>> It should be safer to use
>>    SCIPgetTransformedVar(scip, sp->z_m[p],&transVar)
>>
>>  *//I suppose SCIP want trasformed variables, because I obtain an error
>>> passing the original variables *
>>> *[src/scip/var.c:9329] ERROR: cannot add untransformed original variable
>>> <_var3_>  to LP row<trickRow>*
>>>         SCIP_CALL(SCIPaddVarToRow(scip, sp->trickRow, transVar,
>>> -sp->g_m[p]));
>>>         SCIP_CALL(SCIPtransformVar(scip, sp->y_m[p],&transVar));
>>>         SCIP_CALL(SCIPaddVarToRow(scip, sp->trickRow, transVar,
>>> -sp->d_m[p]));
>>>         SCIP_CALL(SCIPtransformVar(scip, sp->y_p[p],&transVar));
>>>         SCIP_CALL(SCIPaddVarToRow(scip, sp->trickRow, transVar,
>>> sp->d_p[p]));
>>>         SCIP_CALL(SCIPtransformVar(scip, sp->z_p[p],&transVar));
>>>         SCIP_CALL(SCIPaddVarToRow(scip, sp->trickRow, transVar,
>>> sp->g_p[p]));
>>>     }
>>>     SCIP_CALL(SCIPtransformVar(scip, sp->*trickVa*r,&transVar));
>>>
>>> *//trickVar is a variables add to the objective function of the LP, equal
>>> to
>>> the sum of the penalty variables*
>>>
>>>     SCIP_CALL(SCIPaddVarToRow(scip, sp->trickRow, transVar, -1.0));
>>>
>>> SCIP told me this:
>>>  *solution violates original bounds of variable<_var43_>  [-1e+20,1e+20]
>>> solution value<-2e+20>
>>> best solution is not feasible in original problem*
>>>
>>
>> This is hard to say without debugging. I don't know where _var43_
>> appears in your problem.
>>
>>  while if I add a linear constraint with the same variables/values the
>>> solution of the problem is correct (but as you told me in this way I
>>> can't
>>> change the coefficient's values during the LP iterations).
>>>
>>> Perhaps I am missing something...what? (Is that the right way to
>>> transform a
>>> variable?)
>>>
>>
>> Hmm, presolve may just throw out trickVar, since there is no constraint
>> associated to it. If trickVar is additionally unbounded, then SCIP may
>> say that the problem is "infeasible or unbounded".
>> You could add a dummy linear constraint trickVar>= some value and mark
>> it modifiable, so presolve cannot remove it.
>>
>> Stefan
>>
>>  after each pricer iteration (at each branch), modify the row whit new
>>>>
>>>>> coefficients (new penalty values):
>>>>>    *???*
>>>>>
>>>> OK, I see that there are no methods in scip.h or pub_lp.h to change row
>>>> coefficients. :-(
>>>> You can try with those in lp.h, e.g.
>>>> SCIP_RETCODE    SCIProwChgCoef (SCIP_ROW *row, BMS_BLKMEM *blkmem,
>>>> SCIP_SET *set, SCIP_LP *lp, SCIP_COL *col, SCIP_Real val).
>>>> blkmem you can get via SCIPblkmem(scip).
>>>> For set and lp, you would need to include struct_scip.h, so you can do
>>>> scip->set and scip->lp.
>>>>
>>>>  Can you give me more details? Forgive me but really I am stuck in this
>>>>> problem.
>>>>>
>>>> It may help to send mails to the scip mailing list... :-)
>>>>
>>>> Stefan
>>>>
>>>>  (I will be in Darmstadt for the COLGEN in August 23-27, but now I
>>>>> have time to work, so I am trying to solve my problem anyway)
>>>>>
>>>>>  (You could even ask your row for its position in the LP by using
>>>>>> SCIProwGetLPPos, get access to the LP via SCIPgetLPI, and then modify
>>>>>> the LP there, but that is something one should really not do...)
>>>>>>
>>>>>> Stefan
>>>>>>
>>>>>> --
>>>>>> Stefan Vigerske
>>>>>> Humboldt University Berlin, Numerical Mathematics
>>>>>> http://www.math.hu-berlin.de/~stefan<http://www.math.hu-berlin.de/%7Estefan>
>>>>>> <http://www.math.hu-berlin.de/%7Estefan>
>>>>>>
>>>>> <http://www.math.hu-berlin.de/%7Estefan>
>>>>
>>>>>
>>>>>
>>>>>
>>>> --
>>>> Stefan Vigerske
>>>> Humboldt University Berlin, Numerical Mathematics
>>>> http://www.math.hu-berlin.de/~stefan<http://www.math.hu-berlin.de/%7Estefan>
>>>> <http://www.math.hu-berlin.de/%7Estefan>
>>>>
>>>>
>>>
>>>
>>>
>>
>>

-- 
Mattia Barbieri
barbieri.mattia at gmail.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://listserv.zib.de/mailman/private/scip/attachments/20100719/48b46808/attachment.html