Let's discuss how to eliminate subtours. Let's take a look at one subtour. Here we have a network. We have five nodes, but there is a subtour which connects only three nodes in one cycle. Okay? If that happens, it's still possible to satisfy all the constraints you just wrote. Because another cycle would be here. You may still see that for each link, as for each node, there is one entering and one leaving, right? One entering, one leaving. But still, they are subtours. We need to impose some further constraints to eliminate subtours, to make sure that we really have a peak cycle that connects everybody. The idea is the following. You have three links connecting you, three guys, right? I'm going to make this not allowed. For each subset of nodes with at least two nodes, we're going to limit the maximum number of arcs we may select it. Among these three nodes, they are three links. You are allowed to choose at most two. Let's take a look at this constraint, and this may be a little bit weird, but we are able to do that. V is the set of all nodes. Okay? S is also a set. S is a subset of V, and we say S is not V. S is a proper subset of your set V. Also we focus only on that S, which has at least two nodes. Okay? If your S has only one node, you don't need to impose anything. Okay. How's this? Whenever you have a set, for example, these three, then this notation means the cardinality of S, which means the number of elements in this set. In this case, for this particular example, the cardinality of S would be three. This is two at the right-hand side. Then what's the left-hand side thing? The left-hand side thing is that you're going to assign values xi1 to this xij. If you say you want to select link i_j, you are going to set xij to be one. This number two says that among these three nodes, the maximum number of arcs you may select is two. You can not select three to make a subtour. You can only select two of them. The thing is that if that's true for all the proper subsets, then this is going to eliminate subtours. Because if you say, I give you four nodes, then you may select at most three among them. If I have 10 nodes, you may select at most nine arcs in it. There's no way for you to form a cycle. That's the idea of alternative one. In this case, if you have n nodes, then you're going to really have a lot of constraints. Okay? There are two to the power of n ways to choose a subset. Then we know there are n ways to have just a subset with one node, and also there are two ways for a subset of no nodes and a subset of n nodes. All right? If that's the case, we have so many different constraints, the number of constraints would be very large if we take alternative one. Alternative two is also very clever. We are going to introduce new variables called u_i, and more precisely, for node i, u_i is k if node i is the kth node to be visited. Pretty much our place that we're going to label each node. Then we're going to label and say that u the first one, u the second one, u the third one. Eventually, we will see how these may help us do the thing. If we say u is the order, u_1 would be one. It doesn't really matter which one do you choose because eventually it's a cycle. It doesn't really matter where to start. That's why u_1 is one. Then for all others, they should all have a u value, but their u_i should be within two and n. Pretty much that says no u_i would be overlapping. The last constraint is here. It says that for each link, if that link has nothing to do with your first node, then we have this constraint. What's this? Suppose this link is selected, x_ij would become one, the right-hand side would become zero. This says that your u_j must be at least u_i plus one. As long as you select a link, your u_j must be at least a u_i plus one. If u_i is one, then this guy would become two. Somehow it points to somewhere. This guy becomes three, this guy becomes four, this guy becomes five. That said, this is the place for you to go back to your original points. You have five nodes, that's why all your u_i are numbers between 1, 2, 3, 4, and 5. The thing is that when we are saying all of this, don't forget what we are doing is that we don't impose these conditions on the initial node. Pretty much that says, we don't really need to worry about this particular constraint. We don't need to worry about this constraint. Pretty much, that means we don't require this particular u_1 to be greater than or equal to u_5, for example, plus one. If that's the case, then what we are trying to do is to say that, you cannot have subtour. Why is that? Suppose you have a graph like this, then somehow you see there is a subtour. Suppose that's the case, then pretty much what we are saying is that, you need to label each node by u_i. That said, these are nodes 1, 2, and 3. Then for u_1, u_2, and u_3, you're going to see that u_2 should be u_1 plus one, u_3 should be u_2 plus one and the u_1 should also be u_3 plus one. That's going to have a conflict. That's impossible, so you cannot have a subtour. But because this part we ignore or we omit the initial node, pretty much when you are looking at your initial node, it is allowed for you to come in back to here and going out from here. There would be no constraint on this particular link. You don't need to worry about that after you have passed through all the links, all the nodes. You don't need to worry about and say that after you go back, you need to further have been the constraint. Saying that these should be related. Pretty much, that's the idea. Basically for both formulations, what we are trying to do is to eliminate subtours. You need to first take a look at the structure of a subtour and then say," You may select at most two links. " or "You may need to ensure that if this is one, this is two, and then this is three." In either way you need to take off at least one arcs and then there is no subtour. That may be somewhat complicated. But if you want to understand this, just give you some examples and then take a look at this constraint, you will be fine. When we have a node, we may also try to calculate the number of constraints, number of variables we have. For u_i we need n additional variables. Then for constraints, here we have n constraints in some sense. Well, let me do it slowly. We have one constraint. Here, I have two constraints in one shot. Then that two constraints should be multiplied by n minus 1. Then lastly here, this is pretty much saying that I don't take a look at node 1, I take a look at all other nodes except node 1. If I have n nodes, I'm going to look at the other set of nodes and then look at the complete graph there. That's going to be n minus 1 times n minus 2 as the number of constraints we have for the last parts. Collectively, basically I think the number of constraints we have would be 1 plus 2 times n minus 1 plus n minus 1 times n minus 2. We can see that there is a difference. If I do this, that's going to be 2n minus 1. This 2n minus 1 would be sound to this part. I will say the number of constraints we need would be 2n minus 1 plus n minus 1 times n minus 2. The exact number actually is not so important. All we want to say is that, the number of constraints seems to be smaller. Previously we have a lot of constraints. The number of constraints is actually exponential, but in this alternative 2, the number of constraints is limited. It's at least polynomial. The complete formulation is here. You use the thing we introduced plus either alternative 1 or alternative 2, then you would have a formulation for a traveling salesperson problems. Now, our last question is which alternative is good? Alternative 1 has a lot of constraints. Alternative 2 has not so many. You may compare the number of constraints. But the interesting thing is that if you formulate the problem with alternative 1, most of the solver would solve your program faster than using alternative 2. I certainly don't have time to talk about why here. I just want to show you a very simple fact. First, when you want to formulate a problem, there may be multiple correct way to do it. We need to first find a correct way. The second, it may be the case that one from Malaysia is better than the other. In the integer programming, that means one's model can be solved. Can be found an optimal solution easier than the others. That's also possible. Somehow in this course, we don't really talk about whether one IP is better than the other specifically. From time to time we give you some examples, but we don't really talk about the theory behind integer programming formulation. That really takes some advanced courses. All I want to say here is that there may be multiple correct formulations. Among them, one may be the best or one may be better than the others. Hopefully, you'll have these ideas in mind. Maybe in the future you may want to spend some time to study these advanced issues.
