search

scipopt / scip

SCIP - Solving Constraint Integer Programs
Other
406 stars 67 forks source link

Getting Full Search Tree #6

Closed izuwaa closed 3 years ago

izuwaa commented 3 years ago

Hello Team,

I apologize if this is not the best place to post this request for help; having spent a few days trying to read documentation and figure out what to do. I need to get the entire search tree used during computation of a solution to an LP. This tree I assume would have unexplored nodes, pruned nodes etc. Is this possible on SCIP? Thanks for your help and guidance.

I compiled SCIP 7.0.3 on Mac and I am coding on C++.

leoneifler commented 3 years ago

Hello, you are saying you want the search tree during the solution of an LP, is that a typo? A pure LP (no integer variables) does not require a tree search. If you mean MIP, how exactly do you want to have the tree? There exists, e.g. a visualization feature that writes the tree info to a file.

izuwaa commented 3 years ago

Hello,

Thank you for the speedy response. I did mean MIP apologies for that.

Just to be clearer on what I need; I am trying to implement the one-tree algorithm (Generating Multiple Solutions for Mixed Integer Programming Problems Danna etal 2007) where I can query the search tree for solutions within x% of the optimal solution and carry out further actions on the returned nodes.

Could you recommend how I could achieve this on SCIP?

Thanks a lot for helping.

izuwaa commented 3 years ago

Any help with the above will be really appreciated.

Thanks, Izuwa.

leoneifler commented 3 years ago

So if I understand you correctly you want to be able to access information for each of the nodes after (or during?) the solving of a MIP? I think this you would probably have to implement for yourself within SCIP. You could, for example create an event handler (https://www.scipopt.org/doc/html/EVENTHDLR_MAIN.php) that activates whenever a node is solved and either saves the information that you want in some data structure (in case you want to do this stuff during the tree search), or that writes the information to some file for you to access later.

izuwaa commented 3 years ago

Yes I would like to access the information of each node after the solving of an MIP. Thank you very much for pointing in the right direction. I would explore the event hander as recommended.

I didn't want to recreate this if it was already in SCIP i.e. to query the search tree for solutions within x% of the optimal, and get those solutions and their associated values.

leoneifler commented 3 years ago

So some more info on this: If you only want to have as many solutions as possible, then you should definitly use an event that triggers on a found solution (SCIP_EVENTTYPE_SOLFOUND). Also: SCIP will of course not explore all feasible solutions (especially if you find an optimal solution early on, large parts of the tree might be pruned where suboptimal solutions could be found).

izuwaa commented 3 years ago

Ok. Thanks for this extra information. I would explore it.

On Sat, Sep 11, 2021, 11:57 AM Leon Eifler @.***> wrote:

So some more info on this: If you only want to have as many solutions as possible, then you should definitly use an event that triggers on a found solution (SCIP_EVENTTYPE_SOLFOUND). Also: SCIP will of course not explore all feasible solutions (especially if you find an optimal solution early on, large parts of the tree might be pruned where suboptimal solutions could be found).

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/scipopt/scip/issues/6#issuecomment-917429654, or unsubscribe https://github.com/notifications/unsubscribe-auth/AUZ6XO77CBGPWHITF4AUARDUBN35XANCNFSM5DWKB6AA . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub.