Faster MIPs Using Custom Heuristics

Watch this webinar to learn what models may benefit from custom MIP heuristics and how to build your own custom MIP heuristics.

[Chrisratata]

At 12:00 given what you stated was the purpose of Constraint 2, my read of the inequality itself at first was that it would *allow* subtours, not prevent them as planned. Why not just say that the summation (i.e., the total number of chosen edges) must equal the size of N? Is it because subpaths are an inevitable interim effect before arriving at a full tour, so you have to keep the algorithm from attempting a next step that closes a subpath into becoming a subtour? I think the intended key here is the "minus 1" since a subtour whose length is anything less than the total number of nodes *in that subset* would be incomplete.

Either way, what's the purpose of specifying [in Constraint 2] that i<j? Isn't the particular value of each index quite arbitrary such that it has no effect on the quality of the tour? If Node A is connected to Node B, then what difference does it make whether i=1 for A & j=2 for B . . . or i=85 for A & j=63 for B? Either would definitely be inconsequential for the final solution, but what's happening during the churning of the algorithm to where this is relevant? OR [I just thought of this!] is it simply to only focus on one diagonal half of the matrix to get rid of the redundancy of symmetry?

[Chrisratata]

Around the 48:00 mark and before, I want to make sure I understand his use of the word "fix" (i.e., henceforth constant vs. make satisfactory). Does he mean "fixing" as in we are solidifying the choice to include those particular edges (i.e., those with x=1 are henceforth constant)? If so, then what is there left to solve for that submodel with the now-selected (x=1) edges while those yet-selected (x!=1) edges are ignored?

I'm sure I'm misunderstanding but it would make more sense to me if "fixed" meant that those edges (x=1) were henceforth preselected, then only those that violate the Subtour Constraint would need to be modified, after which the collection of yet-selected (x!=1) edges were the only subproblem to focus on...?