Decision Optimization

 View Only
Expand all | Collapse all

[Cplex Python] cannot get optimal solution when set_rhs and solve in a loop

  • 1.  [Cplex Python] cannot get optimal solution when set_rhs and solve in a loop

    Posted Mon November 30, 2020 09:49 AM
    Hello there,

    I'm working on a project that involves the epsilon constraint algorithm, so I use Cplex as an ILP solver. It changes a constraint rhs and solves in a loop. But recently I found that, with the same objective and constraints, the solutions are different when given the same rhs but one is to solve with this rhs individually and another one is to solve it in the loop.

    More formally(not the real code): assume there is an objective, and constraint x ranged from 1 to 99, assume the magic rhs is 87.
    # situation 1
    cplex_solver.set_rhs(x, 87)
    cplex_solver.solver()
    s1 = splex_solver.solution

    # situation 2
    for rhs in range(1, 99):
        cplex_solver.set_rhs(x, rhs)
        cplex_solver.solver()
        if rhs == 87:
            s2 = splex_solver.solution

    and objectives in s1 and s2 are different. Actually, s1 would be better, but both statuses return as "optimal".

    Environment: Cplex 12.10, python 3.6.10. Problem: 2000 binary variables, 1500 constraints, 2 objectives(solving as one objective)

    Codes involve Cplex:
    # prepare cplex solver
solver = Cplex()
solver.set_results_stream(None)
solver.set_warning_stream(None)
solver.set_error_stream(None)
solver.parameters.threads.set(1)
solver.parameters.parallel.set(1)

# load variables, objectives and constraints
# ...ignore their types please, just for showing the logic
solver.variables.add(obj=None, lb=None, ub=None,
                     types=['B']*len(variables), names=variables)

for index, constraint in enumerate(constraints):
    solver.linear_constraints.add(lin_expr=constraint, senses=senses[index],
                                  rhs=[rhs[index]], names=['c'+str(index)]

solver.objective.set_linear(objective[0])
solver.objective.set_sense(solver.objective.sense.minimize)

# set another objective as a constraint
solver.linear_constraints.add(lin_expr=objective[1], senses=['L'],
                                  rhs=[ub[1]], names=['obj']

# solve
for rhs in range(ub[1], lb[1], -1):
    solver.linear_constraints.set_rhs('obj', rhs)
    solver.solve()
    status = solver.soltuion.get_status_string()
    if 'optimal' in status:
        print(rhs, solver.soltuion.get_objective_value())
​

    And the magic rhs 6224, when setting ub = lb+1 = 6224, it prints 6224 -14217.0 .
    ...for range [6225, 6224]:

    6225 -14218.000000000058
    6224 -14218.000000000058

    ... for range [6226, 6224]:

    6226 -14220.000000000007
    6225 -14219.000000000013
    6224 -14218.000000000058

    and a bigger range [6230, 6220]:

    6230 -14226.000000000004
    6229 -14223.999999998661
    6228 -14222.0
    6227 -14220.0
    6226 -14220.0
    6225 -14219.000000000013
    6224 -14218.000000000058
    6223 -14216.0
    6222 -14216.0
    6221 -14214.0
    6220 -14213.000000000011

    Actually, it affects other rhs as well, like 6225 as shown above. I also tried using solver.solution.get_values() to calculate the objective value myself and it came out the same results. That confuses me a lot, I'm wondering whether I used the lib in a wrong way. I also tried the timeout parameters but it seems not working.

    It's so kind of you if you have read it through. Thanks a lot if you can give any advice!

    Best Regards,
    Shi Dong.

    #DecisionOptimization


  • 2.  RE: [Cplex Python] cannot get optimal solution when set_rhs and solve in a loop

    IBM Champion
    Posted Mon November 30, 2020 01:50 PM
    The first thing to note is that solving in a loop may result in a different search tree, particularly if advanced starts (also known as "hot starts") are enabled, which they are by default. That does not mean the optimal solution is different, just that the search path to the optimum may be different.

    Now combine that with the relative MIP gap tolerance, which tells CPLEX it can stop and declare victory if the gap between the incumbent solution and the best bound becomes sufficiently small. The default setting for the relative gap tolerance is 1e-4. The relative difference between -14217.0 (rhs 6224 run alone) and -14218.000000000058 (same rhs in a loop) is about 7e-5, which is below the default tolerance setting. So CPLEX may have found a suboptimal solution that is "close enough" in tolerance terms. You could try reducing the relative MIP gap parameter to see if that results in the same solution being found both times.

    ------------------------------
    Paul Rubin
    Professor Emeritus
    Michigan State University
    ------------------------------

    Original Message