이것은 혼합 정수 선형 프로그래밍의 관점에서 공식화 될 수 있습니까?

Question

특정 시점에 다양한 지점 사이를 이동해야하는 개체 그룹이있는 문제를 해결하려고합니다.

나는 모든 오브젝트와 도착/출발의 모든 : 선형 프로그래밍의 관점에서 등등

object1FirstDepartureTime > X 
object1FirstArrivalTime < Y 
object1FirstArrivalTime - object1FirstDepartureTime > Z 
object1SecondDepartureTime - object1FirstArrivalTime > A 

등과 즉를 제약의 대부분을 공식화 할 수 있었다. 목표 기능은 운송 중에 최소한 또는 가능한 시간을 소비하는 것입니다.

내가 겪고있는 문제는 하나의 추가 제약이 있습니다. 특정 물체는 다른 물체가 여행하는 동안 함께 있어야합니다. 예를 들어, object1은 object2, object3 또는 object4를 수반 할 수 있습니다. 이러한 객체 자체에는 특정 도착 또는 출발 제약 조건이 있습니다. 내 (아마 정수가 혼합 된) 선형 프로그램이 수반 객체의 선택을 처리하도록하고 싶습니다. 그러나 이것을 형식화하려고 시도하면서, 그것을 선형으로 유지하는 방법을 알 수는 없습니다. 나는

object2GoWIthObject1 + object3GoWithObject1 + object4GoWithObject1 < 2 
object2GoWIthObject1, object3GoWithObject1, object4GoWithObject1 are all less than 2 
object2GoWIthObject1, object3GoWithObject1, object4GoWithObject1 are all integers 

같은 혼합 정수 제약 생각하지만 목적이 함께 1 개체 경우는 Y를 목적 1 시간 X에 출발 시간에 도착할 것입니다 "와 같은 제약을 표현하는 방법을 알아낼 수 없습니다 . " 이것은 부울 변수 (객체 2가 객체 1에 수반되는 경우)를 이동 시간으로 곱하는 것처럼 비선형 적으로 보입니다.

당연히 모든 "if ... then ..."문에 대해 서로 다른 선형 문제를 만들 수 있지만 60ish를 따르는 경로와 10 개의 개체를 동반 한 경우이 문제로 인해 10^60 선형 프로그램이 해결됩니다 , 그것은 좋지 않다.

이 선형 프로그래밍 문제를 공식화하는 방법에 대해 직관이있는 사람이라면 "Y는 Y를 동반합니까?" 문제 자체에서 표현 될 수 있습니다, 나는 많은 의무가있을 것입니다!

Answer 1

한 가지 방법은 다음과 같은 큰-M 방법을 사용하는 것입니다 :

object1FirstDepartureTime - object2FirstDepartureTime > -M * object2GoWIthObject1 
object1FirstDepartureTime - object2FirstDepartureTime < M * object2GoWIthObject1 

M은 충분히 큰 상수이다. big-M 접근 방식의 문제점은 LP 완화가 불량하다는 것입니다.

Answer 2

예, 제약 조건을 처리하도록 공식을 수정할 수 있습니다. 이것을 달성하기 위해 "Big-M"과 새로운 0-1을 포함하는 많은 표준 트릭이 있습니다. (한강의 반응은 바로 이것을 의미한다.)

특정 비선형 제약을 수용하기 위해, 당신은 당신의 배합에 추가 선형 제약 조건을 추가 한 후 (당신의 "GoWith"변수처럼) 새로운 0-1 변수를 도입 할 .

은의이 명시된 요구 사항을 보자 : 오브젝트이 함께 1 개체 경우는 Y

Start1 >= X 
Arrive1 <= Y 

이미 객체 1이 제한됩니다 개체 1 시간 X에 출발 시간에 도착합니다.

이진 변수 Z12을 소개합니다. Object2가 Object1로 이동하는 경우 1, 그렇지 않은 경우 Z12 = 0입니다.

그래서,

는 는

If Z12 = 1, then Start2 > X 
If Z12 = 1 then Arrive2 < Y 

는

우리는이를 다시 작성할 수 있습니다와 같은 :

Start2 - X >= 0 if Z12 =1 
Start2 - X >= -M if Z12 =0, where M is a large number. 

한 선형 제약으로 그들을 결합 :

Start2 - X >= M(Z12-1) 

Z12은 한 때이 제약 조건, 구속력과 그렇지 않으면 쉽게 만족된다.

마찬가지로, 오브젝트 1의 도착에 맞게 Object2의 도착을 위해, 당신은 작성합니다

유사 등 당신이 할 수있는 이진 변수 Z13, Z14을 도입함으로써

Arrive2 < Y + M(1-Z12), a linear constraint. 

된다

Arrive2 < Y if Z12=1 
Arrive2 < M if Z12=0 

어떤 하나의 선형 공식으로 모든 제약 조건을 처리하십시오. http://agecon2.tamu.edu/people/faculty/mccarl-bruce/mccspr/new15.pdf

: IP 제제에 사용하는

더 많은 "트릭"에서 확인하실 수 있습니다