[OR-Tools 스터디] Solving a MIP Problem

Maximize x + 10y subject to the following constraints:

1. x + 7y ≤ 17.5

2. 0 ≤ x ≤ 3.5

3. 0 ≤ y

4. x, y integers

 

constraint가 선형이기에 솔루션이 정수로 요구되는 linear optimization problem에 해당한다.

아래 그래프는 문제에 대한 적합한 영역에서의 정수 점을 보여준다.

이 문제는 Solving an LP Problem에서 묘사된 linear optimization problem과 매우 유사하다는 것을 알 수 있으며, 이 경우 우리는 정수 솔루션이 요구된다. 

 

Basic steps for solving a MIP problem

MIP 문제를 해결하기 위해서는 아래의 단계를 포함해야한다.

 

1. Import the linear solver wrapper

2. declare the MIP solver

3. define the variables

4. define the constraints

5. define the objective

6. call the MIP solver

7. display the solution

 

Solution using the MPSolver

OR-Tools MIP solver의 초기값은 SCIP(Solving Constraint Integer Programs)이다.

 

#import the linear solver wrapper
from ortools.linear_solver import pywraplp

def MIPProblem():
    #declare the MIP solver
    #문제에 대한 MIP solver를 선언하는 것.
    solver = pywraplp.Solver.CreateSolver('SCIP')
    if not solver:
        return

    #define the variables
    infinity = solver.infinity()
    #x and y are integer non-negative variables.
    x = solver.IntVar(0.0, infinity, 'x')
    y = solver.IntVar(0.0, infinity, 'y')

    print('Number of variables = ', solver.NumVariables())
    # non-negative 정수값을 가지는 x, y 변수를 생성시키기 위해 MakeIntVar 메소드를 사용함.

    #define the constraints
    #x + 7 * y <= 17.5
    solver.Add(x+7*y <= 17.5)
    #x <= 3.5
    solver.Add(x<=3.5)

    print('Number of constraints =', solver.NumConstraints())

    #define the objective
    #문제에 대한 objective function을 정의한다
    #Maximize x+10*y
    solver.Maximize(x+10*y)

    #call the solver
    status = solver.Solve()

    #display the solution
    if status == pywraplp.Solver.OPTIMAL:
        print('Solution:')
        print('Objective value=', solver.Objective().Value())
        print('x = ', x.solution_value())
        print('y =', y.solution_value())
    else:
        print('The problem does not have an optimal solution.')

MIPProblem()

PyCharm 실행결과 :

결과적으로 x = 3, y = 2 지점에서 objective function의 optimal 값은 23이다. 

 

Comparing Linear and Integer Optimization

정수 문제의 솔루션은 linear 솔루션에 가장 가까운 실현 가능한 영역의 정수 점 즉, x = 0, y = 2일 것이라고 추측할 수 있다.
하지만 사실이 아니다.

 

#import the linear solver wrapper
from ortools.linear_solver import pywraplp

def MIPProblem2():
    #declare the MIP solver
    #문제에 대한 MIP solver를 선언하는 것.
    solver = pywraplp.Solver.CreateSolver('GLOP')
    if not solver:
        return

    #define the variables
    infinity = solver.infinity()
    #x and y are integer non-negative variables.
    x = solver.IntVar(0.0, infinity, 'x')
    y = solver.IntVar(0.0, infinity, 'y')

    print('Number of variables = ', solver.NumVariables())
    # non-negative 정수값을 가지는 x, y 변수를 생성시키기 위해 MakeIntVar 메소드를 사용함.

    #define the constraints
    #x + 7 * y <= 17.5
    solver.Add(x+7*y <= 17.5)
    #x <= 3.5
    solver.Add(x<=3.5)

    print('Number of constraints =', solver.NumConstraints())

    #define the objective
    #문제에 대한 objective function을 정의한다
    #Maximize x+10*y
    solver.Maximize(x+10*y)

    #call the solver
    status = solver.Solve()

    #display the solution
    if status == pywraplp.Solver.OPTIMAL:
        print('Solution:')
        print('Objective value=', solver.Objective().Value())
        print('x = ', x.solution_value())
        print('y =', y.solution_value())
    else:
        print('The problem does not have an optimal solution.')

MIPProblem2()

PyCharm 결과 :

실현 가능한 영역에서 대부분의 다른 정수 포인트들과 비교했을 때, 정수 솔루션은 linear 솔루션과 가깝지 않다는 것을 알 수 있다. 

일반적으로 linear optimization problem과 integer optimization problem들에 대한 솔루션들은 서로 멀리 떨어져있을 수 있다. 이때문에 두가지 타입의 문제는 해결 방법이 다르다. 

 

Reference :

https://developers.google.com/optimization/mip/mip_example

MIP 문제 해결  |  OR-Tools  |  Google Developers