Solving an Optimization Problem

The previous section showed how to find all solutions to a CP problem. Next, we'll show how to find an optimal solution. As an example, we'll solve the following optimization problem.

Maximize 2x + 2y + 3z subject to the following constraints:
x + 72 y + 32 z25
3x - 5y + 7z45
5x + 2y - 6z37
x, y, z0
x, y, z integers

In order to increase computational speed, the CP-SAT solver works over the integers. This means all constraints and the objective must have integer coefficients. In the above example, the first constraint doesn't meet this condition. To solve the problem, you must first transform the constraint by multiplying it by a sufficiently large integer to convert all the coefficients to integers. This is shown in the Constraints section below.

Solution using the CP-SAT solver

The following sections present a Python program that solves the problem using the CP-SAT solver.

Declare the model

The following code declares the model for the problem.

from ortools.sat.python import cp_model


def main():
  model = cp_model.CpModel()

Create the variables

The following code creates the variables for the problem.

  var_upper_bound = max(50, 45, 37)
  x = model.NewIntVar(0, var_upper_bound, 'x')
  y = model.NewIntVar(0, var_upper_bound, 'y')
  z = model.NewIntVar(0, var_upper_bound, 'z')

Define the constraints

Since the first constraint,

x + 72 y + 32 z25

has non-integer coefficients, you must first multiply the entire constraint by a sufficiently large integer to convert the coefficients to integers. In this case, you can multiply by 2, which results in the new constraint

2x + 7y + 3z50

This doesn't change the problem, since the original constraint has exactly the same solutions as the transformed constraint.

The following code defines the three linear constraints for the problem:

  model.Add(2*x + 7*y + 3*z <= 50)
  model.Add(3*x - 5*y + 7*z <= 45)
  model.Add(5*x + 2*y - 6*z <= 37)

Define the objective function

The following code defines the objective function for the problem and declares it to be a maximization problem:

  model.Maximize(2*x + 2*y + 3*z)

Call the solver

The following code calls the solver and displays the results.

  solver = cp_model.CpSolver()
  status = solver.Solve(model)

  if status == cp_model.OPTIMAL:
    print('Maximum of objective function: %i' % solver.ObjectiveValue())
    print()
    print('x value: ', solver.Value(x))
    print('y value: ', solver.Value(y))
    print('z value: ', solver.Value(z))

The output is shown below:

Maximum of objective function: 35

x value:  7
y value:  3
z value:  5

The entire program

The entire program is shown below.

from __future__ import print_function
from ortools.sat.python import cp_model


def main():
  model = cp_model.CpModel()
  var_upper_bound = max(50, 45, 37)
  x = model.NewIntVar(0, var_upper_bound, 'x')
  y = model.NewIntVar(0, var_upper_bound, 'y')
  z = model.NewIntVar(0, var_upper_bound, 'z')

  model.Add(2*x + 7*y + 3*z <= 50)
  model.Add(3*x - 5*y + 7*z <= 45)
  model.Add(5*x + 2*y - 6*z <= 37)

  model.Maximize(2*x + 2*y + 3*z)

  solver = cp_model.CpSolver()
  status = solver.Solve(model)

  if status == cp_model.OPTIMAL:
    print('Maximum of objective function: %i' % solver.ObjectiveValue())
    print()
    print('x value: ', solver.Value(x))
    print('y value: ', solver.Value(y))
    print('z value: ', solver.Value(z))


if __name__ == '__main__':
  main()