10
정수 프로그래밍 문제를 해결하려고합니다.정수 선형 프로그램 문제 해결 : 해결할 수있는 인스턴스가 실행 불가능하다고 주장하는 이유는 무엇입니까?
Int32 a = 0, b = 0;
a = a*-6 + b + 0x74FA - valA;
b = b/3 + a + 0x81BE - valA;
a = a*-6 + b + 0x74FA - valA;
b = b/3 + a + 0x81BE - valA;
// a == -86561, b == -32299
나는이 정수로 구현 : 나는 A와 B의 최종 값을 주어, 모두 사용 SCIP 예를 들어 LPSolve
을 시도했습니다, 나는 다음과 같은 C# 코드에 발라 대한 해결하려는 LP 형식 프로그램합니다 (절단 분할 몇 합병증 발생)
The model is INFEASIBLE
min: ;
+valA >= 0;
+valA < 92;
remAA_sign >= 0;
remAA_sign <= 1;
remAA <= 2;
remAA >= -2;
remAA +2 remAA_sign >= 0;
remAA +2 remAA_sign <= 2;
remAA +4294967296 remAA_range >= -2147483648;
remAA +4294967296 remAA_range <= 2147483647;
remAA +4294967296 remAA_range +2147483648 remAA_sign >= 0;
remAA +4294967296 remAA_range +2147483648 remAA_sign <= 2147483648;
-1 remAA +4294967296 remAA_range +3 remAA_mul3 = 0;
remAB_sign >= 0;
remAB_sign <= 1;
remAB <= 2;
remAB >= -2;
remAB +2 remAB_sign >= 0;
remAB +2 remAB_sign <= 2;
remAB +4294967296 remAB_range >= -2147483648;
remAB +4294967296 remAB_range <= 2147483647;
remAB +4294967296 remAB_range +2147483648 remAB_sign >= 0;
remAB +4294967296 remAB_range +2147483648 remAB_sign <= 2147483648;
+1431655765 remAA +1 offA -2 valA +1 offB -1 remAB +4294967296 remAB_range +3 remAB_mul3 = 0;
a = -86561;
b = -32299;
offA = 29946;
offB = 33214;
-4 offA +3 valA +1431655765 remAA +1 offB +4294967296 Fa - a = 0;
+477218588 remAA -1431655769 offA -1431655764 valA -1431655763 offB +1431655765 remAB +4294967296 Fb - b = 0;
int valA;
int remAA;
int remAA_range;
int remAA_sign;
int remAA_mul3;
int remAB;
int remAB_range;
int remAB_sign;
int remAB_mul3;
int Fa;
int Fb;
int offA;
int offB;
int a;
int b;
하고 그것을 해결하려고
그러나 실제로 가능한 변수 할당을 알고 있기 때문에 실현 가능한 솔루션이 있다는 것을 알고 있습니다. 해결책을 찾을 수 다음과 같은 조건을 원인 추가 :
a = -86561;
b = -32299;
offA = 29946;
offB = 33214;
valA = 3;
remAA = 0;
remAA_range = 0;
remAA_sign = 0;
remAA_mul3 = 0;
remAB = 1;
remAB_range = 0;
remAB_sign = 0;
remAB_mul3 = -21051;
Fa = 0;
Fb = 21054;
두 개의 서로 다른 해법이 가능한 문제가 불가능하다 주장했다. 내가 쓴 조건을 위반하고 있습니까? 무슨 일이야? 실제로 문제를 해결하는 해결사가 있습니까?
모델을 빌드하고 .lp 파일을 내 보낸 다음 CPLEX를 통해 실행합니다. 그것은 좋은 갈등 (infeasibility) 정보가 있습니다. 내 이메일 주소는 gmail.com에있는 내 사용자 이름입니다. 나는 당신이 Pastebin 또는 비슷한 것에 붙여 놓을 수 있다고 생각합니다. – raoulcousins
@raoul 내가 scip에 사용했던 lp-cplex 파일을 이메일로 보냈습니다. –
CPLEX로 해결 했으므로 실현 가능했습니다. 최적해는 목적 함수 값이 0입니다. 이것은 조건 완화가 (카파)가 3.4 인 기본 매트릭스를 갖는 LP 완화와 동일합니다. 여분의 제약으로, 목적 함수는 동일했다. 조건 수는 4.6입니다.CPLEX이이 특정 문제에 대해 SCIP와 다른 후드에서 무엇을하는지 확신 할 수 없습니다. neos-server.org로 모델을 풀고 CPLEX를 사용할 수 있습니까? – raoulcousins