이진 정수 프로그래밍에서의 경험적 발견 방법

Question

이 질문에 대한 답을 찾기 위해 노력했지만 포괄적 인 내용을 찾을 수 없습니다. 나는 이진 정수 프로그래밍 문제,보다 구체적으로 집합 패킹, 집합 파티셔닝 및 집합 커버 문제에 대한 초기 실행 가능한 솔루션을 생성하기위한 알고리즘이나 경험적 발견 방법을 찾고있다.

하나의 솔루션 표현으로 다음과 같은 진 정수 프로그래밍 문제

Minimize  ax_1 + bx_2 + cx_3 
Subject to x_1 + x_2 <= 2 
       3x_1 + 3x_2 >= 6 
       x_2 + 2x_3 = 2 

이있는 경우

[x_1, x_2, x_3] 

곳 x_i로부터 = 0 또는 1을 구성하려고 갈 것 어떻게 그런

1 이 문제에 대한 초기 가능한 해결책. 문제가 수천 개의 변수와 제약으로 구성되어있을 때 가능한 모든 솔루션을 검토하는 것은 명백하게 작동하지 않습니다.

여기서의 목표는 로컬 미니 마를 얻기 위해 로컬 검색을 수행 한 다음 메타 휴학을 적용 할 수있는 초기 실현 가능성을 구성하는 것입니다.

Answer 1

일부 이진 정수 프로그래밍 문제에 대한 실현 가능한 솔루션을 찾는 문제는 이미 NP 완료입니다. Karp의 21 가지 NP 완전 문제 중 하나입니다 ->wiki : 0-1 정수 프로그래밍!

일반 설정에서,별로 다음 전체 접근 이길 것이다 (완성 : 그들은 하나가 유한 한 시간에 존재하는 경우 실현 가능한 해결책을 찾거나 아무도 없다 새삼 느끼게 될 것이다) :

• 정수 프로그래밍 솔버 (심플 렉스 + 브랜치 및 바운드 + 커팅 평면)
  • 예 : Gurobi, CPLEX (상용) 또는 CBC/GLPK (오픈 소스)
• 제약 프로그래밍 솔버
  • 예컨대 예컨대 Gecode (오픈 소스)
• SAT 해법
  • MiniSat (오픈 소스)이 또한 내부적으로 휴리스틱을 사용하는

는 (사실 그들은에 있습니다 : 문제가 완성 NP이기 때문에).

일반적인 알고리즘/소프트웨어를 사용하지 않으려면 일부 문제에 대해 특별히 추론을 조정해야합니다. 그러나 언급 한 이러한 문제는 조금씩 다르며 다른 발견 적 방법이 필요할 수도 있습니다. 인스턴스의 특수 구조를 분석하는 것도 중요합니다 (임의 인스턴스는 대부분의 실제 문제와 매우 다른 방식으로 동작합니다)! 이러한 특수 목적의 휴리스틱을 설계하는 동안 방법을 구현할 수도 있습니다.이 방법이 귀하의 경우에 더 효과적 일 수 있습니다.

초기 실현 가능 솔루션을 찾는 문제는 많은 메타 휴리스틱 스에서 매우 보편적입니다.

복잡한 주제입니다.