Decision Optimization

Expand all | Collapse all

CPLEX CP: minimize_static_lex slowness for some "easy" problems

  • 1.  CPLEX CP: minimize_static_lex slowness for some "easy" problems

    Posted Thu February 18, 2021 12:59 PM
    Hi,

    I have a model which uses minimize_static_lex with ~200 constraints. The constraints are relatively simple, but it takes a lot of time to solve.
    Here is a simplified version of this model:

    from docplex.cp.model import CpoModel
    from docplex.cp.parameters import CpoParameters
    from docplex.cp.solver.solver import CpoSolver
    from docplex.cp.modeler import if_then, logical_or, minimize_static_lex
    from docplex.cp.expression import integer_var, binary_var

    N = 200

    model = CpoModel(name="MyModel")

    x = integer_var(name="x", min=0, max=1)
    ys = [binary_var(name=f"y{i}") for i in range(N)]

    always_true = logical_or(x == 0, x == 1)
    for i in range(N):
    model.add(if_then(always_true, ys[i] == 1))
    model.add(minimize_static_lex(ys))

    seed = int(1234)
    params = CpoParameters(
    RandomSeed=seed,
    # SearchType="MultiPoint",
    LogVerbosity="Verbose", # 'Quiet'
    WarningLevel=3, # 0
    )
    solver = CpoSolver(model, params=params)
    result = solver.solve()
    print(result)

    I tried it with several values for N:

    N = 50, time = 4s
    N = 100, time = 8s
    N = 200, time = 25s
    N = 400, time = 110s

    Any tips for using minimize_static_lex? Or maybe this can be improved in the solver?
    For now, we're just avoiding logical_or as much as possible.

    Thanks,
    Tomer

    ------------------------------
    Tomer Vromen
    ------------------------------


  • 2.  RE: CPLEX CP: minimize_static_lex slowness for some "easy" problems

    Posted Fri February 19, 2021 09:37 AM
    Hello,

    Which version of CP Optimizer do you use? the current version raises the following exception:
    docplex.cp.utils.CpoException: Only one objective function can be added to the model.

    This is due to the for loop in your model, it adds an objective at each iteration.
    You should write:
    for i in range(N):
        model.add(if_then(always_true, ys[i] == 1))
    model.add(minimize_static_lex(ys))
    ​

    instead of:

    for i in range(N):
        model.add(if_then(always_true, ys[i] == 1))
        model.add(minimize_static_lex(ys))
    

    and you will get:
    ! Time spent in solve : 0.03s (0.02s engine + 0.01s extraction)



    ------------------------------
    Olivier Lhomme
    ------------------------------



  • 3.  RE: CPLEX CP: minimize_static_lex slowness for some "easy" problems

    Posted Fri February 19, 2021 11:16 AM
    Hi Olivier,

    Sorry about that - it was a copy-past mistake. In my model it is indeed like you wrote.

    I'm using CPLEX 12.8.
    Is there performance differences for this model between my version and a newer one?

    ------------------------------
    Tomer Vromen
    ------------------------------



  • 4.  RE: CPLEX CP: minimize_static_lex slowness for some "easy" problems

    Posted Mon February 22, 2021 04:56 AM
    Hi Tomer,
    we checked with the 12.8 version, and can reproduce this slow and unexpected behavior. We need to investigate further to understand exactly what are the causes of this problem.
    You should definitely use a more recent version, 12.8 is quite old and many improvements have been done in the subsequent versions. As for this specific model, it is solved in 0.03s with the current version (20.1), or even with the old 12.9 version.
    Thanks for reporting this problem.

    ------------------------------
    Olivier Lhomme
    ------------------------------



  • 5.  RE: CPLEX CP: minimize_static_lex slowness for some "easy" problems

    Posted Mon February 22, 2021 06:11 AM
    Thanks for the quick reply! I will try to use a newer version.

    ------------------------------
    Tomer Vromen
    ------------------------------



  • 6.  RE: CPLEX CP: minimize_static_lex slowness for some "easy" problems

    Posted Thu February 25, 2021 08:32 AM
    Hi Olivier,

    I got access to CPLEX 12.9 and indeed it resolved the issue - thanks!

    However, I'm seeing that it's much slower on all my "regular" models. I don't know whether it's an issue with the version itself, or with the specific build/installation I'm using.
    Is this a known issue?

    > ./venv/bin/python solve.py
    cplex_path: /p/dt/sde/tools/em64t_SLES11/cplex/12.8/cpoptimizer/bin/x86-64_linux/
    model 2a, define & solve 500 times
    total time: 33.46s
    model 2b, define once & solve 500 times
    total time: 33.78s
    
    > ./venv/bin/python solve.py
    cplex_path: /p/dt/sde/tools/em64t_SLES11/cplex/12.9/cpoptimizer/bin/x86-64_linux/
    model 2a, define & solve 500 times
    total time: 47.44s
    model 2b, define once & solve 500 times
    total time: 70.59s
    ​


    def model2a(n = 1):
    
        for i in range(n):
            model = CpoModel(name="MyModel")
    
            w = binary_var(name="w")
            x = binary_var(name="x")
            y = binary_var(name="y")
            z = binary_var(name="z")
    
            model.add(logical_or(x == 1, y == 1))
            model.add(if_then(x == 1, logical_not(z == 1)))
            model.add(logical_and(logical_or(logical_or(w == 1, x == 1), y == 1), z == 1))
    
            params = CpoParameters(
                RandomSeed=int(time.time()),
                SearchType="MultiPoint",
                LogVerbosity="Quiet",
                WarningLevel=0,
            )
            solver = CpoSolver(model, params=params)
            result = solver.solve()
    
    
    def model2b(n = 1):
    
        model = CpoModel(name="MyModel")
    
        w = binary_var(name="w")
        x = binary_var(name="x")
        y = binary_var(name="y")
        z = binary_var(name="z")
    
        model.add(logical_or(x == 1, y == 1))
        model.add(if_then(x == 1, logical_not(z == 1)))
        model.add(logical_and(logical_or(logical_or(w == 1, x == 1), y == 1), z == 1))
    
        params = CpoParameters(
            RandomSeed=int(time.time()),
            SearchType="MultiPoint",
            LogVerbosity="Quiet",
            WarningLevel=0,
        )
        solver = CpoSolver(model, params=params)
        for i in range(n):
            result = solver.solve()
    
    
    n = 500
    
    print(f"model 2a, define & solve {n} times")
    start = time.time()
    model2a(n)
    print(f"total time: {time.time() - start:.2f}s")
    
    print(f"model 2b, define once & solve {n} times")
    start = time.time()
    model2b(n)
    print(f"total time: {time.time() - start:.2f}s")
    ​

    Meanwhile, I'll try to get access to a newer CPLEX version.

    ------------------------------
    Tomer Vromen
    ------------------------------



  • 7.  RE: CPLEX CP: minimize_static_lex slowness for some "easy" problems

    Posted Fri February 26, 2021 10:06 AM
    Edited by Olivier Oudot Fri February 26, 2021 10:09 AM
    Hi Tomer,

    The difference of performances you are talking about appear important just because you are running your problem 500 times.
    For model 2a, the delta per problem is less than 0,03 sec, and for model2b, it is less than 0,08 sec. This is small.

    Global performance increase between 12.9 and 12.8 measured on more than 5300 representative problems (some of them with a solve time of 1000 seconds) is 1,37 in average. However, it can happen that some problems become slower even if most of them become faster.

    Regards.

    ------------------------------
    Olivier Oudot
    ------------------------------



  • 8.  RE: CPLEX CP: minimize_static_lex slowness for some "easy" problems

    Posted Mon March 01, 2021 04:34 AM
    Hi Olivier,

    I understand that globally you have better performance with the version. But our use case is solving many small problems, so this is what I care about. I'm aware that this is not the typical use-case.

    In any case, I investigated this further. Turns out that the significant (~20%) performance degradation happens only when running on the old SLES11 OS (corporate environment...). With the newer SLES12 the degradation is much smaller (~2%) and not an issue. I hope we can move to that environment soon, and that will solve the whole thing.

    Thanks for your help!

    ------------------------------
    Tomer Vromen
    ------------------------------