[Scip] Accessing the dual variables after SCIPsolve() returns

Fri Mar 25 10:17:00 MET 2011

Hi Daniel,

Stefan has already mentioned that pure LP problems should not be solved
with SCIP in case you are interested in dual information.  Using a
SCIP_LPI is a good way to go.  But let me give some more details on what
is happening:

You are calling SCIPgetDualfarkas() for constraints in the original
problem, which are not included in the LP. First, from outside you do
not have access to the corresponding transformed constraint which has
its row in the LP.  Second, the transformed constraint might be
different from your original one due to presolving (different nonzeros
or sides), and thus the farkas proof for the transformed LP is not
necessarily valid for your "original LP".

Another note: You had already turned off presolving, but even then you
cannot guarantee that SCIP detects infeasibility via solving the LP.  In
simple cases, SCIP might even detect infeasibility of the LP while
constructing it.

Now what are these methods good for then?  They are designed for use
within a pricer plugin, where you work directly on transformed
constraints.  Withtin the price-and-cut loop, if the LP relaxation does
not contain all columns and is infeasible, the SCIPgetDualfarkas...()
methods will return meaningful values.  We will try to clarify this also
in the documentation.

Best regards,
ambros

Am 25.03.2011 09:26, schrieb Stefan Heinz:
> Hi Daniel,
> 
> I used and use SCIP also for Benders decomposition. End of last year we had 
> already a question w.r.t. Benders. Here is what I wrote:
> 
> ---------
> 
> If you want to implement a classical bender decomposition, that means, solve 
> the master to optimality, check the slaves, and create a cut if necessary, 
> then none of the classical plugins are suitable for that. The reason is, that 
> if SCIP reaches the state of optimal solution found, it is not possible to 
> create a cut/constraint and restart SCIP out of a classical plugin.
> 
> To realize a classical bender decomposition with SCIP you have to play around 
> with the SCIP concept of original and transformed problem. SCIP always copies 
> the original problem in the beginning into so called transformed problem. 
> During the solving process only the transformed problem is changed. That 
> means, the original problem stays the same. If the problem is solved to 
> optimality you can grep the solution check the solution and if a subproblem is 
> violated you generate a constraint which you add to the original problem. 
> Therefore, you have the free the transformed problem first before you can add 
> the constraint to the original problem. After adding the constraint you repeat 
> to solving process.
> 
> There are two ways you can realize it with SCIP. You can use SCIP as callable 
> library or you implement a (none classical) plugin a SCIP dialog. 
> 
> http://scip.zib.de/doc/html/DIALOG.html
> 
> The advantage of SCIP dialog is that you can use the interactive Shell of 
> SCIP. This gives you the possibilities to easily play around with your 
> instances. That means, changing parameters, setting limits, and so on.
> 
> Currently, we have no example included in the SCIP release which features 
> Bender decomposition. Sorry for that. We are planning to change that with the 
> next release.
> 
> If you are more interested in so-called branch-and-check approach, then things 
> change a lot. For such an approach you should implement a constraint handler. 
> If you need more information for that, just let us know.
> 
> ------------
> 
> Besides that if your Slave/Client is an LP you should use an LP solver 
> directly. To be flexible with that you could use the SCIP LPI. This means you 
> can easily switch between CPLEX, Gurobi, SoPleX, Xpress, .... 
> In case of using the SCIP LPI you can use all function is "lpi.h".
> 
> Best Stefan
> 
> On Wednesday 23 March 2011 15:30:22 Ambros Gleixner wrote:
>> Hi Daniel,
>>
>> can you give more information on how SCIP detects the infeasibility of
>> the client?  I would want to make sure that it is actually due to an
>> infeasible LP and not presolving.  If the latter is the case, the LP
>> would not even be constructed.
>>
>> ambros
>>
>> Am 23.03.2011 15:20, schrieb Daniel Karch:
>>> Hello,
>>>
>>> I'm new to SCIP and I have the following problem:
>>>
>>> The problem I am working on decomposes into a master problem (IP) and a
>>> client problem (LP). I have implemented the client problem in a
>>> constraint handler. When the IP is solved to optimality, the constraint
>>> handler is called. If the LP detects infeasibility, I want to generate a
>>> cut that will be added to the master IP in turn.
>>> Now, I am interested in the LP dual variables that are zero when
>>> infeasibility is detected, as they correspond to constraints in the
>>> (primal) LP that are "not needed" to make it infeasible.
>>>
>>> So, this is essentially what I do to access the dual variables:
>>>
>>> ...
>>> SCIP_CALL( SCIPsolve( client_scip ) );
>>>
>>> ... <problem is detected to be infeasible> ...
>>>
>>> // conss[i] holds the i'th constraint of the client LP
>>> SCIP_Real z_i = SCIPgetDualfarkasLinear( client_scip, conss[i] );
>>>
>>> Now, the call to SCIPgetDualfarkasLinear(...) returns 0.0 for each
>>> constraint, rhich should not happen. I also tried
>>> SCIPgetDualsolLinear(...), to the same effect.
>>> I suspect that the SCIP instance gets cleaned up before I try to access
>>> the dual variables, so that they are not there anymore. Can someone
>>> confirm that this is true? The dual variables are not really all zero --
>>> I stepped into the function SCIPgetDualsolLinear(...) with gdb, and it
>>> always takes the else-branch here:
>>>
>>> if( consdata->row != NULL )
>>>
>>>   return SCIProwGetDualsol(consdata->row);
>>>
>>> else
>>>
>>>   return 0.0;
>>>
>>> Does someone have a solution for my problem?
>>>
>>> Thanks in advance
>>>
>>>   Daniel
>>>
>>> _______________________________________________
>>> Scip mailing list
>>> 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