[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 your informative comments.

All the best
Abbas

On Fri, Feb 9, 2024 at 02:13 Matthew Galati <matthew.galati at gmail.com>
wrote:

> Cplex has classical benders.
>
> Gurobi has something where they take advantage of fully disconnected
> matrices; and I think they try to do some reductions when you have the case
> of "almost fully disconnected". Gu gave a talk on this a few years ago.
>
> But, in general, the answer is "no". No commercial vendors (except for
> SAS) do automated branch-cut-and-price like what GCG does. See:
> https://documentation.sas.com/doc/en/pgmsascdc/v_047/casmopt/casmopt_decomp_overview.htm
>
> Matt
>
> On Thu, Feb 8, 2024 at 5:40 PM Abbas Omidi <abb.omidi at gmail.com> wrote:
>
>> 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/2a2a81e6/attachment.html>