ortools.linear_solver.python.linear_solver_natural_api

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