# Combinatorial Optimization using AMPL

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=\{i\in N,j\in N:i 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 k\in 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

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!

• What's the error? – Nikos Kazazakis Jul 8 at 16:59
• @Nikos Kazazakis The error displayed is: syntax error context: set K:={i in N, j in N, k in N: >>> k!=i, <<< k!=j}; – user3831 Jul 8 at 17:07
• that can be written as set K:={i in N, j in N, k in N: k!=i and k!=j}; i.e. replace the comma with the and operator on the logical condition. Section 5.5 of the AMPL reference contains more examples of conditioning on indexing expressions. – dhasson Jul 8 at 17:17
• @dhasson Thanks, but it is not the only error what I got now. – user3831 Jul 8 at 17:23

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;

• @RobPrattThanks. But I am not familiar with SAS. Also I would like to know whether the objective function declaration is correct in order to calculate the diameter using AMPL (In case I am mistaken). By the way, I appreciated your approach. The idea is very interesting. – user3831 Jul 8 at 17:39
• I recommend translating my working code to AMPL syntax, which is very similar. For example, change "con" to "subject to" for constraint declaration. Regarding your objective, it is not correct syntax because you have omitted $i$ and $j$ from the summation index set. But the diameter is not a sum of $y_{i,j,k}$, anyway. Instead, this model enforces diameter 2 via the second constraint. – RobPratt Jul 8 at 17:45

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
;