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

[Matthew Galati]

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/20240208/89236e2a/attachment.html>