Dual values from MIP solution

[pmla]

Dear CPLEX developers,

I am using docplex to solve a MIP model from which I would like to get the dual values. It seems that the traditional way to do this in CPLEX is by solving a fixed MIP. Does docplex support solution of fixed MIPs?

Alternatively, is their a "correct" way to get dual values from a MIP using docplex? At the moment I am creating a LP model using the LinearRelaxer module and manually setting variable bounds, but this approach is quite slow.

[PhilippeCouronne]

Unfortunately, DOcplex does not yet support fixed MIPs. I understand you are using the linear relaxer, fixing variable to their solution values using bounds and starting a LP solve, am I correct? If so, can you elaborate on the slowness you are experiencing: what size is your problem, how often are you using this technique and what time does it take?

Note that the performance of changing variables bounds was improved in the latest (2.19) version of DOcplex, by introducing an API to change variable bounds in batches, see Model.change_var_lower_bounds (resp. upper).

[pmla]

Thanks for your reply @PhilippeCouronne.

I am solving a fairly large problem (~10 million non-zeros). Benchmarking my solution code gives this breakdown:

% Time
19.5      model.solve()
 0.0      for x in model.iter_integer_vars():
 0.0          x.lb = x.solution_value
 0.0          x.ub = x.solution_value
57.6      model_linear = LinearRelaxer().linear_relaxation(model)
22.7      model_linear.solve()

The total time is about 90 minutes.

As far as I understand, a fixed MIP would only require a few simplex iterations to achieve the same result as the LinearRelaxer approach. The other drawback of the LinearRelaxer is that the memory usage is doubled since it keeps two models in memory.

[PhilippeCouronne]

Thanks for your quick reply, @pmla , now I understand better . Linear relaxer is not an option for a large problem like yours. The solution is probably to use the native Cplex/Python API, but I need to do some tests before going further. I'll come back to you.

[PhilippeCouronne]

@pmla, I wrote a (simple) code that leverages the CPLEX Python API, by switching the problem type to fixedMILP and back. This is not quite satisfactory, as inside the context manager, DOcplex is not 'aware' that the model is actually a LP,, and would throw an exception if accessing the duals. This will be improved in future versions, but meanwhile this should work for you.

# The following sample shows how to set problem type to "fixedLP"
# the compute dual values, and retstore back original type.
# The code uses a Python contextmanager to restore type.

from contextlib import contextmanager

@contextmanager
def model_as_solvefixed(mdl):
    assert mdl.solution
    cpx = mdl.cplex
    # save initial problem type, to be restored.
    old_problem_type = cpx.get_problem_type()
    try:
        cpx.set_problem_type(3) # 3 is constant fixed_MILP
        yield mdl
    finally:
        cpx.set_problem_type(old_problem_type)

if __name__ == '__main__':
    from examples.delivery.modeling.nurses import build
    nm = build()
    ns = nm.solve(log_output=True)
    with model_as_solvefixed(nm) as nmf:
        print(f"-- problem type in block: {nm.problem_type}")
        nmf.solve(log_output=True)
        cpx = nmf.cplex
        # access dual values through CPLEX, as Docplex still thinks this is a MIP...
        all_duals = cpx.solution.get_dual_values()
        for lc, lcd in zip(nm.iter_linear_constraints(), all_duals):
            lcx = lc.index
            if lcd:
                print(f"-- constraint #{lcx}: {str(lc)[:32]}..,  dual={lcd}")
    print(f"-- problem type after: {nm.problem_type}")
    nm.solve(log_output=True, clean_before_solve=True)

[pmla]

@PhilippeCouronne I integrated this into my code and it works brilliantly. Thank you very much for your help!

[PhilippeCouronne]

Happy to help. Some improved version of this code will be integrated in a future version of Docplex