MH Studio · YouTube · 8:37
This 150-second lecture segment introduces a second integer-programming formulation for the Traveling Salesperson Problem aimed at automatically breaking subtours. After showing the title and chapter outline, the speaker defines a new non-negative variable for as the number of cities visited before reaching city i, under the crucial assumption that the tour starts from city 1. The binary arc variable is reviewed as indicating whether the tour goes directly from city i to city j. Using a hand-drawn i-to-j illustration, the lecture derives the conditional rule implies , while imposes no direct relation between and . This if-then logic is then linearized as the big-M inequality , with M required to be large enough that . The slide recommends , the total number of cities, and notes that is the tighter best estimate, though n is used in the presentation. The segment ends with the final MTZ-style subtour-breaking constraint for all distinct i,,,n, stated as automatically eliminating subtours. No worked numerical example appears in this clip, and the full formal proof that the constraint removes every subtour is not completed within the available duration. This lecture segment introduces the Miller-Tucker-Zemlin (MTZ) subtour elimination constraint for the Traveling Salesperson Problem. It defines auxiliary continuous variables to track city visit order and explains how the Big-M method uses the binary edge variables to conditionally enforce the ordering constraint <= . The instructor emphasizes excluding the starting city from these constraints. Two graphical examples are analyzed: a valid full tour that yields consistent bounds and feasible u values, and an invalid subtour configuration that generates a cyclic chain of strict inequalities, thereby proving its mathematical infeasibility. This 150-second lecture segment explains the subtour-breaking constraint in TSP Formulation-2. It first verifies on a 5-node example that a subtour not containing node 1 forces inconsistent values of the auxiliary ordering variables , making the subtour infeasible. The clip then presents the full integer-programming model: minimize total arc cost subject to one-incoming and one-outgoing constraints, binary arc variables , the subtour-breaking inequalities , and nonnegativity of . The lecturer states that the main advantage is automatic subtour elimination, allowing standard solvers such as CPLEX or Gurobi to be used with conventional branch-and-bound. The stated disadvantages are loss of assignment-problem structure, which rules out the Hungarian method for the LP relaxation, and the addition of about (n-1)^2 constraints. The clip ends with an exercise prompt to solve Formulation-2 using Cplex, but no numerical solution is performed here. This 67-second lecture segment first states that the TSP can be tested computationally by solving Formulation-2 with the Cplex solver, using data from Example-1 and Example-2. It then shifts to a conceptual overview of improving the TSP branch-and-bound approach. The speaker identifies two key directions: tightening lower bounds and tightening upper bounds. The slide specifies that the assignment problem approach is used for tighter lower bounds, while heuristic or metaheuristic methods are used for tighter upper bounds. The central claim is that better bounds can drastically reduce the size of the branch-and-bound enumeration tree. No formulas, numerical instances, or solver outputs are shown in this clip.
Use the learning inspector for key ideas and moments, or open the reading tabs for the complete notes.
Generated from the video's visuals and explanation; not verbatim speech.
The clip opens on a lecture titled "Traveling Salesperson Problem" and then shows a chapter outline placing this material under Exact Methods, specifically Formulation-2. The speaker states that this formulation is designed to break all subtours automatically, establishing the modeling goal before any variables are introduced.
The slide titled "TSP: Subtour Breaking Constraint" introduces a new auxiliary variable . It is defined as a non-negative variable representing the number of cities visited before reaching city , for , with the explicit assumption that the tour starts from city 1. The speaker emphasizes that this starting-city assumption is crucial because the later constraint relies on a notion of order along the tour.
Next, the lecture reviews the standard binary arc variable , which equals 1 when the tour travels directly from city to city and equals 0 otherwise. The goal is now to connect this arc variable with the order variables and , because subtour elimination requires enforcing consistency between route selection and visitation order.
A hand-drawn diagram with nodes labeled and supports the intuitive derivation. If , meaning the arc from to is used, then city must be reached after city , so the order variable must satisfy . If , the speaker explicitly notes that no direct relationship between and can be inferred, because the model should not constrain the relative order of cities unless that specific arc is selected.
The conditional statement is then converted into a linear inequality using a big-M formulation: , where is chosen large enough that . When , the term disappears and the ordering constraint becomes active. When , the added relaxes the inequality so that it does not impose the direct ordering relation.
The lecture then specializes the big-M constant to the TSP setting. The slide states that a good estimate is , the total number of cities, and adds that the tighter best estimate is . The speaker says the presentation will use in the slides, so the final displayed model adopts rather than the sharper value.
Substituting yields the final subtour-breaking constraint shown on screen: for all with . The speaker identifies this as the constraint that automatically breaks subtours. The clip ends after presenting the formula and its purpose; it does not include a full formal proof that every possible subtour is excluded, nor does it work a numerical example.
The lecture begins by presenting the subtour breaking constraint for the Traveling Salesperson Problem. The formula is introduced for all with . The instructor highlights a critical design choice: the indices start at 2, deliberately excluding city 1, which serves as the fixed start and end point of the tour. This exclusion is described as the 'crux' of the constraint, preventing artificial restrictions on the depot.
The role of the auxiliary variable is clarified as tracking the sequence of visited cities. The term functions as a Big-M relaxation. When an edge is selected (), this term vanishes, strictly enforcing . Conversely, when the edge is absent (), the addition of ensures the inequality is trivially satisfied, effectively disabling the constraint for that pair. The value is noted as a robust estimate for the Big-M constant.
To validate the formulation, a concrete example with cities is constructed. A directed graph displays a valid Hamiltonian cycle: . The active edges within the subset generate specific inequalities: , , and . Additionally, the global bound applies since city 1 is the start/end point.
The instructor systematically deduces the upper bounds for each variable by tracing the path backward from the start city. Because node 3 connects directly to node 1, is assigned the maximum possible value of 4. Propagating this bound through the chain of inequalities yields , , and . This establishes a strict, acyclic ordering: .
Feasible integer assignments are then demonstrated on the graph. One valid solution sets , while another shifts the entire sequence down to . Both sets perfectly satisfy all derived inequalities and the upper bound constraint, confirming that the formulation correctly accommodates valid, single-loop tours without eliminating legitimate solutions.
The analysis then pivots to an invalid configuration to test the constraint's eliminative power. A new graph illustrates two disjoint subtours: a 2-city loop () and a 3-city loop (). The edges comprising the secondary loop activate the constraints , , and , creating a closed chain of dependencies among the variables.
By chaining these three inequalities together, the system demands that . This circular strict ordering constitutes a fundamental mathematical contradiction, as no real number can be strictly less than itself. Although the video concludes before explicitly stating the final result, the setup definitively proves that the MTZ constraints render any subtour configuration mathematically infeasible.
The clip opens on a slide titled "TSP: Subtour Breaking Constraint" with a five-node directed graph. The lecturer begins a concrete verification by assigning the largest ordering value to node 3, writing . The purpose of this step is to test whether a proposed cyclic solution can satisfy the auxiliary ordering constraints.
Because the remaining cycle does not connect to node 3, the lecturer chooses node 4 arbitrarily and assigns , noting that this value must stay below 3 since the node leading into node 1 should carry the highest value. This sets up a chain of implications through the other inequalities on the slide.
Using the displayed inequality , the assignment forces . Then using , the value forces . These are direct substitutions into the visible constraints, and they show how the ordering variables propagate around the cycle.
The lecturer then examines the third displayed inequality . With , this requires to be 3, contradicting the previously derived value . The slide therefore demonstrates an explicit inconsistency in the same variable, and the spoken conclusion is that the subtour is infeasible under the subtour-breaking constraints.
This example illustrates the general logic of the constraint . When an arc is selected, and the inequality reduces to , imposing a strict ordering from to . Chaining such strict inequalities around a closed cycle eventually demands that some -value be larger than itself, which is impossible.
The presentation then switches to the full model on a slide titled "TSP: Formulation-2". The objective is , minimizing total travel cost over selected arcs. The lecturer states that this objective and some constraints are similar to Formulation-1, while the new ingredients are the subtour-breaking constraint and the associated nonnegative variables.
The degree constraints are shown as for every node and for every node . These enforce exactly one incoming and one outgoing selected arc at each node. The model also declares and for .
The subtour-breaking family is restated in the full formulation as for all with . This is the central addition that distinguishes Formulation-2 from the earlier assignment-style model.
The lecturer then summarizes the practical advantage: because subtours are broken automatically by these explicit inequalities, the model can be given directly to commercial solvers such as CPLEX or Gurobi and solved with conventional branch-and-bound. No special-purpose subtour-handling algorithm has to be built from scratch for this formulation.
Two disadvantages are stated. First, the added constraints and auxiliary variables damage the pure assignment-problem structure, so the Hungarian method can no longer be used to solve the LP relaxation. Second, the formulation introduces approximately additional constraints, increasing the overall problem size relative to Formulation-1.
The clip closes on a slide titled "TSP: Formulation-2 Testing" with the prompt: "Use the data from Example-1 and Example-2, and solve Formulation-2 of TSP using Cplex solver." The lecturer explicitly says that this video will not solve the TSP problem, so the exercise is only announced here and not worked out in the clip.
The clip opens on a slide titled "TSP: Formulation-2 Testing" whose text asks the viewer to use the data from Example-1 and Example-2 and solve Formulation-2 of the TSP with the Cplex solver. The speaker frames this as a departure from the manual branch-and-bound discussion: instead of continuing that method here, the lecture points to a computational route through Cplex.
The slide then changes to "TSP: Improving the B & B Approach," and the lecture turns from solver use to algorithmic refinement of branch and bound. The speaker states that there are two main areas of improvement: the lower bound and the upper bound. The mathematical point is that a tighter pair of bounds narrows the gap used for pruning, so fewer nodes need to be explored in the enumeration tree.
For the lower-bound side, the slide and narration identify the assignment problem approach as the method already covered in the course. This is presented as a way to obtain tighter lower bounds for TSP branch and bound. The speaker also notes that another lower-bound approach will appear later in the slide sequence, but that later method is not shown in this excerpt.
For the upper-bound side, the lecture says that heuristics or metaheuristic methods are typically used to obtain tighter upper bounds. The reasoning is that better feasible tours give smaller upper bounds, which again strengthens pruning in the branch-and-bound tree. The clip closes by announcing that subsequent slides will discuss heuristic methods for the TSP.
This segment introduces a second integer-programming formulation for the Traveling Salesperson Problem. Its stated purpose is to build a model that automatically breaks subtours. The chapter outline places it under Exact Methods as Formulation-2.
The new variable is defined for cities as the number of cities visited before reaching city . It is non-negative and encodes a tour order relative to a fixed starting city. The video stresses that the tour is assumed to start from city 1, and this assumption is essential for the subtour-breaking logic.
The speaker reviews as the usual TSP arc-selection variable. It is binary and equals 1 exactly when the tour travels directly from city to city ; otherwise it equals 0. The formulation seeks a relationship among , , and .
If the arc from to is used, then the order at must be at least one larger than the order at . This gives the implication . If the arc is not used, the video explicitly says no direct relation between and can be asserted.
The conditional relation is rewritten as a single linear inequality using a big-M term: . When , the constraint reduces to the desired ordering relation. When , the term relaxes the inequality so it does not force a direct ordering. The slide requires to be large enough that .
For this TSP formulation, the big-M constant is chosen from the problem size. The slide recommends , the total number of cities, and notes that is the tighter best estimate. The presentation nevertheless uses in the final displayed constraint.
Substituting gives the final constraint shown in the video: for all distinct . The speaker presents this as the condition that automatically breaks subtours by enforcing increasing order values along selected arcs. The clip states the result but does not complete a full formal proof within the available time.
The core integer programming constraint used to prevent disconnected loops in the Traveling Salesperson Problem. It utilizes auxiliary variables to enforce a strict sequential ordering on visited cities, ensuring a single valid tour.
A modeling technique where a large constant (here estimated as ) multiplies the complement of a binary variable . This dynamically activates or deactivates the ordering constraint based on whether a specific edge is included in the tour.
The subtour constraints are strictly defined for indices . City 1 is intentionally omitted from the -variable ordering to serve as an unconstrained depot, which is essential for the logical validity of the formulation.
When edges form a single Hamiltonian cycle, the active constraints create a directed acyclic graph of inequalities. This allows for consistent backward substitution to find valid integer bounds for all variables, as demonstrated by the 5-city example.
If selected edges form a closed loop excluding the start city, the constraints generate a cyclic chain of strict inequalities (e.g., ). This mathematical contradiction proves that subtours cannot yield feasible solutions.
The key new constraint in Formulation-2 is for all with . If arc is selected, then and the constraint becomes , forcing a strict ordering along that arc. If the arc is not selected, the term relaxes the inequality so it does not restrict that pair.
The worked 5-node example assigns , then , which forces from and from . But the remaining inequality forces , contradicting . Hence a closed subtour among nodes cannot satisfy the ordering constraints.
The full model minimizes subject to one incoming and one outgoing arc at each node, binary arc variables, the subtour-breaking inequalities, and nonnegative auxiliary variables for . The lecturer describes this as the overall "formulation two" for TSP.
The model retains assignment-style degree constraints: for each node , and for each node . These ensure every city has exactly one predecessor and one successor in the selected route structure.
The arc variables are binary, , and the auxiliary ordering variables satisfy for . These domain declarations are part of what makes the subtour-breaking constraint work as a mixed-integer formulation.
Because subtours are eliminated automatically by the explicit inequalities, the model can be solved with standard integer-programming software such as CPLEX or Gurobi using conventional branch-and-bound. The lecturer emphasizes that one does not need to build a special branch-and-bound scheme just for TSP.
The added subtour-breaking system destroys the pure assignment-problem structure, so the Hungarian method cannot be used on the LP relaxation. It also adds about constraints, making the model larger than Formulation-1.
The final slide asks the viewer to use data from Example-1 and Example-2 and solve Formulation-2 of TSP with the Cplex solver. The lecturer states that this particular video does not perform that solution.
The opening slide states a concrete computational task: use the data from Example-1 and Example-2 and solve Formulation-2 of the TSP with the Cplex solver. The speaker contrasts this with the branch-and-bound method, indicating that this segment is about testing the formulation in a solver environment rather than developing the enumeration tree by hand.
The lecture organizes improvements to the TSP branch-and-bound approach into two categories: tighter lower bounds and tighter upper bounds. The key claim is that improving both sides of the bounding process can drastically reduce the size of the enumeration tree, because stronger bounds enable more effective pruning.
For lower bounds, the slide specifies the assignment problem approach as the method used to obtain tighter bounds. The speaker notes that this is the approach already seen in the course slides and that another lower-bound method will be introduced later outside this clip.
For upper bounds, the slide specifies heuristic or metaheuristic methods as the standard way to obtain tighter bounds. The lecture's point is that better feasible solutions lower the upper bound, which complements stronger lower bounds in shrinking the branch-and-bound search space.
Explore conditions, steps and evidence. Supplementary explanations are labeled separately from content shown in the video.
Slide text: "Let be a non-negative variable that represents the number of cities visited before reaching city i, ".
Speaker says is a new non-negative variable representing the number of cities visited before reaching city i.
Auxiliary integer-order variable for city i; the number of cities visited before reaching city i, under the assumption that the tour starts from city 1.
Non-negative variable for ; later constrained by and used for i,,,n.
Slide asks for a relationship between , , and .
Speaker reviews x_{ij} as a binary variable equal to 1 if we visit from city i to city j, otherwise 0.
Binary arc-selection variable indicating whether the tour travels directly from city i to city j.
Binary variable, \{0,1\}.
Subscripts in , , and the final quantifier use i.
Hand-drawn node labeled i connected to node labeled j.
i
City index or origin city in an arc from i to j.
In the final displayed constraint, ,,n.
Subscripts in , , and the final quantifier use j.
Hand-drawn node labeled j connected to node labeled i.
j
City index or destination city in an arc from i to j.
In the final displayed constraint, ,,n.
Slide shows and states "where M is some big number, such that ".
Speaker says the if-then scenario can be modeled like a big M constraint and that M is a very large number.
The slide uses M as a generic big number and then recommends n; it does not formally prove that n is sufficient in this clip.
M
Big-M constant used to deactivate the subtour-breaking inequality when .
A sufficiently large number satisfying ; recommended value on the slide is n.
Slide states "A good estimate of M can be n, the total number of cities" and the final constraint quantifies over i,,,n.
Speaker says the best value for M will be n in this case and that n will be used in the slides.
n
Total number of cities in the TSP instance.
Positive integer; used as the chosen big-M value and as the upper index bound for cities.
Slide text defines as a non-negative variable representing the number of cities visited before reaching city i, for .
The speaker discusses finding feasible values for all the u's.
Non-negative integer variable representing the position (or number of cities visited before) of city i in the tour, for .
\{2, , n\}
Slide text uses in the subtour breaking constraint and states 'If , then '.
Binary decision variable indicating whether the edge from city i to city j is included in the tour.
i, \{2, , n\},
Slide text states 'A good estimate of M can be n, the total number of cities'.
Speaker mentions values ranging from 2 up to n.
n
Total number of cities in the Traveling Salesperson Problem instance.
,
Slide text mentions 'A good estimate of M can be n' and 'the best estimate for M is (n-1)'.
Annotations on the graph slide point to constraints saying 'where the big-M part disappears' and 'where the big-M part appears'.
M
A large constant used in the Big-M method to relax constraints when a binary variable is zero.
On the slide titled "TSP: Formulation-2", the variable appears in the objective , in the two degree constraints, in the binary declaration \{0,1\}, and inside the subtour-breaking constraint through the term .
Binary route-selection variable for the directed arc from node i to node j.
\{0,1\},,,n
The objective function on the formulation slide is written as .
The video does not explicitly define in this clip; its meaning is inferred from standard TSP notation and from its use as a coefficient of .
Cost or distance coefficient associated with traveling from node i to node j.
Indexed by i,,,n
Speaker introduces another formulation for the Traveling Salesperson Problem whose idea is to break all subtours automatically.
Title slide reads "Traveling Salesperson Problem"; outline slide lists Exact Methods with Formulation-1 and Formulation-2.
This segment presents a second integer-programming formulation for the TSP. Its stated purpose is to build a model that automatically breaks subtours, rather than relying only on explicit subtour-elimination constraints.
Applies to the Traveling Salesperson Problem.
The formulation is intended to prevent subtours automatically.
Slide text defines as a non-negative variable representing the number of cities visited before reaching city i, , assuming tour starts from city 1.
Speaker emphasizes that the tour starting from city 1 is a crucial assumption affecting the subtour-breaking constraint.
The model introduces for each city . The variable records how many cities are visited before reaching city i, thereby encoding a position or order along the tour. The definition depends on fixing city 1 as the starting city.
Defined for cities .
Assumes the tour starts from city 1.
is non-negative.
Slide asks for a relationship between , , and .
Speaker reviews x_{ij} as binary, equal to 1 if visiting from city i to city j, otherwise 0.
The speaker reviews the standard TSP arc variable . It is binary and indicates whether the selected tour contains the directed move from city i to city j. The new formulation relates this arc variable to the auxiliary order variables and .
is binary.
means the directed arc from i to j is used.
means that direct arc is not used.
Slide states: If , then .
Hand-drawn nodes i and j are connected by a blue line while the speaker discusses going from city i to city j.
Speaker says that if we go from city i to city j, then should be greater than or equal to plus one; if we do not go directly, no relation is certain.
The derivation identifies the logical relationship needed for subtour breaking. If the tour uses the arc from i to j, then the order value at j must be at least one larger than the order value at i. If the arc is not used, the model should not force any direct relation between and .
Applies when considering a possible directed arc from city i to city j.
The implication is active only when .
When , no direct relation between and is asserted.
Slide states: The above scenario can be modeled as , where M is some big number, such that .
Speaker says this is the classical if-then scenario and can be modeled like a big M constraint.
The conditional statement is converted into a single linear inequality using a big-M term multiplied by . When , the M-term vanishes and the ordering constraint is enforced. When , the added M makes the inequality non-binding, provided M is large enough.
M must be sufficiently large.
The slide states the requirement .
is binary.
Slide asks what could be a good estimate of M and answers that a good estimate can be n, the total number of cities; in fact, the best estimate is (n-1).
Speaker says the best value for M will be n in this case, that the best estimate could be n minus one, but n will be used in the slides.
The video distinguishes a good estimate n from a best estimate n-1 but does not provide a proof of optimality for n-1 in this clip.
For this formulation, the big-M constant is chosen based on the number of cities. The slide recommends because there are n cities, while also noting that is the tighter best estimate. The presentation proceeds with .
n is the total number of cities.
M must satisfy the upper-bound requirement for the u variables.
The clip uses n rather than n-1 in the final displayed constraint.
Final slide text: Thus, the following condition will automatically break the subtours: ,,,n,.
Speaker concludes that this is the subtour avoiding constraint built based on the if-then statements.
The clip displays the constraint but does not complete a formal proof that it eliminates every subtour.
Substituting into the big-M inequality gives the final subtour-breaking constraint shown in the video. It is imposed for all ordered pairs of distinct cities i and j among 2 through n. The constraint enforces increasing u-values along used arcs and thereby prevents closed subtours not containing the fixed start city 1.
Applied for all i,,,n with .
Uses .
Assumes the tour starts from city 1.
are non-negative order variables.
are binary arc variables.
Slide displays the formula: , , , n, .
Speaker explains that the condition is designed for all i, j not equal to 1, avoiding the starting city.
This integer programming constraint ensures that if an edge from city i to city j is selected (), the position of city j in the tour must be strictly greater than the position of city . If the edge is not selected (), the term becomes n, which acts as a large enough constant (Big-M) to make the inequality trivially satisfied, thus relaxing the constraint.
Applies to all pairs of cities i and j from 2 to n, where .
Assumes the tour starts and ends at city 1.
Slide text: 'A good estimate of M can be n, the total number of cities (in fact, the best estimate for M is (n-1)).'
Annotations explicitly refer to the 'big-M part' appearing or disappearing based on the value of .
The Big-M method is used to conditionally enforce constraints in integer programming. In this TSP formulation, the term acts as the Big-M component. When , this term is 0, enforcing the strict ordering . When , the term becomes n, which is large enough to ensure the inequality holds regardless of the values of and , effectively disabling the constraint for that specific edge.
M must be chosen large enough so that the constraint is always satisfied when the binary variable is 0.
In this specific formulation, M is estimated as n, the total number of cities.
Slide title: "TSP: Subtour Breaking Constraint".
Displayed constraint: ,,,n,.
The lecturer calls it "the subtour avoiding or subtour breaking constraint".
This constraint uses auxiliary ordering variables to enforce a consistent ordering along selected arcs. If an arc (i,j) is chosen, then and the inequality reduces to , forcing the successor node to have a strictly larger u-value. If the arc is not chosen, then and the large additive term n makes the inequality automatically satisfied, so it imposes no effective restriction on that pair.
Applies for all ordered pairs i,j with i,\{2,,n\} and .
is binary.
is nonnegative for ,,n.
The slide "TSP: Formulation-2" shows minimize : .
The lecturer says, "So this is the overall formulation. We call this as formulation two."
The optimization goal is to minimize total travel cost over all selected directed arcs. The lecturer states that this objective is similar to Formulation-1.
Summation runs over all node pairs i,,,n.
The formulation slide lists ,,n.
The lecturer says some of the constraints are similar to formulation one.
Each node j must have exactly one incoming selected arc from some other node i. This is one of the assignment-style degree constraints retained in Formulation-2.
Holds for every node ,,n.
Self-loops are excluded by .
Slide parenthetical: "assuming tour starts from city 1".
Speaker calls this a very crucial assumption and says it will affect the subtour breaking constraint.
The clip states the importance of the assumption but does not show a counterexample where changing the start city breaks the formulation.
The subtour-breaking formulation assumes that the tour starts from city 1; this assumption is crucial for defining the order variables and for the resulting constraint to work.
The TSP tour is represented with directed arc variables .
Order variables are defined for relative to a start city.
Applies to the formulation presented for cities indexed with a distinguished start city 1.
Slide bullet: If , then .
Speaker says that when going from city i to city j, should be greater than or equal to plus one.
If the tour travels directly from city i to city j, then the order variable at j must be at least one larger than the order variable at i.
is the binary variable for traveling from i to j.
and count cities visited before reaching i and j.
For a considered pair of cities i and j with .
Slide bullet: If , then we cannot say any direct relation between and .
Speaker says if we do not go directly from city i to city j, we are not sure about the relationship between and .
If , the formulation does not assert any direct relationship between and .
is binary.
The only asserted direct relation comes from the case .
For a considered pair of cities i and j with .
Slide states: Thus, the following condition will automatically break the subtours: for all i,,,n, .
Speaker calls it the subtour avoiding constraint built based on the if-then statements.
The clip asserts the subtour-breaking effect but does not include the full formal proof within the available duration.
The constraint for all distinct i,,,n is presented as automatically breaking subtours in the TSP integer program.
The tour starts from city 1.
are non-negative order variables for .
are binary arc variables.
M is chosen as n.
,,,n with .
The lecturer says there is inconsistency because would equal both 0 and 3, and concludes that the subtour is infeasible under these constraints.
The slide shows the chain , , together with assigned values , , and also .
Text on slide: "Thus, any subtour that does not contain Node-1 will Have inconsistency in the value of variable ."
If a closed subtour among nodes 2,,n is selected, then the subtour-breaking constraints force contradictory values for at least one auxiliary variable , so that subtour is infeasible.
The selected arcs form a subtour not containing node 1.
All arcs in the subtour have .
The subtour-breaking constraint is imposed for all i,,,n,\ .
For any subtour on nodes within \{2,,n\} that does not include node 1.
The lecturer says, "so you could use commercial solvers like Cplex or Gurobi and can solve the TSP problem. That is you do not have to build a special branch and bound approach for solving the TSP problem."
Advantages text states that the formulation can be automated and solved using the conventional B&B approach.
Because the subtours are broken automatically by the explicit constraints, Formulation-2 can be solved using standard commercial solvers and conventional branch-and-bound rather than a special-purpose TSP algorithm.
The model includes the subtour-breaking constraints and the auxiliary variables .
For the full Formulation-2 model as presented.
The lecturer says, "we are losing the assignment problem structure, so we cannot use Hungarian method to solve the LP relaxation."
Disadvantages text states: "The assignment problem structure is damaged."
After adding the subtour-breaking constraints and auxiliary variables, the relaxation loses assignment-problem structure, so the Hungarian method cannot be used to solve the LP relaxation.
One considers the LP relaxation of Formulation-2.
For the LP relaxation of the full formulation.
The speaker states that by identifying a better lower bound and a better upper bound, the branch and bound enumeration tree size can be reduced drastically.
The slide heading is "TSP: Improving the B & B Approach" and the listed rules are exactly the two bound-improvement directions.
In TSP branch and bound, improving both the lower bound and the upper bound can drastically reduce the size of the enumeration tree.
The method under discussion is branch and bound for TSP
The bounds being improved are the lower bound and the upper bound
General statement about the branch-and-bound enumeration tree when bounds are tightened.
The speaker says the slides so far used the assignment problem approach for lower bounds and that heuristics or metaheuristics are typically used for upper bounds.
The slide lists "Lower bounds: Use assignment problem approach ..." and "Upper bounds: Use heuristic or metaheuristic methods ...".
For the TSP branch-and-bound approach discussed here, the lecture associates tighter lower bounds with the assignment problem approach and tighter upper bounds with heuristic or metaheuristic methods.
The context is the TSP branch-and-bound framework presented in these slides
Lecture-specific association between bound type and improvement technique.
Slides progress from asking for a relationship among , , to the conditional inequalities, then to the big-M form, then to , and finally to the quantified subtour-breaking constraint.
Speaker explains the review of variables, the if-then logic, the big-M modeling, the choice of M, and the final constraint.
A hand-drawn connection between nodes i and j illustrates the case of traveling from city i to city j.
The derivation establishes the intended constraint but stops before a complete formal proof that every subtour is eliminated.
Review the variables used in the formulation: indicates whether the arc from i to j is used, and records the number of cities visited before reaching city i.
Definitions shown on the slide and explained by the speaker.
If the tour goes directly from city i to city j, then j is reached after i, so its order value must be at least one larger.
Logical consequence of interpreting and as visit counts before reaching the respective cities.
If the arc from i to j is not used, the model should not force a particular ordering between those two cities.
Stated explicitly on the slide and in the audio.
Convert the conditional statement into a linear inequality using a big-M term. When , the term is zero and the ordering constraint is active; when , the term relaxes the inequality.
Standard big-M linearization of an if-then constraint, as identified by the speaker.
Choose the big-M constant as the total number of cities. The slide notes that n-1 is the tighter best estimate, but the presentation uses n.
Slide recommendation and speaker explanation for selecting M.
Substitute and impose the inequality for every ordered pair of distinct cities from 2 through n, producing the final subtour-breaking constraint.
Final displayed formula on the slide.
The video derives an MTZ-style subtour elimination constraint by encoding the required increase in city order along used arcs and linearizing the conditional relation with a big-M constant chosen as n.
Graph shows a full tour 1->3->2->5->4->1. Constraints listed are <=, <=, <=, and ,,,<=4.
Speaker walks through the logic: starting from node 3 reaching node 1, can take max value 4. Then <=3, <=2, <=1, leading to .
Since the tour goes from node 3 to node 1 (the start/end city), node 3 is the last city visited before returning to the start. With cities, the maximum position index for any other city is 4.
Definition of as the number of cities visited before reaching city i, and the structure of the full tour.
The edge from 2 to 3 is in the tour (), so the subtour constraint applies without the Big-M relaxation. Since <= 4, must be at most 3.
Applying the subtour breaking constraint formula with and substituting the bound for .
The edge from 4 to 2 is in the tour (). Applying the constraint and using the bound for gives <= 2.
Applying the subtour breaking constraint formula with and substituting the bound for .
The edge from 5 to 4 is in the tour (). Applying the constraint and using the bound for gives <= 1.
Applying the subtour breaking constraint formula with and substituting the bound for .
Combining the inequalities derived from the edges in the tour establishes a strict ordering of the positions of these cities.
Transitivity of the strict inequalities implied by <= .
For the given full tour, the constraints successfully force a strict, valid ordering of the u variables, allowing feasible integer assignments like (, , , ) or (, , , ).
Graph shows two disjoint subtours: 1->3->1 and 2->5->4->2. Constraints listed are <=, <=, <=.
Speaker begins to analyze the subtour configuration, noting the node reaching city 1 is node 3.
The video cuts off before the speaker completes the derivation showing the contradiction for the 2-5-4 subtour.
Edge 4->2 is present in the subtour, so and the Big-M term vanishes.
Application of the subtour breaking constraint for an active edge.
Edge 2->5 is present in the subtour, so and the Big-M term vanishes.
Application of the subtour breaking constraint for an active edge.
Edge 5->4 is present in the subtour, so and the Big-M term vanishes.
Application of the subtour breaking constraint for an active edge.
Chaining the three inequalities yields <= <= <= , which simplifies to <= , a mathematical contradiction.
Transitivity of inequalities leading to an impossible statement for real numbers.
The subtour breaking constraints create a cyclic set of strict inequalities for any closed loop not containing the starting city, proving that such configurations are mathematically infeasible.
The lecturer assigns , then chooses node 4 and assigns , then derives and from the displayed inequalities, and finally notes that another edge gives , producing contradiction.
Visible inequalities: , , , with bound ,,,.
The graph shows a 2-cycle on nodes 1 and 3 and a 3-cycle on nodes 2, 4, and 5.
The exact arc directions in the drawn 3-cycle are visually small, but the displayed inequalities identify the relevant ordered pairs as (4,2), (2,5), and (5,4).
The lecturer first assigns the highest value to the node reached from node 1 in the 1-3 cycle.
Stated verbally and written next to node 3 on the slide.
From the remaining disconnected cycle, the lecturer arbitrarily picks node 4 and assigns a feasible value below 3.
Stated verbally and written next to node 4 on the slide.
Using the inequality together with forces to be 1.
Derived from the displayed constraint and the assigned value .
Using the inequality together with forces to be 0.
Derived from the displayed constraint and the assigned value .
Using the inequality together with forces to be at least 3, and in the lecturer's spoken chain this is treated as giving .
Derived from the displayed constraint and the assigned value .
The same variable is forced to take two different values, which is impossible.
Direct comparison of the previous two derived assignments.
The attempted assignment around the subtour 2-4-5 leads to a contradiction, so that subtour is infeasible under the subtour-breaking constraints.
The general constraint is shown as .
The binary declaration \{0,1\} is shown on the formulation slide.
When arc (i,j) is selected, the big-M term vanishes and the constraint becomes an ordering requirement from i to j.
Substitution into the displayed subtour-breaking constraint using \{0,1\}.
When arc (i,j) is not selected, the right-hand side is increased by n, making the inequality nonbinding for the example sizes shown.
Substitution into the displayed subtour-breaking constraint using \{0,1\}.
If all arcs in a cycle are active, chaining the reduced inequalities around the cycle forces a strict increase in u-values that returns to the starting node.
Composition of the active-arc inequalities around a closed directed cycle.
Chaining around the cycle yields an impossibility, so a fully active subtour cannot satisfy the constraints.
Transitivity of > applied to the chained inequalities.
The constraint enforces a strict ordering along selected arcs; a closed selected cycle would require a variable to be strictly greater than itself, which is impossible.
Slide shows a 5-node graph with a Hamiltonian cycle 1-3-2-5-4-1 and lists the corresponding active constraints.
Speaker says 'Let us take an example for a full tour...' and walks through finding feasible values for u.
Verify that the subtour breaking constraints allow feasible integer solutions for the u variables when the selected edges form a single valid tour covering all cities.
cities.
Tour edges: (1,3), (3,2), (2,5), (5,4), (4,1).
Constraints apply for i,j >= 2.
Find a feasible set of values for , , , satisfying all active constraints and bounds.
Identify the active constraints corresponding to the edges within the subset of cities {2,3,4,5}.
Edges (5,4), (4,2), and (2,3) have , reducing the general constraint to <= .
Apply the upper bound for the u variables.
Since there are 5 cities and city 1 is the start/end, the maximum number of cities visited before reaching any other city is 4.
Provide one valid assignment of integer values.
Substituting these values satisfies <=2, <=3, <=4, and all are <=4.
Provide another valid assignment of integer values.
Substituting these values satisfies <=1, <=2, <=3, and all are <=4.
Feasible solutions exist, such as (, , , ) or (, , , ), confirming the constraints do not eliminate valid full tours.
Both provided sets of values strictly satisfy all listed inequalities and the upper bound constraint.
Slide shows a 5-node graph with two disjoint cycles: 1-3-1 and 2-5-4-2, along with the active constraints for the second cycle.
Speaker says 'Now let us take another example where we do not have a complete tour...' and begins analyzing the subtour.
The video ends before the speaker explicitly states the contradiction, though the setup clearly implies it.
Analyze the feasibility of the u variables when the selected edges form disjoint subtours instead of a single valid tour.
cities.
Subtour edges: (1,3), (3,1) and (2,5), (5,4), (4,2).
Constraints apply for i,j >= 2.
Determine if a feasible set of values for , , , exists for this configuration.
Identify the active constraints for the edges forming the subtour among cities {2,4,5}.
Edges (4,2), (2,5), and (5,4) have , reducing the general constraint to <= .
Chain the inequalities to derive a contradiction.
Adding the three inequalities yields <= , which simplifies to 3 <= 0, or equivalently, following the strict ordering .
No feasible solution exists because the constraints force a strict cyclic ordering (), which is a mathematical contradiction.
The derived contradiction proves that any closed loop not containing the starting city violates the subtour breaking constraints.
The slide shows nodes 1 and 3 forming one cycle and nodes 2, 4, and 5 forming another cycle.
The displayed inequalities are , , , with ,,,.
The lecturer narrates the assignment process and identifies the contradiction as arising from the subtour.
The precise drawing orientation of each arrow in the 3-cycle is small on screen, but the algebraic inequalities identify the ordered pairs used in the explanation.
Given a candidate solution containing a subtour on nodes 2, 4, and 5, verify whether the subtour-breaking constraints admit a consistent assignment of the u-values.
Selected arcs include the cycle among nodes 2, 4, and 5.
The relevant constraints shown are , , .
The bound shown is ,,,.
The lecturer assigns and then .
Determine whether the subtour can satisfy all displayed constraints.
Choose node 4 arbitrarily from the disconnected cycle and assign a feasible value less than 3.
Stated by the lecturer and written on the slide.
From and , infer .
Substitution into the displayed inequality.
From and , infer .
Substitution into the displayed inequality.
From and , the lecturer obtains the conflicting requirement .
Substitution into the displayed inequality as narrated in the video.
The same variable is forced to equal both 0 and 3, which is impossible.
Direct inconsistency between the two derived values.
The subtour on nodes 2, 4, and 5 is infeasible under the subtour-breaking constraints.
The contradiction and demonstrates infeasibility; the slide also states that any subtour not containing node 1 will create inconsistency in the value of some .
Slide title: "TSP: Formulation-2 Testing".
Question text: "Q. Use the data from Example-1 and Example-2, and solve Formulation-2 of TSP using Cplex solver."
The lecturer says, "In this video, we are not going to solve the TSP problem."
The referenced data from Example-1 and Example-2 are not shown in this clip.
Use the data from Example-1 and Example-2, and solve Formulation-2 of TSP using Cplex solver.
The formulation to be used is Formulation-2.
The solver named on the slide is Cplex.
The required input data come from Example-1 and Example-2, which are outside this clip.
Solve the TSP instance with the newly introduced formulation using a commercial solver.
The clip only presents the exercise prompt and states that the solution will not be performed here.
Visible question slide plus the lecturer's closing remark.
No numerical answer is provided within this clip.
The slide explicitly frames the task as a testing exercise to be done with Cplex, and the lecturer states that this video will not solve the TSP problem.
The slide text gives the task: "Use the data from Example-1 and Example-2, and solve Formulation-2 of TSP using Cplex solver."
The speaker says they are going to see how to solve the TSP problem using the Cplex solver.
No numerical instance data, model equations, or solver output are shown in this clip.
Use the data from Example-1 and Example-2 to solve Formulation-2 of the TSP with the Cplex solver.
Data from Example-1
Data from Example-2
Formulation-2 of TSP
Cplex solver
Demonstrate that the TSP formulation can be solved computationally with Cplex instead of by manual branch and bound.
Identify the computational route: the slide asks for Formulation-2 of TSP to be solved with Cplex.
Directly stated on the slide and reinforced by the speaker's introduction.
Use the previously introduced Example-1 and Example-2 data as the input instance for the solver-based test.
The slide explicitly names those examples as the data source.
The clip states the task but does not display the solved result.
No verification is shown within this segment; only the problem statement and intended method are visible.
Title slide reads "Traveling Salesperson Problem" with date March 31, 2020.
Outline slide lists About TSP, Exact Methods with Formulation-1 and Formulation-2, Heuristic Methods, and Conclusion.
Title slide
Chapter Outline slide
Formulation-2 bullet
The presentation moves from the title slide to the chapter outline.
The outline identifies Formulation-2 under Exact Methods.
The topic remains the Traveling Salesperson Problem.
The segment is framed as part of a larger lecture sequence.
The opening visuals locate the clip as the beginning of a lecture section introducing a second exact TSP formulation focused on automatic subtour breaking.
Slide title is "TSP: Subtour Breaking Constraint".
Red-highlighted text defines as the number of cities visited before reaching city i, , assuming tour starts from city 1.
definition text
red emphasis
slide title
The slide introduces the auxiliary variable .
The phrase about the number of cities visited before reaching city i is visually emphasized.
The goal remains building an IP model that automatically breaks subtours.
City 1 is fixed as the assumed starting city.
The visual emphasis marks as the key new ingredient distinguishing this formulation from a plain arc-variable TSP model.
Two hand-drawn red circles labeled i and j appear, connected by a blue line.
Bullets state If , then , and If , then no direct relation can be said between and .
The drawing shows an undirected-looking blue line, while the spoken and symbolic context treats travel from city i to city j as directional.
Node i
Node j
Blue connecting line
conditional bullets
The diagram appears while the speaker discusses moving from city i to city j.
The slide adds the two cases and .
The labels i and j represent cities.
The relation being explained concerns arc usage and order variables.
The sketch supports the intuitive derivation: using the i-to-j move forces j to occur later than i in the tour order, while not using that move leaves no direct ordering implication.
Slide shows , then , then the final constraint for all i,,,n, .
Generic big-M inequality
M estimate text
final quantified inequality
The conditional relation is replaced by a single linear inequality with M.
M is estimated as n, with n-1 noted as tighter.
The final constraint is displayed with universal quantification over i,,,n, .
remains binary.
remains the order variable for cities .
The tour-start assumption at city 1 remains in force.
The visual sequence shows the standard modeling pattern: identify an if-then logical condition, linearize it with big-M, choose a problem-specific M, and state the resulting family of constraints.
Nodes 1 through 5 appear sequentially, followed by directed edges forming a Hamiltonian cycle. Text boxes listing constraints and bounds appear alongside the graph.
Specific numerical values for , , , are overlaid on the nodes to demonstrate feasible solutions.
Nodes 1, 2, 3, 4, 5
Directed edges forming a cycle
Constraint text boxes
Variable value overlays
Nodes and edges are drawn to form a complete tour.
Constraint inequalities are listed based on the active edges.
Feasible integer values for u variables are displayed on the nodes.
The underlying graph structure remains a 5-node complete graph representation.
The general form of the subtour constraint remains constant at the top of the slide.
The visual progression maps the abstract algebraic constraints directly onto the geometric structure of the tour, showing how selecting specific edges activates specific inequalities that bound the u variables.
The previous graph clears, and new edges are drawn forming two distinct, disconnected cycles: one between nodes 1 and 3, and another between nodes 2, 4, and 5.
A new set of constraint text boxes appears, reflecting only the edges within the {2,4,5} subtour.
Nodes 1, 2, 3, 4, 5
Directed edges forming two disjoint cycles
Constraint text boxes
Edges are redrawn to represent a fragmented tour with subtours.
The list of active constraints updates to reflect the new edge selections.
The node positions remain fixed.
The general subtour constraint formula remains visible at the top.
The visual shift highlights how changing the selected edges alters the system of inequalities, setting up a cyclic dependency among the u variables that leads to infeasibility.
A graph with five numbered circular nodes is shown; nodes 1 and 3 form one small cycle, and nodes 2, 4, and 5 form another cycle.
A green pointer moves among the nodes and edges while the lecturer assigns values and highlights the relevant inequalities.
The exact visual direction of every arrow in the 3-cycle is hard to read at this scale, though the displayed inequalities identify the ordered pairs used in the argument.
Five numbered nodes
Directed edges forming a 2-cycle on nodes 1 and 3
Directed edges forming a 3-cycle on nodes 2, 4, and 5
Green pointer
Displayed inequalities , ,
Bound ,,,
The pointer first indicates node 3 while is discussed.
It then moves to node 4 while is assigned.
It proceeds to node 5 and node 2 as the chain of inequalities is evaluated.
A conflicting label appears alongside the earlier derived .
The underlying graph structure remains the same throughout the verification segment.
The displayed subtour-breaking family and the three specific inequalities remain visible.
The visual demonstration shows how assigning ordering variables around a closed subtour forces incompatible values, thereby proving that the subtour cannot satisfy the constraints.
At about 85 seconds the slide changes from "TSP: Subtour Breaking Constraint" to "TSP: Formulation-2".
The new slide lists the full minimization model and later reveals advantages and disadvantages text at the bottom.
Title bar "TSP: Formulation-2"
Objective function
Two degree constraints
Subtour-breaking constraint
Binary declaration
Nonnegativity declaration
Advantages text
Disadvantages text
The view switches from a graph-based verification example to a complete algebraic formulation.
Bottom text first shows advantages, then later shows disadvantages.
The subtour-breaking inequality remains the central new constraint carried over from the previous slide.
The presentation moves from a concrete contradiction example to the full mathematical model and then summarizes practical consequences of using that model.
A blue-header slide titled "TSP: Formulation-2 Testing" shows a single question line about solving Formulation-2 of TSP using Cplex solver.
A green pointer dot moves around the slide text while the slide remains otherwise static.
Slide title bar
Question text
Green pointer dot
The pointer dot shifts position across the text area.
The slide content remains unchanged during this interval.
No formulas or numerical data are added on screen.
The visual functions as a prompt slide introducing a solver-based test of the TSP formulation.
The slide changes to "TSP: Improving the B & B Approach" with two starred bullets for lower bounds and upper bounds.
The green pointer dot moves near the bullet lines while the rest of the slide stays fixed.
Slide title bar
Lower bounds bullet
Upper bounds bullet
Green pointer dot
The pointer dot moves between the two bullet items as the speaker discusses them.
Only two improvement categories are listed.
No equations or algorithmic pseudocode appear on the slide.
The slide visually organizes the lecture into two branches of improvement: tightening lower bounds and tightening upper bounds.
Slide explicitly says "assuming tour starts from city 1".
Speaker calls this a very crucial assumption and says it affects the subtour breaking constraint.
One might think the definition of works independently of which city is chosen as the start.
The video stresses that the formulation assumes the tour starts from city 1, and this choice is crucial for the subtour-breaking constraint presented here.
Slide states: If , then we cannot say any direct relation between and .
Speaker says that without going directly from i to j, we are not sure about the relationship between and .
One might infer that every pair of cities must satisfy regardless of whether the arc is used.
The direct ordering relation is asserted only when . When , the formulation intentionally avoids imposing a direct relation between and .
The slide distinguishes a good estimate from the best estimate .
The speaker emphasizes choosing M based on the number of cities rather than leaving it arbitrary.
The clip does not discuss numerical conditioning or solver performance in detail.
One might think that once a big-M value is valid, making it larger has no modeling significance.
The analyst adds: The video at least indicates that the value of M must relate to the problem size, and specifically notes that n minus one is tighter than n; in practical integer programming modeling, an excessively large M typically weakens the linear relaxation and may impair solution efficiency.
Slide text specifies the constraint applies for ', , , n'.
Speaker emphasizes: 'we are avoiding the city from which the tour starts... that is one of the crux of this constraint.'
Believing the subtour breaking constraint should be applied to all cities, including the starting city (city 1).
The constraint is deliberately defined only for i, j >= 2. Excluding the starting city prevents the formation of cyclic inequalities that would include the depot, ensuring that only valid paths originating from or returning to the depot are modeled correctly without artificial restrictions on the depot's 'position'.
The constraint contains the term , which disappears only when .
The lecturer explains that the constraint breaks subtours automatically once included in the model.
One might think imposes for every pair i,j regardless of whether the arc is used.
The inequality is only restrictive when . When , the added term n relaxes the constraint so that it does not enforce ordering on that unused arc.
Disadvantages text: "The assignment problem structure is damaged."
The lecturer says this means the Hungarian method cannot be used for the LP relaxation.
Because the two degree constraints resemble assignment constraints, one may assume the whole model still has assignment-problem structure.
The added subtour-breaking constraints and auxiliary variables destroy the pure assignment structure, so assignment-specific algorithms such as the Hungarian method no longer apply to the relaxation.
The speaker contrasts the current topic with using the branch and bound method and says they will instead see how to solve the TSP problem using the Cplex solver.
One might assume that solving TSP with Cplex is just another presentation of the same manual branch-and-bound procedure discussed earlier.
The lecture explicitly separates the two: this segment introduces a solver-based route for Formulation-2, distinct from the hand-developed branch-and-bound discussion.
The speaker says there are two areas, lower bound and upper bound, and that better bounds reduce the enumeration tree size drastically.
The slide lists lower-bound and upper-bound improvement as separate bullets.
One might think improving either bound alone is enough, or that lower and upper bounds are interchangeable tools.
The lecture treats them as two distinct improvement axes: lower bounds are tightened via the assignment problem approach, while upper bounds are tightened via heuristic or metaheuristic methods.
Speaker introduces the formulation as a way to break subtours automatically, then defines for that purpose.
Slide goal is followed by the definition of .
The auxiliary variable is introduced specifically to make the automatic subtour-breaking formulation possible.
The definition of precedes the conditional statement when .
The conditional ordering relation is meaningful only after and have been interpreted as visit-count/order variables.
The slide asks for a relationship among , , and , then states the implication involving .
The if-then relation uses as the trigger that decides whether the ordering constraint between and should be enforced.
The conditional bullets are followed by the slide line "The above scenario can be modeled as" and the big-M inequality.
The big-M inequality is presented as the linear model of the preceding if-then logical condition.
The generic M inequality is followed by the question of estimating M and the answer , with n-1 noted as best.
Choosing specializes the generic big-M formulation to the TSP with n cities.
After stating , the slide displays the final constraint with .
The final subtour-breaking constraint is obtained by substituting the chosen value into the big-M inequality.
Final slide text says the condition will automatically break the subtours.
The final constraint is the concrete mechanism by which the second TSP formulation achieves its stated goal of automatic subtour breaking.
The term in the constraint formula directly utilizes the concept of a large constant M (estimated as n) to relax the inequality.
The Big-M method is the underlying mechanism used to construct the conditional subtour breaking constraint, allowing it to enforce ordering only when an edge is selected.
The speaker uses the specific instances of the constraint generated by the graph edges to logically deduce the bounds and contradictions for the u variables.
The derivations demonstrating the feasibility of full tours and the infeasibility of subtours rely entirely on applying the algebraic rules defined by the subtour breaking constraint.
The same inequality appears on the verification slide and again in the full formulation slide.
The lecturer says the new thing in Formulation-2 is the subtour avoiding or subtour breaking constraint.
The subtour-breaking constraint introduced in the verification example is incorporated into the complete Formulation-2 model alongside the objective and degree constraints.
The disadvantages text states that the assignment problem structure is damaged.
The model retains the two degree constraints but adds subtour-breaking constraints and variables.
Although the incoming and outgoing degree constraints resemble an assignment problem, adding the subtour-breaking system contrasts with that structure and removes the applicability of assignment-specific methods.
Advantages text says the formulation can be automated and solved using the conventional B&B approach.
The lecturer names CPLEX and Gurobi as solvers that can handle the TSP with this formulation.
The explicit subtour-breaking constraints are what allow the model to be passed directly to standard integer-programming solvers using conventional branch-and-bound.
Slide defines as the number of cities visited before reaching city i.
Speaker calls the assumption that the tour starts from city 1 crucial.
Slide asks for a relationship between , , and and then gives the conditional implication.
Slide models the scenario as .
Slide states M can be n and that the best estimate is n-1.
Final displayed constraint is for all i,,,n, .
Slide says if , no direct relation can be said between and .
Speaker explains the rationale for restricting indices to 2 through n.
Slide shows the term and discusses estimating M.
Graph shows a disjoint cycle and the resulting chained inequalities.
The slide explicitly displays under the title "TSP: Subtour Breaking Constraint".
The lecturer derives and and calls this an inconsistency due to the subtour.
The graph shows a separate cycle on nodes 2, 4, and 5.
Covered · Title and outline introduce the second TSP formulation and its goal of automatically breaking subtours.
Covered · Slide defines the auxiliary variable and the crucial assumption that the tour starts from city 1.
Covered · Speaker reviews the binary arc variable and sets up the search for a relationship among , , and .
Covered · Hand-drawn i-j illustration accompanies the conditional ordering logic for used and unused arcs.
Covered · The conditional relation is linearized with a big-M constraint and M is specialized to n, with n-1 noted as tighter.
Covered · Final quantified subtour-breaking constraint is displayed and identified as the automatic subtour elimination condition.
Covered · Introduction of the MTZ subtour breaking constraint, definition of variables, explanation of the Big-M method, and the specific exclusion of the starting city.
Covered · Step-by-step verification using a full tour example, deriving bounds for u variables and showing feasible integer assignments.
Covered · Setup and logical derivation for a subtour configuration, demonstrating how cyclic edges lead to contradictory inequalities.
Covered · Verification example on the subtour-breaking constraint, including the graph, assigned u-values, contradiction, and interpretation.
Covered · Full Formulation-2 slide with objective, constraints, variable declarations, and spoken advantages/disadvantages.
Covered · Closing exercise prompt asking to solve Formulation-2 with Cplex using data from earlier examples; no solution is shown in this clip.
Covered · Opening slide introduces solving TSP Formulation-2 with Cplex and contrasts it with branch and bound.
Covered · Second slide explains two ways to improve TSP branch and bound: tighter lower bounds via the assignment problem approach and tighter upper bounds via heuristics or metaheuristics.
Reviewed subject paths
Continue with related videos in the same subject.
YouTube5:07
YouTube4:58
YouTube4:44