Source code for

# returns a relaxed model from a given model

from import DocplexLinearRelaxationError

from collections import defaultdict

[docs]class LinearRelaxer(object): """ This class returns a linear relaxation for a MIP model. """ def __init__(self): self._unrelaxables = defaultdict(list) def iter_unrelaxables(self): return self._unrelaxables.items() def main_cause(self): unrelaxables = self._unrelaxables max_urx = -1 justifier = None main_cause = None for cause, urxs in unrelaxables.items(): if len(urxs) > max_urx: max_urx = len(urxs) main_cause = cause justifier = urxs[0] return main_cause, justifier @staticmethod def make_relaxed_model(mdl, return_partial=False, **kwargs): lrx = LinearRelaxer() return lrx.linear_relaxation(mdl, return_partial=return_partial, **kwargs)
[docs] def linear_relaxation(self, mdl, return_partial=False, **kwargs): """ Returns a continuous relaxation of the model. Variable types are set to continuous (note that semi-xxx variables have their LB set to zero) Some constructs are not relaxable, for example, piecewise-linear expressions, SOS sets, logical constraints... When a model contains at least one of these non-relaxable constructs, a message is printed and this method returns None. By default, model parameters are not copied. If you want to copy them, pass the keyword argument `copy_parameters=True` :param mdl: the initial model :param return_partial: if True, returns the partially relaxed model anyway, default is False, if an unrelaxable item is encountered, None is returned :return: a new model with continuous relaxation, if possible, else None. """ relax_name = kwargs.get('relaxed_name', None) verbose = kwargs.get('verbose', True) copy_parameters = kwargs.get('copy_parameters', False) # relax sos by default relax_sos = kwargs.get('relax_sos', True) model_name = def info(msg): if verbose: print("* relaxation of model {0}: {1}".format(model_name, msg)) mdl_class = mdl.__class__ unrelaxables = defaultdict(list) def process_unrelaxable(urx_, reason): unrelaxables[reason or 'unknown'].append(urx_) relax_model_name = relax_name or "lp_%s" % relaxed_model = mdl_class(name=relax_model_name) # transfer kwargs relaxed_model._parse_kwargs(mdl._get_kwargs()) # transfer variable containers ctn_map = {} for ctn in mdl.iter_var_containers(): copied_ctn = ctn.copy_relaxed(relaxed_model) ctn_map[ctn] = copied_ctn # transfer variables var_mapping = {} continuous = relaxed_model.continuous_vartype for v in mdl.iter_variables(): cpx_code = v.cplex_typecode if not v.is_generated() or cpx_code == 'C': # if v has type semixxx, set lB to 0 if cpx_code in {'N', 'S'}: rx_lb = 0 else: rx_lb = copied_var = relaxed_model._var(continuous, rx_lb, v.ub, var_ctn = v.container if var_ctn: copied_ctn = ctn_map.get(var_ctn) assert copied_ctn is not None copied_var.container = copied_ctn var_mapping[v] = copied_var # transfer all non-logical cts for ct in mdl.iter_constraints(): if not ct.is_generated(): if ct.is_logical(): process_unrelaxable(ct, 'logical') try: copied_ct = ct.relaxed_copy(relaxed_model, var_mapping) relaxed_model.add(copied_ct) except DocplexLinearRelaxationError as xe: process_unrelaxable(xe.object, xe.cause) except KeyError as ke: info('failed to relax constraint: {0}'.format(ct)) process_unrelaxable(ct, 'key') # clone objective relaxed_model.objective_sense = mdl.objective_sense try: relaxed_model.objective_expr = mdl.objective_expr.relaxed_copy(relaxed_model, var_mapping) except DocplexLinearRelaxationError as xe: process_unrelaxable(urx_=xe.object, reason=xe.cause) except KeyError: process_unrelaxable(urx_=mdl.objective_expr, reason='objective') # clone kpis for kpi in mdl.iter_kpis(): relaxed_model.add_kpi(kpi.copy(relaxed_model, var_mapping)) if mdl.context: relaxed_model.context = mdl.context.copy() if copy_parameters: # copy parameters is not the default behavior # by default, the relaxed copy has a clean, default, parameter set. # if verbose: # info("copying initial model parameters to relaxed model") nb_copied = 0 for p1, p2 in zip(mdl.parameters.generate_params(), relaxed_model.parameters.generate_params()): if p1.is_nondefault(): p2.set(p1.get()) nb_copied += 1 if verbose: info("copied {0} initial model parameters to relaxed model".format(nb_copied)) # if relax_sos: for sos in mdl.iter_sos(): # list of mapped variables for original sos sos_vars = [var_mapping[dv1] for dv1 in sos.iter_variables()] sos_type = sos.sos_type sos_ctname = f"relaxed_sos{sos_type.value}#{sos.index+1}" relaxed_model.add(relaxed_model.sum_vars(sos_vars) <= sos_type.value, sos_ctname) else: for sos in mdl.iter_sos(): unrelaxables['sos'].append(sos) self._unrelaxables = unrelaxables if unrelaxables: nb_unrelaxables = len(unrelaxables) main_cause, justifier = self.main_cause() if verbose and not return_partial: print("* model {0}: found {1} un-relaxable elements, main cause is {2} (e.g. {3})" .format(, nb_unrelaxables, main_cause, justifier)) if verbose: for cause, urxs in unrelaxables.items(): print('* reason: {0}: {1} unrelaxables'.format(cause, len(urxs))) for u, urx in enumerate(urxs): if hasattr(urx, "is_generated") and urx.is_generated(): s_gen = " [generated]" else: s_gen = "" print('-- {0}: cannot be relaxed: {1!s}{2}'.format(u + 1, urx, s_gen)) if return_partial: if verbose: print(f"-- returning partially relaxed model") return relaxed_model else: return None else: # force cplex if any... cpx = relaxed_model.get_cplex(do_raise=False) if cpx: # force type to LP cpx.set_problem_type(0) # 0 is code for LP. # sanity check... assert not relaxed_model._contains_discrete_artefacts() assert not relaxed_model._solved_as_mip() # --- return relaxed_model