s_j = max {a_j, s_i + t_ij}를 선형 제약으로 공식화 할 수 있습니까?

Question

내 질문은 선형 제약 조건으로 다음을 표현하는 트릭이 있는지 여부입니다.

S_j = 최대 {a_j, S_i +의 t_ij}

곳 a_j 및 상수

Answer 1

예, 새로운 이진 변수 y_j을 도입하여이 작업을 수행 할 수 있습니다 사전에

많은 감사 (t_ij 있습니다 0 또는 1) 및 몇 가지 선형 제약.

로 우리는 당신의 제약 조건을 다시 작성할 수 있습니다 :

Sj = a  if a > Si + T 
Sj = Si + T if a < Si + T 


Sj = a y_j + (Si + T) (1 - yj)  .....(1) 

이의 말을하자 그 y_j = 0이

M y_j + a - (Si + T) > 0 ....(2) 
where M is a big number, much bigger than a or Si or T. 

시 + T보다 작은 경우는

y_j = 1 큰 경우 y_j가 1이면 위의 제약 조건을 만족해야하며 Sj는 a와 같습니다. y_j가 0이면 는은 (1)과 (2)이 시행 한 것이다 max 제약 조건을 포함, 제약 조건을 만족하는 큰 수 있고, 당신의 배합에 Sj = Si + T

.