Source code for

# --------------------------------------------------------------------------
# Source file provided under Apache License, Version 2.0, January 2004,
# (c) Copyright IBM Corp. 2015, 2016
# --------------------------------------------------------------------------
from import UpdateEvent
from import _SubscriptionMixin
from import Expr, ZeroExpr
from import LinearOperand
from import *
from import update_dict_from_item_value
from import StaticTypeChecker

def _compare_vars(v1, v2):
    v1i = v1._index
    v2i = v2._index
    return (v1i > v2i) - (v2i > v1i)

class VarPair(object):
    __slots__ = ("first", "second", "_cached_hash")

    def __init__(self, v1, v2=None):
        if v2 is None:
            self.first = v1
            self.second = v1
            if _compare_vars(v1, v2) <= 0:
                self.first = v1
                self.second = v2
                self.first = v2
                self.second = v1
        self._cached_hash = self._hash_pair()

    def is_square(self):
        return self.first is self.second

    def __eq__(self, other):
        # INTERNAL: necessary for use as dict keys
        # VarPair ensures variables are sorted by indices
        return isinstance(other, VarPair) and (self.first is other.first) and (self.second is other.second)

    def _hash_pair(self):
        f = hash(self.first)
        s = hash(self.second)
        # cantor encoding. must cast to int() for py3
        self_hash = int(((f + s) * (s + f + 1) / 2) + s)
        if self_hash == -1:
            # value -1 is reserved for errors
            self_hash = -2  # pragma: no cover
        return self_hash

    def __hash__(self):
        return self._cached_hash

    def __repr__(self):
        return "{0!s},second={1!s})".format(self.first, self.second)

    def __str__(self):
        return "VarPair({0!s}, {1!s})".format(self.first, self.second)

    def __getitem__(self, item):
        if 0 == item:
            return self.first
        elif 1 == item:
            return self.second
            raise StopIteration

    def index_tuple(self):
        return self.first._index, self.second._index

[docs]class QuadExpr(_SubscriptionMixin, Expr): """QuadExpr() This class models quadratic expressions. This class is not intended to be instantiated. Quadratic expressions are built either by using operators or by using :func:``. """ def _new_term_dict(self): return self._model._lfactory.term_dict_type() def copy(self, target_model, var_mapping): copied_quads = self._quadterms.__class__() for qv1, qv2, qk in self.iter_quad_triplets(): new_v1 = var_mapping[qv1] new_v2 = var_mapping[qv2] copied_quads[VarPair(new_v1, new_v2)] = qk copied_linear = self._linexpr.copy(target_model, var_mapping) return QuadExpr(model=target_model, quads=copied_quads, linexpr=copied_linear, safe=True) def relaxed_copy(self, relaxed_model, var_map): raise DocplexLinearRelaxationError(self, cause='quadratic')
[docs] def is_quad_expr(self): return True
[docs] def has_quadratic_term(self): """ Returns true if there is at least one quadratic term in the expression. """ return any(qk for _, qk in self.iter_quads())
def square(self): if self.has_quadratic_term(): self.fatal("Cannot take the square of a quadratic term: {0!s}".format(self)) else: return self._linexpr.square() def _raw_solution_value(self, s=None): # INTERNAL quad_value = 0 for qv0, qv1, qk in self.iter_quad_triplets(): quad_value += qk * (qv0._raw_solution_value(s) * qv1._raw_solution_value(s)) lin_value = self._linexpr._raw_solution_value(s) return quad_value + lin_value __slots__ = ('_quadterms', '_linexpr', '_transient', '_subscribers') def __init__(self, model, quads=None, linexpr=None, safe=False): Expr.__init__(self, model) self._transient = False self._subscribers = [] # used by subscription mixin if quads is None: self._quadterms = self._new_term_dict() elif isinstance(quads, dict): if safe: self._quadterms = quads else: # check safe_quads = self._new_term_dict() for qvp, qk in quads.items(): model._typecheck_num(qk) if not isinstance(qvp, VarPair): self.fatal("Expecting variable-pair, got: {0!r}", qvp) else: safe_quads[qvp] = qk self._quadterms = safe_quads elif isinstance(quads, tuple): try: v1, v2, qk = quads if not safe: model._typecheck_var(v1) model._typecheck_var(v2) model._typecheck_num(qk, 'QuadExpr') self._quadterms = model._lfactory._new_term_dict() self._quadterms[VarPair(v1, v2)] = qk except ValueError: # pragma: no cover self.fatal("QuadExpr accepts tuples of len: 3, got: {0!r}", quads) elif is_iterable(quads): qterms = model._lfactory.term_dict_type() for qv1, qv2, qk in quads: qterms[VarPair(qv1, qv2)] = qk self._quadterms = qterms else: self.fatal("unexpected argument for QuadExpr: {0!r}", quads) # pragma: no cover if quads is not None: self._model._quad_count += 1 if linexpr is None: self._linexpr = model._lfactory.linear_expr() else: self._linexpr = model._lfactory._to_linear_expr(linexpr) def clone_if_necessary(self): # INTERNAL if self._transient and not self._model._keep_all_exprs and not self.is_in_use(): return self else: return self.clone() def keep(self): self._transient = False
[docs] def clone(self): """ Makes a copy of the quadratic expression and returns it. Returns: A quadratic expression. """ cloned_linear = self._linexpr.clone() new_quad = QuadExpr(self.model, quads=self._quadterms.copy(), linexpr=cloned_linear, safe=True) return new_quad
def is_discrete(self): for qv0, qv1, qk in self.iter_quad_triplets(): if not qv0.is_discrete or not qv1.is_discrete() or not is_int(qk): return False return self._linexpr.is_discrete() def _generate_quad_triplets(self): # INTERNAL # a generator that returns triplets (i.e. tuples of len 3) # with the variable pair and the coefficient for qvp, qk in self.iter_quads(): yield qvp[0], qvp[1], qk def iter_quads(self): return iter(self._quadterms.items()) def iter_sorted_quads(self): if self._model.keep_ordering: return self.iter_quads() else: return self._iter_sorted_quads() def _iter_sorted_quads(self): quadterms = self._quadterms for vp in sorted(quadterms.keys(), key=lambda vvp: vvp.index_tuple()): yield vp, quadterms[vp] def iter_opposite_ordered_quads(self): # INTERNAL for qv, qk in self.iter_sorted_quads(): yield qv, -qk
[docs] def iter_quad_triplets(self): """ Iterates over quadratic terms. This iterator returns triplets of the form `v1,v2,k`, where `v1` and `v2` are decision variables and `k` is a number. Returns: An iterator object. """ return self._generate_quad_triplets()
[docs] def iter_terms(self): """ Iterates over the linear terms in the quadratic expression. Equivalent to self.linear_part.iter_terms() Returns: An iterator over the (variable, coefficient) pairs in the linear part of the expression. Example: Calling this method on (x^2 +2x+1) will return one pair (x, 2). See Also: :func:`` """ return self._linexpr.iter_terms()
@property def number_of_quadratic_terms(self): """ This property returns the number of quadratic terms. Counts both the square and product terms. Examples: .. code-block:: python q1 = x**2 q1.number_of_quadratic_terms >>> 1 q2 = (x+y+1)**2 q2.number_of_quadratic_terms >>> 3 """ return len(self._quadterms) @property def size(self): return self.number_of_quadratic_terms + self._linexpr.size
[docs] def is_separable(self): """ Checks if all quadratic terms are separable. Returns: True if all quadratic terms are separable. """ return all(qv.is_square() for qv, _ in self.iter_quads())
def compute_separable_convexity(self, sense=1): # INTERNAL # returns 1 if separable, convex # returns -1 if separable non convex # return s0 if non separable justifier = None for qv, qk in self.iter_quads(): if not qv.is_square(): return 0, None # non separable: fast exit elif qk * sense < 0: if justifier is None: justifier = (qk, qv[0]) # separable, non convex, kept else: return justifier or (1, None) # (1, None) is for separable, convex
[docs] def get_quadratic_coefficient(self, var1, var2=None): ''' Returns the coefficient of a quadratic term in the expression. Returns the coefficient of the quadratic term `var1*var2` in the expression, if any. If the product is not present in the expression, returns 0. Args: var1: The first variable of the product (an instance of class Var) var2: the second variable of the product. If passed None, returns the coefficient of the square of `var1` in the expression. Example: Assuming `x` and `y` are decision variables and `q` is the expression `2*x**2 + 3*x*y + 5*y**2`, then `q.get_quadratic_coefficient(x)` returns 2 `q.get_quadratic_coefficient(x, y)` returns 3 `q.get_quadratic_coefficient(y)` returns 5 Returns: The coefficient of one quadratic product term in the expression. ''' self.model._typecheck_var(var1) if var2 is None: var2 = var1 else: self.model._typecheck_var(var2) return self._get_quadratic_coefficient(var1, var2)
def _get_quadratic_coefficient(self, var1, var2): # INTERNAL, no checks vp = VarPair(var1, var2 or var1) return self._get_quadratic_coefficient_from_var_pair(vp) def _get_quadratic_coefficient_from_var_pair(self, vp): # INTERNAL return self._quadterms.get(vp, 0) def set_quadratic_coefficient(self, var1, var2, k): self.model._typecheck_var(var1) if var2 is None: var2 = var1 else: self.model._typecheck_var(var2) self._set_quadratic_coefficient(var1, var2, k) def _set_quadratic_coefficient_internal(self, var1, var2, k): vp = VarPair(var1, var2 or var1) self_quadterms = self._quadterms if not k: if vp in self_quadterms: del self_quadterms[vp] return True else: return False else: self_quadterms[vp] = k return True def _set_quadratic_coefficient(self, var1, var2, k): if self._set_quadratic_coefficient_internal(var1, var2, k): self.notify_modified(event=UpdateEvent.QuadExprGlobal) def _set_quadratic_coefficients(self, var_coef_seq): nb_changes = 0 for (var1, var2), k in var_coef_seq: if self._set_quadratic_coefficient_internal(var1, var2, k): nb_changes += 1 if nb_changes: self.notify_modified(event=UpdateEvent.QuadExprGlobal) # --- def equals(self, other): if not isinstance(other, QuadExpr): return False if self.number_of_quadratic_terms != other.number_of_quadratic_terms: return False for qvp, qk in self.iter_quads(): if other._get_quadratic_coefficient_from_var_pair(qvp) != qk: return False return self._linexpr.equals(other._linexpr) def is_constant(self): return not self.has_quadratic_term() and self._linexpr.is_constant() def get_constant(self): return self._linexpr.constant def set_constant(self, num): linexpr = self._linexpr event = None if num != linexpr.get_constant(): linexpr._constant = num event = UpdateEvent.ExprConstant self.notify_modified(event) @property def constant(self): """This property is used to get or set the constant part of a quadratic expression """ return self.get_constant() @constant.setter def constant(self, new_cst): self.set_constant(new_cst) @property def linear_part(self): """ This property returns the linear part of a quadratic expression. For example, the linear part of x^2 +2x+1 is (2x+1) :return: an instance of :class:`` """ return self.get_linear_part() def get_linear_part(self): linexpr = self._linexpr return linexpr if linexpr else 0 def iter_variables(self): for qvp, _ in self.iter_quads(): if qvp.is_square(): yield qvp[0] else: yield qvp[0] yield qvp[1] linexpr = self._linexpr for lv in linexpr.iter_variables(): yield lv def _quad_variable_set(self): # INTERNAL setof_qvars = set() for qvp, _ in self.iter_quads(): setof_qvars.add(qvp[0]) if not qvp.is_square(): setof_qvars.add(qvp[1]) return setof_qvars def iter_quad_variables(self): # iterates on quadratic variables, # returns each variable only once # order is irrelevant. setof_qvars = self._quad_variable_set() return iter(setof_qvars) iter_quad_vars = iter_quad_variables def __contains__(self, dvar): return self.contains_var(dvar)
[docs] def contains_var(self, dvar): # required by tests... for qv in self.iter_variables(): if qv is dvar: return True else: return False
def __iter__(self): # INTERNAL: this is necessary to prevent expr from being an iterable. # as it follows getitem protocol, it can mistakenly be interpreted as an iterable # but this would make sum loop forever. raise TypeError # pragma: no cover def contains_quad(self, qv): # INTERNAL return qv in self._quadterms def __repr__(self): return "" % self.repr_str() def to_stringio(self, oss, nb_digits, use_space, var_namer=lambda v: v.lp_name): q = 0 # noinspection PyPep8Naming SP = u' ' for qvp, qk in self.iter_sorted_quads(): if not qk: continue qv1 = qvp.first qv2 = qvp.second # --- # sign is printed if non-first OR negative # at the end of this block coeff is positive if q > 0 and use_space: oss.write(SP) if qk < 0 or q > 0: oss.write(u'-' if qk < 0 else u'+') if qk < 0: qk = -qk if use_space and q > 0: oss.write(SP) # write coeff if <> 1 varname1 = var_namer(qv1) if 1 != qk: self._num_to_stringio(oss, num=qk, ndigits=nb_digits) if use_space: oss.write(SP) oss.write(str(varname1)) if qv1 is qv2: oss.write(u"^2") else: if use_space: oss.write(SP) oss.write(u'*') oss.write(SP) else: oss.write(u'*') oss.write(str(var_namer(qv2))) q += 1 # problem for linexpr: force '+' ssi c>0 linexpr = self._linexpr lin_constant = linexpr.get_constant() if linexpr: first_lk = 0 for lv, lk in linexpr.iter_terms(): if lk: first_lk = lk break if q > 0 and first_lk > 0: if use_space: oss.write(u' ') oss.write(u"+") if first_lk: if use_space: oss.write(SP) self._linexpr.to_stringio(oss, nb_digits, use_space, var_namer) elif lin_constant: self._num_to_stringio(oss, lin_constant, nb_digits, print_sign=True, force_plus=q > 0, use_space=use_space) elif not q: oss.write(u'0') def plus(self, other): cloned = self.clone_if_necessary() cloned.add(other) return cloned def minus(self, other): cloned = self.clone_if_necessary() cloned.subtract(other) return cloned def rminus(self, other): # other - self cloned = self.clone() cloned.negate() cloned.add(other) return cloned def times(self, other): if is_number(other) and 0 == other: return self.zero_expr() elif isinstance(other, ZeroExpr): return other elif self.is_constant(): k = self.constant if not k: return self.zero_expr() elif 1 == k: return self._model._lfactory._to_linear_expr(other) else: return other * k else: cloned = self.clone() cloned.multiply(other) return cloned def __add__(self, other): return def __iadd__(self, other): self.add(other) return self def __radd__(self, other): return def __sub__(self, other): return self.minus(other) def __rsub__(self, other): # e - self return self.rsubtract(other) def __isub__(self, other): self.subtract(other) return self def __mul__(self, other): return self.times(other) def __rmul__(self, other): return self.times(other) def __imul__(self, other): # self is modified return self.multiply(other) def __div__(self, e): return self.quotient(e) def __idiv__(self, other): self.divide(other, check=True) return self def __truediv__(self, e): return self.quotient(e) # pragma: no cover def __itruediv__(self, other): # this is for Python 3.z return self.divide(other) # pragma: no cover def __neg__(self): cloned = self.clone() cloned.negate() return cloned def add(self, other): # increment the QuadExpr with some other argument if isinstance(other, QuadExpr): event = self._add_quad(other) else: self._linexpr.add(other) event = UpdateEvent.LinExprGlobal self.notify_modified(event=event) def rsubtract(self, other): # to compute (other - self) we copy self, negate the copy and add other # result is always cloned even if other is zero (optimization possible here) cloned = self.clone() cloned.negate() cloned.add(other) return cloned def subtract(self, other): if isinstance(other, QuadExpr): self._subtract_quad(other) event = UpdateEvent.QuadExprGlobal else: self._linexpr.subtract(other) event = UpdateEvent.LinExprGlobal self.notify_modified(event=event) return self def negate(self): # INTERNAL: negate sall coefficients, modify self qterms = self._quadterms for qvp, qk in qterms.items(): qterms[qvp] = -qk self._linexpr.negate() self.notify_modified(event=UpdateEvent.QuadExprGlobal) return self def multiply(self, other): event = UpdateEvent.QuadExprGlobal if is_number(other): self._scale(other) elif self.is_constant(): this_constant = self._linexpr.get_constant() if 0 == this_constant: # do nothing event = None else: self._assign_scaled(other, this_constant) elif self.has_quadratic_term(): if other.is_constant(): return self.multiply(other.get_constant()) else: StaticTypeChecker.mul_quad_lin_error(self.model, self, other) else: # self is actually a linear expression if is_quad_expr(other): if other.has_quadratic_term(): StaticTypeChecker.mul_quad_lin_error(self.model, self, other) else: return self.multiply(other._linexpr) else: other_linexpr = other.to_linear_expr() self_linexpr = self._linexpr for v1, k1 in self_linexpr.iter_terms(): for v2, k2 in other_linexpr.iter_terms(): self._add_one_quad_term(VarPair(v1, v2), k1 * k2) other_cst = other.get_constant() self_cst = self_linexpr.get_constant() if other_cst: self_linexpr._scale(other_cst) if self_cst: for ov, ok in other.iter_terms(): self_linexpr._add_term(ov, ok * self_cst) self.notify_modified(event) return self def quotient(self, e): self.model._typecheck_as_denominator(e, self) cloned = self.clone() cloned.divide(e, check=False) return cloned def divide(self, other, check=True): if check: self.model._typecheck_as_denominator(other, self) # only a nonzero number is allowed... inverse = 1.0 / other self._scale(inverse) self.notify_modified(event=UpdateEvent.QuadExprGlobal) return self def _scale(self, factor): # INTERNAL: scales a quad expr from a numeric constant. # no checks done! # this method modifies self. if 0 == factor: self.clear() elif 1 == factor: # nothing to do pass else: # scale quads self_quadterms = self._quadterms for qv, qk in self.iter_quads(): self_quadterms[qv] = factor * qk # scale linear part if self._linexpr is not None: self._linexpr._scale(factor) def _assign_scaled(self, other, factor): # INTERNAL if isinstance(other, LinearOperand): scaled = self._model._lfactory._to_linear_expr(other, force_clone=True) scaled *= factor self._linexpr = scaled elif isinstance(other, QuadExpr): for qv, qk in other.iter_quads(): self._add_one_quad_term(qv, qk * factor) self._assign_scaled(other.linear_part, factor) else: pass def _add_one_quad_term(self, qv, qk): qterms = self._quadterms if qk or qv in qterms: qterms[qv] = qterms.get(qv, 0) + qk def normalize(self): # pragma: no cover # INTERNAL quadterms = self._quadterms if quadterms: to_remove = [qvp for qvp, qk in self.iter_quads() if not qk] for rvp in to_remove: del quadterms[rvp] self._linexpr.normalize() def clear(self): self._quadterms.clear() self._linexpr._clear() # quad-specific def _add_quad(self, other_quad): # add quad part for oqv, oqk in other_quad.iter_quads(): self._add_one_quad_term(oqv, oqk) # add linear part if other_quad._linexpr.is_zero(): return UpdateEvent.QuadExprQuadCoef else: self._linexpr.add(other_quad._linexpr) return UpdateEvent.QuadExprGlobal def _subtract_quad(self, other_quad): # subtract quad quadterms = self._quadterms for oqv, oqk in other_quad.iter_quads(): update_dict_from_item_value(quadterms, oqv, -oqk) # subtract linear part self._linexpr.subtract(other_quad._linexpr) def to_linear_expr(self, msg=None): # pragma: no cover # used_msg = msg or "Quadratic expression [{0!s}] cannot be converted to a linear expression" # self.fatal(used_msg, self) raise DocplexQuadToLinearException(self) def is_normalized(self): # pragma: no cover # INTERNAL for _, qk in self.iter_quads(): if not qk: return False # pragma: no cover else: return True # --- relational operators def __eq__(self, other): return self._model._qfactory.new_eq_constraint(self, other) def __le__(self, other): return self._model._qfactory.new_le_constraint(self, other) def __ge__(self, other): return self._model._qfactory.new_ge_constraint(self, other) def __ne__(self, other): self.model.fatal("Operator `!=` is not supported for quadratic expressions, {0!s} was passed", self) def notify_expr_modified(self, expr, event): if expr is self._linexpr: # something to do.. self.notify_modified(event, )