Hi, I wonder if (1) there is a tighter representation for the following constraint or perhaps a way to separate them on the fly upon need:
Also, if (2) we need to avoid a subcycle in the graph provided that we do not know whether that let say three cyclemaking edges will actually appear, how do we model this with some thing different from \(m+n+o \leq 2\) if \(m, n,\) and \(o\) represent variables associated to those edges and they just might appear as 1 if their endpoints force them as in question (1). Any comment is appreciated. 
If I understand your second problem correctly, you need representing subtour elimination constraints (as needed in routing problems such as TSP and VRP). Your own method is similar to the DantzigFulkersonJohnson method which is usually implemented in a cutting plane algorithm as the subtours are identified along the algorithm process (due to exponential number of constraints). Another possible approach, which has a linear number of constraints but results in weaker LP relaxation, is the MillerTuckerZemlin formulation which could help you with what you want. Extensions of this method for more complex situations in VRP such as capacity and time windows constraints are discussed here. $$ \begin{align} u_1=1 \end{align} $$ $$ \begin{align} 2\le u_i\le n,\quad \qquad i\in N,i\ne 1 \end{align} $$ $$ \begin{align} u_iu_j+1\le \left(n1\right)(1x_{ij}),\quad \qquad i,j\in N,i\ne j,i,j\ne 1 \end{align} $$ Update: Based on the new information that the routing decision should be made only for selected nodes (and not all of them), your problem is very similar to the traveling salesman problem with profit maximization, in which the salesman selects nodes based on their respective revenues and tries to maximize the total revenues  total travel costs. Here is a very good paper, which has discussed modeling issues as well as various subtour elimination constraints. The essence of the paper is that the above constraints are still valid, but you should add the node selection variable to the constraints ensuring incoming and outgoing flow at each node as follows: $$ \begin{align} \sum_{j \in N\setminus\big\{i\big\}}(x_{ij}) = y_i,\quad \qquad i\in N \end{align} $$ $$ \begin{align} \sum_{i \in N\setminus\big\{i\big\}}(x_{ij}) = y_j,\quad \qquad j\in N \end{align} $$ answered 07 Jun '12, 06:26 Ehsan ♦ @Ehsan Thanks for the comment. But it is rather different, in TSP or VRP you know that all your nodes are somehow involved in the optimal solution but this is not the case for my problem as I do not know what are those nodes appearing in the any solution and only for those nodes we need to generate the cut. That is why I am looking for a better set of constraint.
(07 Jun '12, 07:48)
ShahinG
I'm not sure whether this is working or not, but mabye you could multiply the last constraint with \(y_i\times yj\) to ensure that this constraint is hold only when both nodes \(i\) and \(j\) are selected. The linearization of \(y_i\times yj\) and then the whole constraint is trivial, but it would add many binary variables.
(07 Jun '12, 07:58)
Ehsan ♦

If you are using a solver that provides callbacks, you should be able to generate cycle elimination constraints (whether the MTZ form or \(m+n+o\le 2\)) on the fly using a cut callback. You might also try a branch callback, in which you look at the most recently added arc, identify which arcs would result in a cycle forming, and zero out their variables as part of the branch. Either way, though, your problem relaxations early in the tree are likely to be weaker than they would be had the cycle elimination constraints been included explicitly. (No free lunch here.) answered 09 Jun '12, 10:34 Paul Rubin ♦♦ @Paul, thanks for your comment.
why should we "zero out their variables as part of the branch."
How do you know which one of the cycle members must be zero?
I can understand separating cut here but not this approach.
(09 Jun '12, 10:49)
ShahinG
Let's use your mno triangle. Suppose that, early on, a branch sets \(m=1\). At that point, we scan for cycles that are one edge short of complete, find none, and do nothing special. Later in that subtree, a branch sets \(n=1\). We again scan for cycles that are one edge short of complete, find mno, and change that branch from \(n=1\) to \(n=1,o=0\). This requires that, at each branch where an edge is added, you scan for potential cycles containing that edge. In the sibling node where the edge is excluded (\(n=0\)), no such scan is required.
(09 Jun '12, 11:17)
Paul Rubin ♦♦
