ortools.linear_solver.python.linear_solver_natural_api

  1# Copyright 2010-2024 Google LLC
  2# Licensed under the Apache License, Version 2.0 (the "License");
  3# you may not use this file except in compliance with the License.
  4# You may obtain a copy of the License at
  5#
  6#     http://www.apache.org/licenses/LICENSE-2.0
  7#
  8# Unless required by applicable law or agreed to in writing, software
  9# distributed under the License is distributed on an "AS IS" BASIS,
 10# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 11# See the License for the specific language governing permissions and
 12# limitations under the License.
 13
 14"""Patch to the python wrapper of ../linear_solver.h providing an algebraic API.
 15
 16This is directly imported, and use exclusively in ./linear_solver.i. See that
 17file.
 18For examples leveraging the code defined here, see ./pywraplp_test.py and
 19../../../python/linear_programming.py.
 20"""
 21
 22import collections
 23import numbers
 24
 25# The classes below allow linear expressions to be expressed naturally with the
 26# usual arithmetic operators +-*/ and with constant numbers, which makes the
 27# python API very intuitive. See the top-level comment for examples.
 28
 29
 30inf = float("inf")
 31
 32
 33class _FakeMPVariableRepresentingTheConstantOffset:
 34    """A dummy class for a singleton instance used to represent the constant.
 35
 36    To represent linear expressions, we store a dictionary
 37    MPVariable->coefficient. To represent the constant offset of the expression,
 38    we use this class as a substitute: its coefficient will be the offset. To
 39    properly be evaluated, its solution_value() needs to be 1.
 40    """
 41
 42    def solution_value(self):  # pylint: disable=invalid-name
 43        return 1
 44
 45    def __repr__(self):
 46        return "OFFSET_KEY"
 47
 48
 49OFFSET_KEY = _FakeMPVariableRepresentingTheConstantOffset()
 50
 51
 52def CastToLinExp(v):
 53    if isinstance(v, numbers.Number):
 54        return Constant(v)
 55    else:
 56        return v
 57
 58
 59class LinearExpr:
 60    """Holds linear expressions.
 61
 62    A linear expression is essentially an offset (floating-point value), and a
 63    dictionary mapping MPVariable objects to their coefficient (which is also a
 64    floating-point value).
 65    """
 66
 67    OVERRIDDEN_OPERATOR_METHODS = [
 68        "__%s__" % opname
 69        for opname in [
 70            "add",
 71            "radd",
 72            "sub",
 73            "rsub",
 74            "mul",
 75            "rmul",
 76            "div",
 77            "truediv",
 78            "neg",
 79            "eq",
 80            "ge",
 81            "le",
 82            "gt",
 83            "lt",
 84            "ne",
 85        ]
 86    ]
 87
 88    def solution_value(self):  # pylint: disable=invalid-name
 89        """Value of this linear expr, using the solution_value of its vars."""
 90        coeffs = self.GetCoeffs()
 91        return sum(var.solution_value() * coeff for var, coeff in coeffs.items())
 92
 93    def AddSelfToCoeffMapOrStack(self, coeffs, multiplier, stack):
 94        """Private function used by GetCoeffs() to delegate processing.
 95
 96        Implementation must either update coeffs or push to the stack a
 97        sub-expression and the accumulated multiplier that applies to it.
 98
 99        Args:
100          coeffs: A dictionary of variables' coefficients. It is a defaultdict that
101              initializes the new values to 0 by default.
102          multiplier: The current accumulated multiplier to apply to this
103              expression.
104          stack: A list to append to if the current expression is composed of
105              sub-expressions. The elements of the stack are pair tuples
106              (multiplier, linear_expression).
107        """
108        raise NotImplementedError
109
110    def GetCoeffs(self):
111        coeffs = collections.defaultdict(float)
112        stack = [(1.0, self)]
113        while stack:
114            current_multiplier, current_expression = stack.pop()
115            current_expression.AddSelfToCoeffMapOrStack(
116                coeffs, current_multiplier, stack
117            )
118        return coeffs
119
120    def __add__(self, expr):
121        return Sum(self, expr)
122
123    def __radd__(self, cst):
124        return Sum(self, cst)
125
126    def __sub__(self, expr):
127        return Sum(self, -expr)
128
129    def __rsub__(self, cst):
130        return Sum(-self, cst)
131
132    def __mul__(self, cst):
133        return ProductCst(self, cst)
134
135    def __rmul__(self, cst):
136        return ProductCst(self, cst)
137
138    def __div__(self, cst):
139        return ProductCst(self, 1.0 / cst)
140
141    def __truediv__(self, cst):
142        return ProductCst(self, 1.0 / cst)
143
144    def __neg__(self):
145        return ProductCst(self, -1)
146
147    def __eq__(self, arg):
148        if isinstance(arg, numbers.Number):
149            return LinearConstraint(self, arg, arg)
150        else:
151            return LinearConstraint(self - arg, 0.0, 0.0)
152
153    def __ge__(self, arg):
154        if isinstance(arg, numbers.Number):
155            return LinearConstraint(self, arg, inf)
156        else:
157            return LinearConstraint(self - arg, 0.0, inf)
158
159    def __le__(self, arg):
160        if isinstance(arg, numbers.Number):
161            return LinearConstraint(self, -inf, arg)
162        else:
163            return LinearConstraint(self - arg, -inf, 0.0)
164
165    def __lt__(self, arg):
166        raise ValueError('Operators "<" and ">" not supported with the linear solver')
167
168    def __gt__(self, arg):
169        raise ValueError('Operators "<" and ">" not supported with the linear solver')
170
171    def __ne__(self, arg):
172        raise ValueError('Operator "!=" not supported with the linear solver')
173
174
175class VariableExpr(LinearExpr):
176    """Represents a LinearExpr containing only a single variable."""
177
178    def __init__(self, mpvar):
179        self.__var = mpvar
180
181    def __str__(self):
182        return str(self.__var)
183
184    def AddSelfToCoeffMapOrStack(self, coeffs, multiplier, stack):
185        coeffs[self.__var] += multiplier
186
187
188class ProductCst(LinearExpr):
189    """Represents the product of a LinearExpr by a constant."""
190
191    def __init__(self, expr, coef):
192        self.__expr = CastToLinExp(expr)
193        if isinstance(coef, numbers.Number):
194            self.__coef = coef
195        else:
196            raise TypeError
197
198    def __str__(self):
199        if self.__coef == -1:
200            return "-" + str(self.__expr)
201        else:
202            return "(" + str(self.__coef) + " * " + str(self.__expr) + ")"
203
204    def AddSelfToCoeffMapOrStack(self, coeffs, multiplier, stack):
205        current_multiplier = multiplier * self.__coef
206        if current_multiplier:
207            stack.append((current_multiplier, self.__expr))
208
209
210class Constant(LinearExpr):
211
212    def __init__(self, val):
213        self.__val = val
214
215    def __str__(self):
216        return str(self.__val)
217
218    def AddSelfToCoeffMapOrStack(self, coeffs, multiplier, stack):
219        coeffs[OFFSET_KEY] += self.__val * multiplier
220
221
222class SumArray(LinearExpr):
223    """Represents the sum of a list of LinearExpr."""
224
225    def __init__(self, array):
226        self.__array = [CastToLinExp(elem) for elem in array]
227
228    def __str__(self):
229        parts = []
230        for term in map(str, self.__array):
231            if not parts:
232                parts.append(term)
233                continue
234            if term[0] == "-":
235                parts.append(" - " + term[1:])
236            else:
237                parts.append(" + " + term)
238        return f'({"".join(parts)})'
239
240    def AddSelfToCoeffMapOrStack(self, coeffs, multiplier, stack):
241        # Append elements in reversed order so that the first popped from the stack
242        # in the next iteration of the evaluation loop will be the first item of the
243        # array. This keeps the end result of the floating point computation
244        # predictable from user perspective.
245        for arg in reversed(self.__array):
246            stack.append((multiplier, arg))
247
248
249def Sum(*args):
250    return SumArray(args)
251
252
253SumCst = Sum  # pylint: disable=invalid-name
254
255
256class LinearConstraint:
257    """Represents a linear constraint: LowerBound <= LinearExpr <= UpperBound."""
258
259    def __init__(self, expr, lb, ub):
260        self.__expr = expr
261        self.__lb = lb
262        self.__ub = ub
263
264    def __str__(self):
265        if self.__lb > -inf and self.__ub < inf:
266            if self.__lb == self.__ub:
267                return str(self.__expr) + " == " + str(self.__lb)
268            else:
269                return (
270                    str(self.__lb) + " <= " + str(self.__expr) + " <= " + str(self.__ub)
271                )
272        elif self.__lb > -inf:
273            return str(self.__expr) + " >= " + str(self.__lb)
274        elif self.__ub < inf:
275            return str(self.__expr) + " <= " + str(self.__ub)
276        else:
277            return "Trivial inequality (always true)"
278
279    def Extract(self, solver, name=""):
280        """Performs the actual creation of the constraint object."""
281        coeffs = self.__expr.GetCoeffs()
282        constant = coeffs.pop(OFFSET_KEY, 0.0)
283        lb = -solver.infinity()
284        ub = solver.infinity()
285        if self.__lb > -inf:
286            lb = self.__lb - constant
287        if self.__ub < inf:
288            ub = self.__ub - constant
289
290        constraint = solver.RowConstraint(lb, ub, name)
291        for (
292            v,
293            c,
294        ) in coeffs.items():
295            constraint.SetCoefficient(v, float(c))
296        return constraint