# Combinatorial Optimization using AMPL

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

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

## Related Questions

### What is a general procedure to prove that the LP relaxation of an IP delivers the optimal IP solution?

2  Asked on August 19, 2021 by k88074

### CPLEX MIP warm start seems slow down the program?

1  Asked on August 19, 2021 by mengfan-ma

### (Iterative?) Solutions to a certain quadratic program with non-convex constraints

2  Asked on August 19, 2021 by cfp

### Problem with implementing squared terms in the objective function

1  Asked on August 19, 2021 by poofybridge

### Scheduling with setup cost

0  Asked on August 19, 2021 by dirk-nachbar

### Is a convex or MILP (without big-M) formulation possible for this problem

1  Asked on August 19, 2021 by batwing

### MINLP Solution same as Global Optimum?

2  Asked on August 19, 2021 by clement

### Linear objective function with non-linear constraints

2  Asked on August 19, 2021 by fightmilk

### Meta papers on operations research

2  Asked on August 19, 2021 by luke599999

### Verifying the correctness of KKT conditions

0  Asked on August 19, 2021 by s_scouse

### How can I use warm start in C#

1  Asked on August 19, 2021 by fhm-ider

### Feasible sets represented as point clouds

1  Asked on August 19, 2021 by harry-cohen

### Is this the same as Agent Based DES or something different?

0  Asked on August 19, 2021 by brendan-hill

### Column generation when intractable variables appear in the objective function

1  Asked on August 19, 2021 by mostafa

### Is there any OR way to solve this problem?

3  Asked on August 19, 2021 by samiczy

### Find a particular optimal solution

1  Asked on August 19, 2021 by ljg

### How to find all vertices of a polyhedron

3  Asked on August 19, 2021

### Can every convex problem use Lagrangian dual method?

0  Asked on August 19, 2021

### Does strong duality hold when I dualize only a subset of the constraints?

1  Asked on August 19, 2021 by george-chang