Operations Research Asked by user3831 on August 19, 2021

I want to solve the following integer programming problem using AMPL. The problem is the following (It was already asked on mathstackexchange.com, but I need to know how to solve it using AMPL):

Let $N={1,…,22}$ be the nodes, and let $P={iin N,jin N:i<j}$ be the set of node pairs. For $(i,j)in P$, let binary decision variable $x_{i,j}$ indicate whether $(i,j)$ is an edge. For $(i,j)∈P$ and $k in N setminus {i,j}$, let binary decision variable $y_{i,j,k}$ indicate whether k is a common neighbor of i and j.

Optimization Model:

**Minimize** $sum_{k in N setminus {i,j}} y_{i,j,k}$

subject to:

begin{align}

sum_{(i,j)in P: k in {i,j}} x_{i,j} &= 5 &&text{for $kin N$} tag1\

x_{i,j} + sum_{k in N setminus {i,j}} y_{i,j,k} &ge 1 &&text{for $(i,j)in P$} tag2\

y_{i,j,k} &le [i<k]x_{i,k} + [k<i]x_{k,i} &&text{for $(i,j)in P$ and $k in N setminus {i,j}$} tag3\

y_{i,j,k} &le [j<k]x_{j,k} + [k<j]x_{k,j} &&text{for $(i,j)in P$ and $k in N setminus {i,j}$} tag4

end{align}

so far I have tried the following in AMPL, but the result has error (Please I need help):

**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;
```

Thanks!

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
;
```

Answered by Oguz Toragay on August 19, 2021

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;
```

Answered by RobPratt on August 19, 2021

2 Asked on August 19, 2021 by k88074

integer programming linear programming lp relaxation relaxation

1 Asked on August 19, 2021 by mengfan-ma

2 Asked on August 19, 2021 by cfp

mixed integer programming nonconvex programming quadratic programming

1 Asked on August 19, 2021 by poofybridge

1 Asked on August 19, 2021 by batwing

2 Asked on August 19, 2021 by clement

2 Asked on August 19, 2021 by fightmilk

0 Asked on August 19, 2021 by s_scouse

1 Asked on August 19, 2021 by harry-cohen

0 Asked on August 19, 2021 by brendan-hill

1 Asked on August 19, 2021 by mostafa

1 Asked on August 19, 2021 by ljg

3 Asked on August 19, 2021

0 Asked on August 19, 2021

1 Asked on August 19, 2021 by george-chang

Get help from others!

Recent Answers

- Lex on Does Google Analytics track 404 page responses as valid page views?
- haakon.io on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?

Recent Questions

- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?
- Does Google Analytics track 404 page responses as valid page views?
- Why fry rice before boiling?

© 2022 AnswerBun.com. All rights reserved. Sites we Love: PCI Database, MenuIva, UKBizDB, Menu Kuliner, Sharing RPP