설명

n명의 남자와 n명의 여자가 주어졌을 때, 각각 쌍으로 결혼하십시오.
남자는 여자를 선호하는 순서대로 1부터 n까지 순위를 매겼습니다.
w_1,...,w_n 그리고 각 여성도 마찬가지로 m_1,...,m_n을 수행했습니다. 만약
결과 결혼 세트에는 m_i,w_j 형식의 쌍이 포함되어 있지 않습니다.
m_k,w_l m_i는 w_j보다 w_l을 선호하고 w_l은 m_k보다 m_i를 선호합니다.
결혼생활은 안정적이라고 합니다. Gale과 Shapley(1962)는 다음을 보여주었습니다.
어떤 순위를 선택하든 안정적인 결혼이 존재합니다(Skiena 1990,
p. 245). 미국에서는 Gale과 Shapley의 알고리즘이
(1962)는 병원을 의료 인턴과 연결하는 데 사용됩니다(Skiena 1990,
p. 245).

이 모델은 MIP 컷을 도입하여 다중/전체 솔루션을 생성합니다.
MIP를 해결합니다.

소형 모델 유형 :MIP

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

메인 파일 : stablem.gms

$title 안정적인 결혼 문제 (STABLEM,SEQ=389)

$onText
n명의 남자와 n명의 여자가 주어졌을 때, 각각 쌍으로 결혼하십시오.
남자는 여자를 선호하는 순서대로 1부터 n까지 순위를 매겼습니다.
w_1,...,w_n 그리고 각 여성도 마찬가지로 m_1,...,m_n을 수행했습니다. 만약
결과 결혼 세트에는 m_i,w_j 형식의 쌍이 포함되어 있지 않습니다.
m_k,w_l m_i는 w_j보다 w_l을 선호하고 w_l은 m_k보다 m_i를 선호합니다.
결혼생활은 안정적이라고 합니다. Gale과 Shapley(1962)는 다음을 보여주었습니다.
어떤 순위를 선택하든 안정적인 결혼이 존재합니다(Skiena 1990,
p. 245). 미국에서는 Gale과 Shapley의 알고리즘이
(1962)는 병원을 의료 인턴과 연결하는 데 사용됩니다(Skiena 1990,
p. 245).

이 모델은 MIP 컷을 도입하여 다중/전체 솔루션을 생성합니다.
MIP를 해결합니다.

Gale, D 및 Shapley, LS, 대학 입학 및 안정성
결혼. 미국 수학 월간지 69, 1(1962), 9-15.

Gusfield, D 및 Irving, RW, 안정적인 결혼 문제: 구조
그리고 알고리즘. MIT 출판부, 케임브리지, 매사추세츠, 미국, 1989.

스키에나, S, 6.4.4. 안정적인 결혼. 이산 수학 구현에서:
Mathematica를 이용한 조합론 및 그래프 이론. 애디슨-웨슬리 롱먼
Publishing Co., Inc., 보스턴, 매사추세츠, 미국, 1991.

Weisstein, E W, 안정적인 결혼 문제. MathWorld-A Wolfram 웹에서
자원. http://mathworld.wolfram.com/StableMarriageProblem.html

Sethuraman, V J 및 Teo, C P, 선형 프로그래밍은 결혼 생활을 가져옵니다
행복. 수학 메들리, 싱가포르 수학 학회 25, 2
(1998).

키워드: 혼합정수선형계획법, 결혼 문제, 매칭
$offText

* 게임 사용 ... --data=xxx
$데이터를 설정하지 않은 경우 $set 데이터 사전 설정
$maxsol을 설정하지 않은 경우 $set maxsol 100

$ifThenI %data% == 초기
세트
   m / 앨런, 밥, 칼, 댄 /
   w / 앨리스, 브렌다, 신디, 데비 /;

테이블 wp(w,m) '여성 선호도'
           앨런 밥 칼 댄
   앨리스 3 4 2 1
   브렌다 3 4 1 2
   신디 3 2 1 4
   데비 4 2 3 1;

테이블 mp(m,w) '남자 선호도'
          앨리스 브렌다 신디 데비
   앨런 2 4 1 3
   밥 1 4 2 3
   칼 3 4 2 1
   단 3 2 1 4;

$elseIfI %data% == 미니징크
세트
   m / m1*m5 /
   w / w1*w5 /;

테이블 wp(w,m) '여성 선호도'
       m1 m2 m3 m4 m5
   w1 1 2 4 3 5
   w2 3 5 1 2 4
   파3 5 4 2 1 3
   파4 1 3 5 4 2
   파5 4 2 3 5 1;

테이블 mp(m,w) '남자 선호도'
       w1 w2 w3 w4 w5
   m1 5 1 2 4 3
   m2 4 1 3 2 5
   m3 5 3 2 4 1
   m4 1 5 4 3 2
   m5 4 3 2 1 5;

$elseIfI %data% == 5
세트
   m / 조, 브라이언, 조지, 매트, 짐 /
   w / 에이미, 사라, 수잔, 켈리, 다이앤 /;

테이블 wp(w,m) '여성 선호도'
           조 브라이언 조지 매트 짐
   에이미 1 2 4 3 5
   사라 3 5 1 2 4
   수잔 5 4 2 1 3
   켈리 1 3 5 4 2
   다이앤 4 2 3 5 1;

테이블 mp(m,w) '남자 선호도'
           에이미 사라 수잔 켈리 다이앤
   조 5 1 2 4 3
   브라이언 4 1 3 2 5
   조지 5 3 2 4 1
   매트 1 5 4 3 2
   짐 4 3 2 1 5;

$elseIfI %data% == 수학세계
세트
   m / m1*m9 /
   w / w1*w9 /;

테이블 wp(w,m) '여성 선호도'
       m1 m2 m3 m4 m5 m6 m7 m8 m9
   파1 3 9 3 8 6 2 9 6 8
   w2 1 4 1 7 9 4 3 3 2
   파3 5 8 8 5 2 5 8 2 6
   파4 2 1 9 3 5 1 2 1 4
   파5 8 7 5 2 1 6 7 8 9
   파6 7 6 4 6 4 8 5 4 1
   파7 6 3 2 4 7 3 4 5 3
   파8 9 2 6 9 3 9 6 9 7
   파9 4 5 7 1 8 7 1 7 5;

테이블 mp(m,w) '남자 선호도'
       w1 w2 w3 w4 w5 w6 w7 w8 w9
   m1 7 5 4 9 2 2 1 5 6
   m2 3 4 8 7 6 7 6 6 1
   m3 8 8 3 4 4 8 2 9 4
   m4 9 3 9 2 9 6 3 1 7
   m5 6 1 7 5 8 5 8 2 5
   m6 4 2 5 8 7 3 5 8 8
   m7 2 6 6 3 5 4 4 4 3
   m8 1 7 1 1 1 1 9 3 9
   m9 5 9 2 6 3 9 7 7 2;

$else
$abort 데이터세트 "%data%"가 존재하지 않습니다. premer,five,minizinc를 사용하세요.
$endIf

별칭(m,mm), (w,ww);

이진변수 match(w,m);

가변 순위;

방정식 onem(w), onew(m), stable(w,m), defrank;

defrank.. 순위 =e= sum((w,m), wp(w,m)*match(w,m));

onem(w)..sum(m, match(w,m)) =e= 1;

onew(m)..sum(w, match(w,m)) =e= 1;

stable(w,m).. sum(mm$(wp(w,mm) > wp(w,m)), match(w,mm))
            + sum(ww$(mp(m,ww) > mp(m,w)), match(ww,m)) =l= 1;

모델 sm / 모두 /;

mip 최소화 순위를 사용하여 sm을 해결합니다.

세트
   nn '해의 수' / sol-1*sol-%maxsol% /
   엔(nn)
   솔(nn,w,m);

방정식 cut(nn);

cut(n).. sum(sol(n,w,m), match(w,m)) =l= 카드(w) - 1;

모델 신품/sm, 컷/;

new.modelStat = sm.modelStat;
옵션 limRow = 0, limCol = 0, solPrint = 꺼짐, optCr = 0,solvLink = 5;

루프(nn$(new.modelStat = 1),
   n(nn) = 예;
   sol(nn,w,m) = round(match.l(w,m));
   밉 최소화 순위를 사용하여 새로운 문제를 해결합니다.
);
옵션 sol:0:0:1;
디스플레이 솔;