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

Stefan Heinz heinz at zib.de
Fri Mar 25 09:26:23 MET 2011


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


More information about the Scip mailing list