[OR-Tools 스터디] CP-SAT Solver

OR-Tools는 정수 프로그래밍 문제를 해결하기 위한 두가지 메인 툴을 제공한다.

• MPSolver (이전 섹션에서 기술된 것)
• CP-SAT solver(다음에서 기술할 것)

CP-SAT solver와 MPSolver wrapper를 둘다 사용한 정수 프로그래밍 문제를 푸는 예제는 추후 Solving an Assignment Problem 섹션에서 확인 가능하다. 

 

여기서는 CP-SAT solver를 어떻게 사용하는지에 대해 다룬다. 

 

Example: finding a feasible solution

간단한 예제 문제이다 : 

Three variables, x, y, and z, each of which can take on the values: 0, 1, or 2.

one constraint: x !=  y

 

from ortools.sat.python import cp_model

class VarArraySolutionPrinter(cp_model.CpSolverSolutionCallback):
    def __init__(self, variables):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self.__variables = variables
        self.__solution_count = 0
    def on_solution_callback(self):
        self.__solution_count += 1
        for v in self.__variables:
            print('%s = %i' % (v, self.Value(v)), end=' ')
        print()
    def solution_count(self):
        return self.__solution_count

def CPSAT():
    # Declare the model
    model = cp_model.CpModel()

    # Create the variables
    num_vals = 3
    x = model.NewIntVar(0, num_vals -1, 'x')
    y = model.NewIntVar(0, num_vals -1, 'y')
    z = model.NewIntVar(0, num_vals -1, 'z')
    # solver는 3개의 변수를 생성하는데 이들은 각각 0, 1 또는 2를 가질 수 있다

    # Create the constraint
    # constraint : x != y
    model.Add(x != y)

    all_solution = True
    solver = cp_model.CpSolver()
    if all_solution == False:
        # Call the solver
        status = solver.Solve(model)
        if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
            print('x = %i' % solver.Value(x))
            print('y = %i' % solver.Value(y))
            print('z = %i' % solver.Value(z))
        else:
            print('No solution found.')
    else:
        solution_printer = VarArraySolutionPrinter([x, y, z])
        solver.parameters.enumerate_all_solutions = True
        status = solver.Solve(model, solution_printer)
        print('Status = %s' % solver.StatusName(status))
        print('Number of solutions found: %i' % solution_printer.solution_count())

    # Display the first solution


CPSAT()

 

Reference :

https://developers.google.com/optimization/cp/cp_solver

CP-SAT 솔버  |  OR-Tools  |  Google Developers