1
$\begingroup$

I am trying to build a constraint of the form x[i j] +x[j i] <y[i][j] where x is a decision variable if arc ij is used.

The arcs are defined in terms of tuples. However, not all arcs are available in that [2 3] is presented while [3 2] is not.

y[i][j] is a decision variable too but it is using nodes (not tuple values) representing if the two nodes are covered by the same trip or not.

How can I write this constraint?

Note: When I run it using this constraint, it uses only same arc tuples

   forall(i,j in Setlocations :  i < j && i!=j )

   forall( g in Graph : g.o==j && g.d==i ) 

   forall(m in Graph : m.o==j && m.d==i) 
    x[g] + x[m]  <= z[i][j] ; 
$\endgroup$
1
  • 1
    $\begingroup$ Welcome to OR SE. You wrote a "z" in your constraint. Is that a misprint (should it be "y")? Also, it would help if you edited the question to show the OPL code you use to declare the variables x and y (or z, whichever is correct). $\endgroup$
    – prubin
    Dec 9, 2021 at 0:32

1 Answer 1

1
$\begingroup$

in How to with OPL I shared a few TSP starting points.

TSP with remove circuits is an easy one.

.mod

 // Cities
int     n       = ...;
range   Cities  = 1..n;

// Edges -- sparse set
tuple       edge        {int i; int j;}
setof(edge) Edges       = {<i,j> | ordered i,j in Cities};
int         dist[Edges] = ...;

// Decision variables
dvar boolean x[Edges];

 {int} nodes={i.i | i in Edges} union {i.j | i in Edges};

range r=1..-2+ftoi(pow(2,card(nodes)));


{int} nodes2 [k in r] = {i | i in nodes: ((k div (ftoi(pow(2,(ord(nodes,i))))) mod 2) == 1)};

 

 

/*****************************************************************************
 *
 * MODEL
 *
 *****************************************************************************/

// Objective
minimize sum (<i,j> in Edges) dist[<i,j>]*x[<i,j>];
subject to {
   
   // Each city is linked with two other cities
   forall (j in Cities)
        sum (<i,j> in Edges) x[<i,j>] + sum (<j,k> in Edges) x[<j,k>] == 2;
        
   // Subtour elimination constraints.
 
   
forall(k in r)  // all subsets but empty and all
    sum(e in Edges:(e.i in nodes2[k]) && (e.j in nodes2[k])) x[e]<=card(nodes2[k])-1;  

 }  
 
 
 setof(edge) solEdges       ={e | e in Edges : x[e]==1};
 execute
 {
   writeln(solEdges);
 }
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.