최대화 할 때 목적 함수에서 max를 변환하는 방법은 무엇입니까?

Question

어떻게 프로그램

maximize max(2x, 3y) 
s.t 0 <= x, y <= 1 

/MILP 요추 천자는 그것을 해결 할 수 있도록 재 작성?

내 실제 목적 함수는

나는 LP에 새로 온 사람, 내가 '진 제약'을 사용하는 방법을 잘 이해하지 못하는 것입니다.

저는 PuLP과 GLPK으로 학습하고 있습니다.
제 제작 코드에서 CPLEX 또는 Gurobi을 사용합니다.
이 두 가지가 '최대화 최대화'를 지원합니까? 목적은 최소화했다 경우 다음과 같이

Answer 1

"최대치 최대화"는 본질적으로 비논임입니다. 여기서 MIP 트릭을 사용해야합니다. 그리고 그렇게하기 위해서 여러분은 객체의 상한과 하한을 얻을 수 있어야합니다. 모든 유한 경계가 수행되지만 선명 경계는 더 빨리 풀고 수치 적으로 더 가깝게 느슨해지는 긴장 완화를 제공합니다.

은 소폭 더 일반적인 당신이 준 것보다있는 다음과 같은 문제를 가지고 가정 :

maximize max(3x, 2y) 
s.t. 0 <= x <= A, 0 <= y <= B. 

3x이 하찮게 3A에 의해 0에 의해 위 아래 묶여 것을 알 수 있습니다. 유사하게, 2y은 0 이상, 2B에 의해 아래에 한정된다. 이제 두 개의 이진 변수, c_1 및 c_2을 소개하고 그 중 하나가 1이되도록 요청하십시오. c_1은 max에서 3x의 선택에 해당하고 c_2은 max에서 2y의 선택에 해당합니다. 그럼 당신은

maximize z_1 + z_2 
s.t. z_1 <= 3A c_1 
     z_1 <= 3x 
     z_2 <= 2B c_2 
     z_2 <= 2y 
     c_1 + c_2 = 1 
     0 <= x <= A, 0 <= y <= B 
     c_1, c_2 binary 

쓰기 첫 번째 제약은 최대가 2y에 의해 attaned 경우 제로 공헌을 갖도록 z_1을 "해제". 제 2 제약 식은 3x에 의해 최대치가 얻어진 경우에 z_1을 3x으로 제한한다.

Answer 2

, 당신은 보조 변수를 사용할 수 있습니다 :

minimize z 
s.t. z >= 2x, z >= 3y, 0 <= x, y <= 1 

그것을 아래

M가 충분히 큰 수이고, 작동해야하는 극대화 있다면;

u_{1,2}_{1,2}은 2x와 3y를 정렬하는 "순열"을 나타내는 보조 변수 집합입니다. 숫자의 무리의

maximize (z_1_2 + z_2_2) 
s.t. 
z_1 = 2x 
z_2 = 3y 

z_1 = z_1_1 + z_1_2 
z_2 = z_2_1 + z_2_2 

u_1_1 + u_1_2=1 
u_2_1 + u_2_2=1 
u_1_1 + u_2_1=1 
u_1_2 + u_2_2=1 

z_1_1 <= M*u_1_1 
z_1_2 <= M*u_1_2 
z_2_1 <= M*u_2_1 
z_2_2 <= M*u_2_2 

z_1_1 + z_2_1 <= z_2_1 + z_2_2 


0 <= x, y <= 1 
u_{1,2}_{1,2} in {0,1} //u_i_k are binary variables. 

최소 및 최대는 합계는 달리, 선형 양식을하지 않습니다, 나는 CPLEX 생각하지 않는다 또는 MILP는 일반적으로 이것에 대한 특별한 형태를 가지고있다. 이 특별한 예에서 더 적은 수의 이진 보조 변수가 충분할 수도 있지만 (예 : u_{1,2}_{1,2}) 일반적으로이 순열 변수는 일련의 숫자 순서를 제공하고 순위에 따라 임의의 값을 선택할 수 있도록합니다 귀하의 경우 가장 큰 항목).