JuMP를 사용하여 MIP에 대한 차선책을 찾는 방법

Question

혼합 정수 프로그래밍 문제가 있습니다. JuMP를 사용하여 최적의 솔루션을 찾을 수 있습니다. 그러나 어떻게하면 차선책을 찾을 수 있습니까? 또는 세 번째로 가장 등

이 잠재적으로 또 다른 동등하게 최적의 솔루션이 될 수 있습니다, 하거나 더 나쁜의 솔루션이 될 수 있습니다, 하거나 :Infeasible 수 있습니다 - 아니 대부분의 솔루션이 없을 수 있습니다.

TSP와 비슷한 문제에 대해 알고 있는데, 최적의 경로에있는 링크를 점진적으로 제거하여 추가 솔루션을 찾을 수 있습니다 (일부 도시 간 거리를 무한대로 설정). schedualling type 문제에 대해서도, 최적 경로에 사용 된 타임 슬롯의 사용 가능성을 금지하는 것과 마찬가지로 점진적으로 설정할 수 있습니다.

하지만이 솔루션을 허용하지 않는 문제에 대한 구체적인 방법을 코딩하지 않고 일반적인 방법이 있습니까?

Answer 1

방금 ​​찾은 최적 해를 막기 위해자를 추가하여 다시 풀 수 있습니다. 모델에 이진 변수x(i)이 있다고 가정 해보십시오. 앞에서 찾은 최적 해결책이 a(i):=x*(i)이라고합시다. 그런 다음 선형 제약 조건 추가 :

sum(i, x(i) * a(i)) - sum(i, x(i) * (1-a(i))) <= sum(i, a(i)) - 1 

를 다시 해결한다. (이 것은 파생 된 here입니다.) x이 일반 정수 변수 인 경우 상황이 더욱 복잡해집니다.

Cplex 및 Gurobi와 같은 일부 해결사도 솔루션 풀이라고 불리는 것을 가지고 있습니다.