설명

가장 가까운 문자열 문제(CSP)는 다음을 최소화하는 중앙 문자열을 찾습니다.
중앙 스트링과 다른 모든 스트링 사이의 해밍 거리.
해밍 거리는 일치하지 않는 문자의 수를 계산합니다. 예를 들어,
'CATCC'와 'CTTGC'의 해밍 거리는 2입니다.

세 가지 공식이 제시됩니다. 제제 1과 2만 사용할 수 있습니다.
작은 문제를 위해. 공식 3은 가장 직관적인 공식입니다.
범용 MIP 코드와 잘 작동합니다.

CPLEX의 루트 노드 휴리스틱은 다음을 수행한다는 점에 유의해야 합니다.
아주 좋아요. 1~2개의 절대적인 차이가 있는 경우 CPLEX는 다음에서 솔루션을 찾습니다.
모든 제안된 크기에 대해 몇 초 정도 소요됩니다. 예를 들어 아래 설정은
전역 최적값에서 1.0 이내인 솔루션이 생성됩니다.
또는 1% 미만:

옵션 optCr = 0.01, optCa = 1.99;

소형 모델 유형 :MIP

카테고리 : 슬롯 게임 모델 라이브러리

메인 파일 : csp.gms

$title 가장 가까운 문자열 문제(CSP,SEQ=306)

$onText
가장 가까운 문자열 문제(CSP)는 다음을 최소화하는 중앙 문자열을 찾습니다.
중앙 스트링과 다른 모든 스트링 사이의 해밍 거리.
해밍 거리는 일치하지 않는 문자의 수를 계산합니다. 예를 들어,
'CATCC'와 'CTTGC'의 해밍 거리는 2입니다.

세 가지 공식이 제시됩니다. 제제 1과 2만 사용할 수 있습니다.
작은 문제를 위해. 공식 3은 가장 직관적인 공식입니다.
범용 MIP 코드와 잘 작동합니다.

CPLEX의 루트 노드 휴리스틱은 다음을 수행한다는 점에 유의해야 합니다.
아주 좋아요. 1~2개의 절대적인 차이가 있는 경우 CPLEX는 다음에서 솔루션을 찾습니다.
모든 제안된 크기에 대해 몇 초 정도 소요됩니다. 예를 들어 아래 설정은
전역 최적값에서 1.0 이내인 솔루션이 생성됩니다.
또는 1% 미만:

옵션 optCr = 0.01, optCa = 1.99;

Meneses, CN, Lu, Z, Oliveira, C A S 및 Pardalos, P M,
정수 프로그래밍을 통한 가장 가까운 문자열 문제에 대한 최적의 솔루션입니다.
INFORMS Journal on Computing 16, 4 (2004), 419-429.

키워드: 혼합 정수 선형 계획법, 가장 가까운 문자열 문제, 계산 생물학
$offText

$eolCom //

세트
   n '문자열'
   m '문자열'
   '알파벳';

매개변수 x(n,m) '문자열 값';

$문자가 설정되지 않은 경우 $문자 26개 설정
$문자열을 설정하지 않은 경우 $set 문자열 4
$길이를 설정하지 않은 경우 $길이 6 설정

세트
   n / s1*s%strings% /
   m / c1*c%길이% /
   a / a1*a%문자% /;

* 종이의 샘플 데이터
테이블 x(n,m)
      c1 c2 c3 c4 c5 c6
   s1 4 9 6 6 5 18 // 다르다
   s2 13 5 4 9 1 14 // 중앙값
   s3 12 5 14 7 20 8 // 길이
   s4 13 5 4 9 21 13 // 중간;

* 샘플 데이터 인식
$%strings%+%length%+%letters% == 4+6+26이 아닌 경우
x(n,m) =uniformInt(1,card(a));

if(카드(n)*카드(m) > 50,
   옵션 limCol = 0, limRow = 0, solPrint = off, resLim = 10, optCr = 0.01, optCa = 1.999;
그렇지 않으면
   옵션 resLim = 5, optCr = 0.0, optCa = 0.999;
);

* 제형 P1
변수
   d 't와 x 사이의 최대 차이'
   t(m) '참조 문자열'
   z(n,m) '문자열이 다릅니다.';

이진변수 z;

방정식
   e1(n) 'd의 하한'
   e2(n,m) '차이의 하한'
   e3(n,m) '차이의 상한';

e1(n)..합(m, z(n,m)) =l= d;

* x <> 티
e2(n,m)..t(m) =l= t.up(m)*z(n,m) + x(n,m)*(1 - z(n,m));

e3(n,m)..t(m) =g= t.lo(m)*z(n,m) + x(n,m)*(1 - z(n,m));

t.lo(m) = smin(n, x(n,m));

t.up(m) = smax(n, x(n,m));

모델 p1A / e1, e2, e3 /;

매개변수 보고서 '요약 보고서';
보고서(m,'t.lo') = t.lo(m);
보고서(m,'t.up') = t.up(m);

mip를 사용하여 p1A min d를 해결합니다.

보고서(m,'p1A') = t.l(m);
보고서('객관적','p1A') = p1a.objVal;
보고서('Est Global','p1A') = ceil(p1a.objEst - 1e-6);

* 제제 P2
set ma(m,a) '위치별로 가능한 문자';
ma(m,a) = sum(n, ord(a) = x(n,m));

* 디스플레이 엄마;

이진 변수 v(m,a) '문자 선택';

방정식
   e4(m) '하나만 선택하세요'
   e5(m) 't에 문자 값을 할당합니다';

e4(m).. sum(ma(m,a), v(ma)) =e= 1;

e5(m)..t(m) =e= sum(ma(m,a), ord(a)*v(ma));

모델 p2 / e1, e2, e3, e4, e5 /;

mip를 사용하여 p2 min d를 해결합니다.

보고서(m,'p2') = t.l(m);
보고서('객관적','p2') = p2.objval;
report('Est Global','p2') = ceil(p2.objEst - 1e-6);

* 제제 P3
방정식 e6(n) '일치하는 문자 수 계산';

e6(n).. 카드(m) - sum(ma(m,a),(x(n,m) = ord(a))*v(ma)) =l= d;

모델 p3 / e4, e6 /;

mip를 사용하여 p3 min d를 해결합니다.

t.l(m) = sum(ma(m,a), ord(a)*v.l(ma));
보고서(m,'p3') = t.l(m);
보고서('객관적','p3') = p3.objVal;
report('Est Global','p3') = ceil(p3.objEst - 1e-6);

보고서 표시;