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:

g is forced to be 1 if two variables a and b are 1 \(\Leftrightarrow g \geq a+b-1\) (all variables are binary)

Also, if

(2) we need to avoid a sub-cycle in the graph provided that we do not know whether that let say three cycle-making 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.

asked 07 Jun '12, 01:54

ShahinG's gravatar image

accept rate: 0%

edited 07 Jun '12, 03:38

fbahr's gravatar image

fbahr ♦

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 Dantzig-Fulkerson-Johnson 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 Miller-Tucker-Zemlin 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_i-u_j+1\le \left(n-1\right)(1-x_{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's gravatar image

Ehsan ♦
accept rate: 16%

edited 08 Jun '12, 09:12

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

@Shahin: I think your problem is similar to the traveling salesman problem with profit maximization. I updated my post to reflect on that. This way, you could also ignore my previous comment.

(08 Jun '12, 06:03) 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%20Rubin's gravatar image

Paul Rubin ♦♦
accept rate: 19%

@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 m-n-o 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 m-n-o, 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 ♦♦

@Paul many thanks.

(10 Jun '12, 06:50) ShahinG
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 07 Jun '12, 01:54

Seen: 1,931 times

Last updated: 30 Mar '13, 17:00

OR-Exchange! Your site for questions, answers, and announcements about operations research.