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

[Abbas Omidi]

Dear Dr. Galati,

Thank you so much for pointing this out.
I have often used SCIP-GCG or CPLEX and do not have any experience with
SAS.
Do you know if there are any implementations with CPLEX or Gurobi under a
hood?

Kind regards
Abbas

On Thu, Feb 8, 2024 at 3:51 PM Matthew Galati <matthew.galati at gmail.com>
wrote:

> The only commercial solver that has these methods is SAS. Look for the
> DECOMP option.
>
> Cheers,
> Matt
>
> Sent from my iPhone
>
> On Feb 8, 2024, at 4:26 AM, Katrin Halbig <katrin.halbig at fau.de> wrote:
>
>  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 listScip at zib.dehttps://listserv.zib.de/mailman/listinfo/scip
>
>
> --
> Katrin Halbig, FAU Erlangen-Nürnberg, Analytics & Mixed-Integer Optimization, Tel. +49 9131 85-67179
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> https://listserv.zib.de/mailman/listinfo/scip
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20240209/0e0df614/attachment.html>