Decision Optimization

Expand all | Collapse all

CPLEX relax SOS1 constraints

  • 1.  CPLEX relax SOS1 constraints

    Posted Fri July 23, 2021 12:18 AM

    I am trying to use the LinearRelaxer module to relax a MILP model with SOS1 constraints implemented in DoCplex MP. As per the docs here [1], the LinearRelaxer cannot relax the SOS1 constraints natively. While I can always rewrite the model such that the SOS1 constraints are expressed in their equivalent linear forms, it introduces a ton of overhead. Is there a native way to relax the SOS constraints?



    Louis Luo

  • 2.  RE: CPLEX relax SOS1 constraints

    Posted Fri July 23, 2021 04:43 AM

    Unfortunately, there is no native way to relax SOS variable sets. However, you are right in that we could improve the linear relaxer by
    replacing SOS by linear constraints in the relaxed model. 

    Note that for SOS2, the relaxation will be much weaker, as the constraint that only two adjacent variables can be equal to 1 cannot be enforced.

    This will be fixed in the next version of DOcplex. Meanwhile, I can propose the code below to  implement a relaxation of SOS: this code
    saves SOS info, clears them, calls relaxer and then adds constraints for each SOS.

    def relax_sos_sets(mdl):

    # 1. save sos info
    saved_sos_sets = []
    for sos in mdl.iter_sos():
    saved_sos_sets.append((list(sos.iter_variables()), sos.sos_type))

    # 2. clear sos and relax model without sos
    relaxed_mdl = Lrx.make_relaxed_model(mdl)

    assert relaxed_mdl is not None
    # 3. add relaxation linear constraint for sos
    for s, (sosvars, sostype) in enumerate(saved_sos_sets, start=1):
    relaxed_vars = [relaxed_mdl.get_var_by_index(dv.index) for dv in sosvars]
    sosval = sostype.value
    relaxed_mdl.add(relaxed_mdl.sum_vars(relaxed_vars) <= sosval, f"relaxed_sos{sosval}#{s}")
    # 4. restore sos in initial model
    mdl.add_sos(sosvars, sostype)

    return relaxed_mdl

    Sorry for the inconvenience, and don't hesitate to come back to us if this temp code is not sufficient.


    Philippe Couronne