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 결과 :
Reference :
https://developers.google.com/optimization/mip/mip_example
MIP 문제 해결 | OR-Tools | Google Developers
이 페이지는 Cloud Translation API를 통해 번역되었습니다. Switch to English 의견 보내기 MIP 문제 해결 컬렉션을 사용해 정리하기 내 환경설정을 기준으로 콘텐츠를 저장하고 분류하세요. 다음 섹션에서
developers.google.com
'M.S. > OR-Tools' 카테고리의 다른 글
[OR-Tools 스터디] Constraint Optimization (0) | 2023.02.15 |
---|---|
[OR-Tools 스터디] Using Arrays to Define a Model (0) | 2023.02.14 |
[OR-Tools 스터디] Integer Optimization (Overview) (0) | 2023.02.13 |
[OR-Tools 스터디] The Stigler Diet Problem (0) | 2023.02.08 |
[OR-Tools 스터디] Solving an LP Problem (0) | 2023.02.07 |
댓글