[SCIP] Dealing with a problem that contains a specific structure with a standard MILP solver

[Katrin Halbig]

Dear Abbas,

To use decompositions, it is best to first write a *.dec file and then 
read it into Scip. You can write the *.dec file manually or use gcg to 
automatically create a decomposition and write it out to a *.dec file.
This file is read in the same way as the problem itself. On the command 
line enter "read path/to/problem read path/to/decomposition.dec optimize".
In pyscipopt:
m = Model()
m.readProblem("path/to/problem")
m.readProblem("path/to/decomposition.dec")

There are several plugins that (can) use such a decomposition, for 
example, heur_gins, heur_dps, heur_padm, and the benders framework. 
Switch on the heuristics by setting the corresponding parameters, for 
example, m.setParam('heuristics/dps/freq', 0).
It's not always efficiently to use these methods, but just try it.

Independent from a decomposition is the cons_component presolver. This 
method detects on its own whether the problem is split into independent 
components and treats them separately. But since you mentioned that you 
have linking constraints and variables, your problem is probably connected.
I don't know what commercial solvers do, but I would strongly assume 
that they also use methods like cons_components.

Best,
Katrin

Am 05.02.24 um 12:48 schrieb Abbas Omidi:
> Dear Alexander,
>
> Thank you so much for your quick response.
> Please, let me explain more about what I meant.
>
> I am currently working on a scheduling problem and its structures, 
> indeed from the modeling point of view, to investigate how a standard 
> MIP solver like SCIP or Gurobi can solve this problem efficiently.
> For that, I am using GCG, actually PyGCGopt, to analyze these 
> problems. In my previous email, I asked about some parameters at GCG 
> that seed up the solving process, and the comment by 
> Prof. Lübbecke was really helpful.
>
> Now, at the moment I do not need to use/implement this method manually 
> and I think everything can be done automatically. Also, on the other 
> hand, I am not aware of that the SCIP has a tool that applies 
> cons_components 
> <https://www.scipopt.org/doc-8.0.2/html/cons__components_8c.php> as a 
> successful presolving technique. By that, my questions are:
>
> 1) Is it possible to employ the mentioned decomposition by using the 
> command line? (e.g. read problem -> set this method -> optimize)
> 2) Is there any Python implementation, PySCIPopt, that shows how we 
> can use this method? (unfortunately, I do not have more experience 
> with C/C++)
> 3) Based on the mentioned "successful presolving technique", can 
> we infer that commercial solvers like Gurobi and CPLEX have gained 
> from such techniques under a hood?
>
> Best regards
> Abbas
>
>
> On Mon, Feb 5, 2024 at 2:09 PM Hoen, Alexander <hoen at zib.de> wrote:
>
>     Hi Abbas,
>
>
>     SCIP allows the user to provide a problem decomposition. Section
>     4.2 in the SCIP 7 Release report describes how SCIP uses the
>     decomposition.
>
>     On https://www.scipopt.org/doc-8.0.2/html/DECOMP.php there is an
>     explanation of how to provide such a decomposition.
>
>     Best,
>
>     Alex
>
>     ------------------------------------------------------------------------
>     *From:* Scip <scip-bounces at zib.de> on behalf of Abbas Omidi
>     <abb.omidi at gmail.com>
>     *Sent:* Monday, February 5, 2024 10:49:50 AM
>     *To:* scip at zib.de
>     *Subject:* [SCIP] Dealing with a problem that contains a specific
>     structure with a standard MILP solver
>     Dear support team,
>
>     Suppose we have a specific formulation which contains a particular
>     structure. For example, the formulation contains a block diagonal
>     format with some linking constraints or variables.
>
>     As far as I know, this format would be suitable for the
>     decomposition scheme. Now, I am interested to know if is there any
>     benefit to using this special structure with a standard MILP
>     solver line SCIP or Gurobi.
>
>     All the best
>     Abbas
>
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip

-- 
Katrin Halbig, FAU Erlangen-Nürnberg, Analytics & Mixed-Integer Optimization, Tel. +49 9131 85-67179
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20240208/3df52389/attachment.html>