使用AMPL的組合優化


4

我想使用AMPL解決以下整數編程問題。問題是following(已經在mathstackexchange.com上問過了,但是我需要知道如何使用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的共同鄰居。

優化模型:最小化 $ \ sum_ {k \ in N \ setminus \ {i,j \}} y_ {i,j,k} $

必須遵守:

\開始{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

到目前為止,我已經在AMPL中嘗試了以下方法,但是結果有錯誤(請尋求幫助):

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;

謝謝!

3

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;

3

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
;