# 使用AMPL的組合優化

$$N = \ {1，…，22 \}$$作為節點，並讓$$P =\ {i \ in N，j \ in N：i 是節點對的集合。對於P 中的 （i，j）\ ，讓二進制決策變量 x_ {i，j} 表示 （i，j） 是否為邊。對於 （i，j）∈P 和 k \ in N \ setminus \ {i，j \} ，讓二元決策變量 y_ {i，j，k} 表示k是否為i和j的共同鄰居。$$

\開始{align}\ sum _ {（i，j）\ in P：\ k \ in \ {i，j \}} x_ {i，j}＆= 5 && \ text {for k \ in N } \ tag1 \\x_ {i，j} + \ sum_ {k \ in N \ setminus \ {i，j \}} y_ {i，j，k}＆\ ge 1 && \ text {對於（i，j）\ in P} \ tag2 \\y_ {i，j，k}＆\ le [i

example1.mod

``````set N:={1..22};
set P:={i in N, j in N: i<j};
set K:={i in N, j in N, k in N: k!=i,k!=j};

var x{i in P, j in P} binary; #for x_{ij}
var y{i in P, j in P, k in K} binary; #for y_{ijk}

var x{j in P,k in K: j<k} binary; #for x_{jk}
var x{i in P,k in K: i<k} binary; #for x_{ik}
var x{k in K,j in P: k<j} binary; #for x_{kj}
var x{k in K,i in P: k<i} binary; #for x_{ki}

minimize z: sum{k in K} y[i,j,k];

subject to Constraint1{i in P, j in P}: sum{k in N}x[i,j]=5;
subject to Constraint2{i in P, j in P}: sum{k in K}y[i,j,k]>=1-x[i,j] ;
subject to constraint3{i in P, j in P, k in K}: y[i,j,k]<=x[i,k]+x[k,i];
subject to constraint4{i in P, j in P, k in K}:y[i,j,k]<=x[j,k]+x[k,j];
``````

example2.run

``````reset;
model example1.mod;
option solver cplex;
solve;
display x, z;
``````

Here is the SAS code that I used to obtain the results in the linked thread. Maybe it will help you correct your AMPL errors. In particular, note that you should declare each variable only once.

``````proc optmodel;
num n = 22;
set NODES = 1..n;
num degree {NODES} = 5;
set NODE_PAIRS = {i in NODES, j in NODES: i < j};

var X {NODE_PAIRS} binary;

var Y {<i,j> in NODE_PAIRS, k in NODES diff {i,j}} binary;

con DegreeCon {k in NODES}:
sum {<i,j> in NODE_PAIRS: k in {i,j}} X[i,j] = degree[k];

con DiameterTwo {<i,j> in NODE_PAIRS}:
X[i,j] + sum {k in NODES diff {i,j}} Y[i,j,k] >= 1;

con CommonNeighbor1 {<i,j> in NODE_PAIRS, k in NODES diff {i,j}}:
Y[i,j,k] <= (if <i,k> in NODE_PAIRS then X[i,k] else X[k,i]);

con CommonNeighbor2 {<i,j> in NODE_PAIRS, k in NODES diff {i,j}}:
Y[i,j,k] <= (if <j,k> in NODE_PAIRS then X[j,k] else X[k,j]);

solve;
set EDGES = {<i,j> in NODE_PAIRS: X[i,j].sol > 0.5};
put EDGES=;
quit;
``````

Here is the AMPL interpretation of @RobPratt's answer which works perfectly using the gurobi in my local pc:

``````model;
param n := 22;
set NODES = 1..n;
param degree {NODES} := 5;
set NODE_PAIRS = {i in NODES, j in NODES: i < j};

var X {NODE_PAIRS} binary;
var Y {(i,j) in NODE_PAIRS, k in NODES diff {i,j}} binary;

subject to DegreeCon {k in NODES}:
sum {(i,j) in NODE_PAIRS: k in {i,j}} X[i,j] = degree[k];
subject to DiameterTwo {(i,j) in NODE_PAIRS}:
X[i,j] + sum {k in NODES diff {i,j}} Y[i,j,k] >= 1;
subject to CommonNeighbor1 {(i,j) in NODE_PAIRS, k in NODES diff {i,j}}:
Y[i,j,k] <= (if (i,k) in NODE_PAIRS then X[i,k] else X[k,i]);
subject to CommonNeighbor2 {(i,j) in NODE_PAIRS, k in NODES diff {i,j}}:
Y[i,j,k] <= (if (j,k) in NODE_PAIRS then X[j,k] else X[k,j]);

option solver gurobi;
solve;
display X, Y;
set EDGES = {(i,j) in NODE_PAIRS: X[i,j].sol > 0.5};
let EDGES = ;
quit;
``````

The results that I got:

``````Gurobi 9.0.2: optimal solution; objective 0
230671 simplex iterations
166 branch-and-cut nodes
Objective = find a feasible point.
X [*,*]
:    2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22:=
1    1   1   1   1   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
2    .   0   0   0   0   1   0   0   1   0   0   0   0   0   0   0   1   1   0   0   0
3    .   .   0   0   0   0   1   0   0   1   0   0   0   0   1   0   0   0   0   0   1
4    .   .   .   0   0   0   0   1   0   1   0   0   0   0   1   0   0   0   1   0   0
5    .   .   .   .   0   0   0   0   0   0   1   1   0   1   0   1   0   0   0   0   0
6    .   .   .   .   .   0   0   0   0   1   0   0   1   0   0   0   0   0   0   1   1
7    .   .   .   .   .   .   1   0   0   0   0   0   0   1   0   0   0   0   1   1   0
8    .   .   .   .   .   .   .   1   0   0   0   1   1   0   0   0   0   0   0   0   0
9    .   .   .   .   .   .   .   .   1   0   1   0   0   0   0   0   0   0   0   1   0
10   .   .   .   .   .   .   .   .   .   0   0   0   0   0   0   1   0   1   0   0   1
11   .   .   .   .   .   .   .   .   .   .   0   0   0   1   0   0   0   1   0   0   0
12   .   .   .   .   .   .   .   .   .   .   .   0   0   1   0   0   1   0   0   0   1
13   .   .   .   .   .   .   .   .   .   .   .   .   0   0   0   0   0   1   1   1   0
14   .   .   .   .   .   .   .   .   .   .   .   .   .   0   0   1   1   0   1   0   0
15   .   .   .   .   .   .   .   .   .   .   .   .   .   .   0   1   0   0   0   0   0
16   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   1   1   0   0   1   0
17   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   0   0   0   0   0
18   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   1   0   0   0
19   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   0   0   0
20   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   0   1
21   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   0
;
``````