Mathematical modeling / English

Assignment problem by branch and bound method

Lets Try · YouTube · 10:31

Selected moment · 8:04 · Chapter markers are time references, not playback progress.

IN THIS VIDEO

01Assignment problem objective
02Branch and bound as the solution method
03Lower bound idea

FROM THE LEARNING NOTES

\begin{pmatrix} 9 & 2 & 7 & 8 \\ 6 & 4 & 3 & 7 \\ 5 & 8 & 1 & 8 \\ 7 & 6 & 2 & 4 \end{pmatrix}

4x4 cost matrix example

SELECTED MOMENT

Selecting Next Node and Evaluating Leaves

SUGGESTED PREPARATION

Basic idea of a cost table or matrix
Elementary minimization language
Familiarity with matching people to tasks
Assignment problem formulation
Cost matrix interpretation
Basic branch-and-bound search trees
Minimization lower bounds
Understanding of matrices
Basic knowledge of optimization problems
Familiarity with tree data structures
Linear Algebra (Matrices)
Discrete Mathematics (Graph Theory/Trees)
Optimization Concepts
Assignment problem basics
Minimization bounds: lower bound and upper bound
Search-tree representation of partial assignments

READ & KEEP

The explanation, unpacked.

Saves 0

Reviewed learning material · Video analysis · English

Read the full overview

This 631-second whiteboard video solves a four-person, four-job assignment problem by branch and bound. The original cost matrix has row minima 2,3,1,2, giving a valid root lower bound 8. Branching on person a gives bounds 18,12,20,17; the $a=2$ branch gives bounds 13,14,15 for $b=1$ ,3,4. The two leaves under $a=2$ , $b=1$ cost 13 and 18. Thus $a=2$ , $b=1$ , $c=3$ , $d=4$ is optimal with cost 13. Some earlier automated notes misread the matrix entry c-to-job-4 as 3; the source shows 8.

Use the learning inspector for key ideas and moments, or open the reading tabs for the complete notes.

Chapters

0:00Topic introduction: assignment problem and branch and bound 0:10What the assignment problem asks for 0:44Meaning of the lower bound 1:03Example cost matrix with persons and jobs 1:46Computing LB from row minima 2:30Root node and second-level branching 3:20Rule for child-node lower bounds 3:38Worked bound for

a = 1

4:25Worked bound for

a = 2

4:52Start of bound for

a = 3

5:00Introduction to Branch and Bound for Assignment Problems 5:15Calculating Lower Bounds for Initial Branches 5:45Selecting the Most Promising Branch and Expanding the Tree 6:30Calculating Lower Bounds for Second-Level Branches 7:30Problem Setup and Initial Lower Bound 7:48Exploring Branches for Person B 8:04Selecting Next Node and Evaluating Leaves 9:45Conclusion: Optimal Assignment 10:00Feasible leaf assignment and upper bound 10:08Combining LB = 8 and UB = 13 into the optimal range 10:21Summary: branch and bound for the assignment problem

Learning script

Generated from the video's visuals and explanation; not verbatim speech.

The clip opens on a handwritten title page reading ASSIGNMENT PROBLEM and BRANCH AND BOUND METHOD. The speaker frames the lesson as a demonstration of how to solve an assignment problem using branch and bound.

The narrator explains the problem setting in words: there are persons and jobs, each person should receive a job, and the aim is to choose assignments so that the total cost is as small as possible. This establishes the optimization objective before any matrix is shown.

The next idea introduced is the lower bound. Informally, the speaker describes it as a value associated with the least possible cost, signaling that branch and bound will begin by estimating a floor on the total assignment cost rather than immediately enumerating all assignments.

A concrete 4x4 cost matrix appears. Rows are labeled a, b, c, d for persons and columns 1, 2, 3, 4 for jobs. The entries are costs for each person-job pair, so the example turns the abstract assignment problem into a table from which one choice per row and column must eventually be made.

Before doing the arithmetic, the speaker names the next stage of the method: after the initial bound is found, the search will continue through a state space tree. That tree is mentioned but not constructed within this excerpt.

The lower-bound computation is then carried out directly on the matrix. For each row, the smallest entry is selected: row a contributes 2, row b contributes 3, row c contributes 1, and row d contributes 2.

These four minima are summed in a boxed line, LB = $2 + 3 + 1 + 2 = 8$ . The circled 8 is presented as the initial lower bound for the example, giving a numerical floor for the total cost before branching begins.

The board shows an assignment problem solved by the branch-and-bound method. A 4x4 cost matrix is written with persons a,b,c,d as rows and jobs 1,2,3,4 as columns. Below it, the root node of the search tree is labeled $LB = 2+3+1+2 = 8$ .

The presenter now constructs the second level of the state-space tree by branching on the job assigned to person a. Four child nodes are drawn and labeled $a=1$ , $a=2$ , $a=3$ , and $a=4$ .

For each child node, the task is to estimate the best possible completion cost once that assignment is fixed. The rule used in the video is: add the fixed cost for person a, then for every remaining job take the minimum entry in that column among the rows not yet assigned.

For the branch $a=1$ , the fixed cost is the matrix entry in row a, column 1, namely $9$ . Since row a is already used, the remaining minima are taken from rows b, c, and d only.

In column 2, the entries in rows b,c,d are $4,8,6$ , so the minimum is $4$ . In column 3, the entries in rows b,c,d are $3,1,2$ , so the minimum is $1$ . In column 4, the entries in rows b,c,d are $7,8,4$ , so the minimum is $4$ .

Adding these contributions gives the child-node lower bound $9+4+1+4=18$ , which is written beneath the node $a=1$ .

For the branch $a=2$ , the fixed cost is the entry in row a, column 2, namely $2$ . Again, row a is excluded when choosing minima for the remaining columns.

In column 1, the entries in rows b,c,d are $6,5,7$ , so the minimum is $5$ . In column 3, the minimum among rows b,c,d is $1$ . In column 4, the minimum among rows b,c,d is $4$ .

Therefore the lower bound for node $a=2$ is $2+5+1+4=12$ , and this value is written under that branch.

The presenter then says the same procedure will be repeated for $a=3$ and $a=4$ , and begins the $a=3$ case by noting the fixed cost $7$ , but the clip ends before that calculation is completed.

The video begins by calculating the lower bound for the branch where person 'a' is assigned to job '3'. The fixed cost is 7. The minimum costs from the remaining columns (1, 2, and 4), excluding row 'a', are 5, 4, and 4 respectively. Summing these gives a lower bound of $7 + 5 + 4 + 4 = 20$ .

Next, the lower bound for the branch ' $a=4$ ' is calculated. The fixed cost is 8. The minimum costs from the remaining columns (1, 2, and 3), excluding row 'a', are 5, 4, and 1. The total lower bound is $8 + 5 + 4 + 1 = 17$ .

Comparing the lower bounds of all four initial branches (18, 12, 20, 17), the algorithm selects the most promising one, which is ' $a=2$ ' with a lower bound of 12. This means person 'a' is tentatively assigned to job '2'.

The search tree is then expanded from the ' $a=2$ ' node. The next level of branching will consider assignments for person 'b'. Since job '2' is already taken by 'a', person 'b' can only be assigned to jobs '1', '3', or '4'. These three new branches are drawn.

To calculate the lower bound for the new branches, the row for person 'a' and the column for job '2' are effectively removed from consideration. The video demonstrates this by pointing to the relevant parts of the cost matrix.

Under $a=2$ , $b=1$ , fixed costs are 2 and 6; the remaining jobs 3 and 4 have minima 1 and 4 among c and d. The written bound $2+6+1+4=13$ is valid.

The video starts calculating the lower bound for the branch ' $b=3$ ' (under ' $a=2$ '). The fixed cost for this assignment is 3. It then looks for the minimum in the first column, finding 5. The calculation is interrupted before completion.

The video begins by evaluating a node in the branch and bound tree where person 'a' is assigned job '2'. The speaker calculates a lower bound, stating 'the second one is two plus the minimum of fourth one is four', arriving at a value of 14. However, the written calculation on the board for this node (labeled $b=3$ ) shows ' $3+5+2+4=14$ ', which does not align perfectly with the spoken numbers or the matrix values.

Next, the speaker evaluates the branch where person 'b' is assigned job '4' (under the main branch $a=2$ ). They sum the cost of b->4 (which is 7) with the minimums of the remaining columns for persons c and d: 5 for job 1, 2 for job 3, and 1 for job 3 (wait, job 3 min is 1, job 1 min is 5). The speaker says 'seven plus the minimum... is five... two... one', resulting in 15. The board shows ' $7+5+2+1=15$ '.

The algorithm then selects the most promising branch. Comparing the lower bounds of the children of node ' $a=2$ ' (which are 13, 14, and 15), the speaker chooses the node with the lowest bound, 13, corresponding to the assignment ' $b=1$ '. This means person 'a' takes job '2' and person 'b' takes job '1'.

With persons 'a' and 'b' assigned, only 'c' and 'd' remain for jobs '3' and '4'. The speaker identifies two possible complete assignments (leaves in the tree): either c takes job 3 and d takes job 4, or c takes job 4 and d takes job 3.

The speaker calculates the total cost for the first leaf: a->2 (cost 2), b->1 (cost 6), c->3 (cost 1), d->4 (cost 4). Summing these gives $2 + 6 + 1 + 4 = 13$ . This matches the written calculation on the board.

The second leaf assigns $a=2$ , $b=1$ , $c=4$ , $d=3$ . Reading c-to-job-4 as 8 gives $2+6+8+2=18$ , matching the board.

The two leaves cost 13 and 18. Since all competing branches have lower bounds above 13, $a=2$ , $b=1$ , $c=3$ , $d=4$ is globally optimal with cost 13.

The video is focused on a handwritten branch-and-bound tree for an assignment problem with variables a, b, c, d. At the highlighted leaf, the complete assignment is $a=2$ , $b=1$ , $c=3$ , $d=4$ . Under that box, the total cost is written as $2+6+1+4=13$ , and the number 13 is marked as UB, meaning an upper bound.

The speaker then relates this feasible cost to the root lower bound already shown at the top of the tree, LB = $2+3+1+2 = 8$ . From these two displayed quantities, the explanation concludes that the optimal assignment cost must lie between 8 and 13.

This interval is presented as the result of the worked example: the lower bound gives a floor of 8, while the feasible assignment supplies a ceiling of 13. The narration describes this as giving the optimal solution range and the optimal cost information for the problem instance on the page.

The clip closes by summarizing the method itself: the assignment problem is being solved by branch and bound, using a search tree over partial assignments, node cost totals, and comparison of lower and upper bounds. The full cost matrix is not visible in this excerpt, so the arithmetic shown on the page is the direct evidence available here.

Knowledge cards

Assignment problem objective

The video defines the assignment problem as matching persons to jobs so that every person gets a particular job and the total cost is minimized. This is the optimization target that branch and bound will attack.

Branch and bound as the solution method

Branch and bound is introduced as the method for solving the assignment problem. In this excerpt, the first step emphasized is computing an initial lower bound before exploring a state space tree.

Lower bound idea

The lower bound is described informally as a value tied to the least possible cost. It serves as an initial estimate that helps guide the branch-and-bound search.

4x4 cost matrix example

The worked example uses four persons (rows a, b, c, d) and four jobs (columns 1, 2, 3, 4). Each matrix entry is the cost of assigning that person to that job.

\begin{pmatrix} 9 & 2 & 7 & 8 \\ 6 & 4 & 3 & 7 \\ 5 & 8 & 1 & 8 \\ 7 & 6 & 2 & 4 \end{pmatrix}

Initial lower bound from row minima

To compute the starting bound in this lesson, take the minimum entry in each row and add them. For the displayed matrix, the row minima are 2, 3, 1, and 2.

LB = 2 + 3 + 1 + 2 = 8

State space tree comes next

After the lower bound is found, the speaker says the remaining branch-and-bound procedure will be carried out through a state space tree. The tree itself is not shown in this clip.

Caution: lower bound is not yet a proved optimum

The spoken wording can make 8 sound like the final optimal cost, but the excerpt only demonstrates the initial lower-bound calculation. A full branching verification is not completed here.

Branch-and-bound setup for the assignment problem

The example uses a 4x4 cost matrix with persons a,b,c,d and jobs 1,2,3,4. The root node of the state-space tree carries the lower bound $LB = 2+3+1+2 = 8$ . The next step is to branch on the assignment of person a.

Second level of the state-space tree

Branching on person a produces four child nodes, one for each possible job: $a=1$ , $a=2$ , $a=3$ , and $a=4$ . These nodes represent subproblems in which that assignment is fixed.

a=1,\ a=2,\ a=3,\ a=4

How to compute a child-node lower bound

At a child node, first take the cost of the fixed assignment. Then, for each remaining job, take the minimum cost among the rows corresponding to unassigned persons. Sum these terms to get the node's lower bound.

Lower bound for branch $a = 1$

With $a=1$ , the fixed cost is $9$ . Excluding row a, the minima in columns 2, 3, and 4 are $4$ , $1$ , and $4$ . Hence the lower bound is $9+4+1+4=18$ .

9+4+1+4=18

Why the assigned row is excluded

Once person a has been assigned to a job, that person cannot be reused in the remaining assignments. Therefore the minima for the other columns must be taken only from the unassigned rows, not from row a.

Lower bound for branch $a = 2$

With $a=2$ , the fixed cost is $2$ . Excluding row a, the minima in columns 1, 3, and 4 are $5$ , $1$ , and $4$ . Hence the lower bound is $2+5+1+4=12$ .

2+5+1+4=12

Branch and Bound Method

A systematic algorithm for solving optimization problems like the assignment problem. It works by dividing the problem into smaller subproblems (branching) and estimating the best possible solution for each subproblem (bounding) to prune unpromising paths from the search tree.

Lower Bound Calculation

In the context of the assignment problem, the lower bound for a partial assignment is the sum of the costs of the already made assignments plus the sum of the minimum remaining costs in each unassigned column, considering only the rows of unassigned persons.

LB = \sum_{\text{fixed } i} C_{i, j_i} + \sum_{\text{unassigned } k} \min_{j \in \text{available}} C_{k, j}

Search Tree Expansion

The process of creating new nodes in the branch and bound tree. After selecting the most promising node (lowest bound), new child nodes are created by assigning the next unassigned person to each of the still-available jobs.

Common Pitfall: Incorrect LB Calculation

A frequent mistake is to incorrectly sum the fixed costs and the global column minimums, rather than the sum of fixed costs and the restricted column minimums (excluding already assigned rows). Always ensure that the minimums are taken only from the rows and columns that are still available for assignment.

Assignment Problem Cost Matrix

The problem involves assigning 4 jobs to 4 persons (a, b, c, d) to minimize total cost. The costs are given in a 4x4 matrix where rows are persons and columns are jobs.

\begin{bmatrix} 9 & 2 & 7 & 8 \\ 6 & 4 & 3 & 7 \\ 5 & 8 & 1 & 3 \\ 7 & 6 & 2 & 4 \end{bmatrix}

Branch and Bound Method

A systematic approach to solve optimization problems. It explores a state space tree, calculating a 'lower bound' (LB) for partial assignments. Branches with LBs higher than the best known solution are pruned.

Lower Bound Calculation

At any node in the tree, the LB is the sum of the costs of already fixed assignments plus the minimum possible costs for the remaining unassigned jobs (considering only available persons).

LB = \sum C_{fixed} + \sum \min(C_{remaining\_jobs})

Optimal Solution Identification

The leaf $a=2$ , $b=1$ , $c=3$ , $d=4$ costs $2+6+1+4=13$ ; the alternative leaf under the same branch costs $2+6+8+2=18$ . Other branch lower bounds exceed 13, so the first leaf is optimal.

Branch-and-bound tree for an assignment problem

The page shows a search tree over assignments of four variables a, b, c, d. Each branch fixes one variable, and nodes carry handwritten cost totals. The method compares these totals against bounds to narrow down the optimal assignment.

Root lower bound LB = 8

At the top of the tree, the lower bound is written explicitly as LB = $2 + 3 + 1 + 2 = 8$ . In the spoken summary, 8 is identified as the lower bound for the assignment cost.

LB = 2 + 3 + 1 + 2 = 8

Feasible assignment giving UB = 13

One leaf of the tree gives the complete assignment $a=2$ , $b=1$ , $c=3$ , $d=4$ . Its total cost is computed as $2+6+1+4=13$ , and this value is labeled UB, an upper bound on the optimum.

a=2,\ b=1,\ c=3,\ d=4,\quad 2+6+1+4=13\ (UB)

Detailed learning notes

Explore conditions, steps and evidence. Supplementary explanations are labeled separately from content shown in the video.

Symbols · 23

LB

Clear evidence

Shown in the video

Evidence

Formula
Observation
The presenter writes the boxed expression LB = $2 + 3 + 1 + 2 = 8$ .
Audio
Observation
The speaker says this gives the lower bound value, that is the eight.

Symbol

Meaning

Lower bound of the total assignment cost for the given cost matrix.

Domain

Nonnegative integer cost value derived from row minima in the example.

a, b, c, d

Clear evidence

Shown in the video

Evidence

Diagram
Observation
A 4x4 table has row labels a, b, c, d on the left.
Audio
Observation
The speaker identifies these as the persons.

Symbol

a, b, c, d

Meaning

Row labels representing the four persons in the assignment example.

Domain

Set of four persons.

1, 2, 3, 4

Clear evidence

Shown in the video

Evidence

Diagram
Observation
The same 4x4 table has column labels 1, 2, 3, 4 across the top.
Audio
Observation
The speaker identifies these as the jobs.

Symbol

1, 2, 3, 4

Meaning

Column labels representing the four jobs in the assignment example.

Domain

Set of four jobs.

cost matrix

Clear evidence

Shown in the video

Evidence

Diagram
Observation
The visible matrix entries are row a: 9, 2, 7, 8; row b: 6, 4, 3, 7; row c: 5, 8, 1, 8; row d: 7, 6, 2, 4.
Audio
Observation
The speaker refers to it as the cost matrix.

Symbol

cost matrix

Meaning

A 4x4 table whose entry in row i and column j gives the cost of assigning person i to job j.

Domain

Finite integer-valued matrix indexed by persons and jobs.

Cost matrix entries

Clear evidence

Shown in the video

Evidence

Diagram
Observation
A 4x4 handwritten cost matrix is shown with rows labeled a, b, c, d and columns labeled 1, 2, 3, 4.
Audio
Observation
The speaker refers to the rows as persons and the columns as jobs.

Symbol

Cost matrix entries

Meaning

Assignment costs between persons a,b,c,d and jobs 1,2,3,4.

Domain

Positive integers in the displayed table.

LB

Clear evidence

Shown in the video

Evidence

Formula
Observation
The root node is written as LB = $2+3+1+2 = 8$ .
Audio
Observation
The speaker discusses lower bounds while constructing the state space tree.

Symbol

Meaning

Lower bound at a node of the branch-and-bound search tree.

Domain

Integer-valued bound used for minimization.

$a = j$

Clear evidence

Shown in the video

Evidence

Formula
Observation
Child nodes are written as $a = 1$ , $a = 2$ , $a = 3$ , $a = 4$ .
Audio
Observation
The speaker says they will take the A row, that is person one, and make four blocks for A equals 1, 2, 3, and 4.

Symbol

$a = j$

Meaning

Branch label stating that person a is assigned to job j.

Domain

$j \in {1,2,3,4}$ .

a

Clear evidence

Shown in the video

Evidence

Diagram
Observation
The cost matrix has rows labeled a, b, c, d.
Audio
Observation
The speaker refers to assigning person A the job 2.

Symbol

Meaning

Person a (or A) in the assignment problem.

Domain

Set of persons {a, b, c, d}.

b

Clear evidence

Shown in the video

Evidence

Diagram
Observation
The cost matrix has rows labeled a, b, c, d.
Audio
Observation
The speaker discusses finding assignments for persons b, c, and d.

Symbol

Meaning

Person b in the assignment problem.

Domain

Set of persons {a, b, c, d}.

c

Clear evidence

Shown in the video

Evidence

Diagram
Observation
The cost matrix has rows labeled a, b, c, d.
Audio
Observation
The speaker discusses finding assignments for persons b, c, and d.

Symbol

Meaning

Person c in the assignment problem.

Domain

Set of persons {a, b, c, d}.

d

Clear evidence

Shown in the video

Evidence

Diagram
Observation
The cost matrix has rows labeled a, b, c, d.
Audio
Observation
The speaker discusses finding assignments for persons b, c, and d.

Symbol

Meaning

Person d in the assignment problem.

Domain

Set of persons {a, b, c, d}.

1, 2, 3, 4

Clear evidence

Shown in the video

Evidence

Diagram
Observation
The cost matrix has columns labeled 1, 2, 3, 4 under the heading 'Jobs ->'.

Symbol

1, 2, 3, 4

Meaning

Job indices or columns in the cost matrix.

Domain

Set of jobs {1, 2, 3, 4}.

Knowledge points · 16

Assignment problem objective

Clear evidence

Shown in the video

Evidence

Audio
Observation
The speaker says that in the assignment problem we need to assign some job to some person, at least one job per person, and then check that the cost should be the lowest.
Audio
Observation
The speaker adds that we have to generate an optimized solution, that is an optimized assignment to the jobs.

Definition

Explanation

The video defines the assignment problem operationally: each person is assigned a particular job, and among all such assignments one seeks the solution with the least total cost. The spoken wording emphasizes one-to-one assignment in the example, although the general verbal setup first mentions that there can be any number of jobs and at least one job per person.

Formula

Conditions

There are persons and jobs to be matched.
Each person receives a particular job in the worked example.
The goal is to minimize total cost.

Branch and bound applied to assignment problems

Clear evidence

Shown in the video

Evidence

Caption evidence
Observation
The page title reads ASSIGNMENT PROBLEM and BRANCH AND BOUND METHOD.
Audio
Observation
The speaker says this video will show how to solve the assignment problem by using the branch and bound method.

Method

Explanation

The clip introduces branch and bound as the solution method for the assignment problem. In this excerpt, only the opening idea is stated: the method begins by finding a lower bound before proceeding further through a state space tree.

Formula

Conditions

The problem under discussion is an assignment problem.

Prerequisites

Assignment problem objective

Lower bound as a least-cost estimate

Clear evidence

Shown in the video

Evidence

Audio
Observation
The speaker says, at first we will check and find out the lowest lower bound, that is the lower bound is a solution that gives us the least cost.

Uncertainties

The phrase 'lowest lower bound' is spoken imprecisely; the worked example treats LB as a single lower-bound estimate obtained from row minima.

Definition

Explanation

In the video's informal explanation, the lower bound is described as a value associated with the least possible cost. The later computation shows that this lower bound is obtained by summing the minimum entry in each row of the cost matrix.

Formula

Conditions

A cost matrix is available.
The method is being used to estimate a minimum achievable total cost.

Prerequisites

Assignment problem objective

Computing the initial lower bound from row minima

Clear evidence

Shown in the video

Evidence

Audio
Observation
The speaker says the lower bound is obtained by getting the minimum value of each of these.
Formula
Observation
The written calculation is LB = $2 + 3 + 1 + 2 = 8$ .
Diagram
Observation
The pen points successively to the row minima 2, 3, 1, and 2 in rows a, b, c, and d.

Method

Explanation

For the displayed 4x4 cost matrix, the video computes the initial lower bound by taking the minimum element in each row and adding those four minima. This produces a quick admissible estimate of the minimum total assignment cost before branching begins.

Formula

LB = 2 + 3 + 1 + 2 = 8

Conditions

The matrix is organized with persons as rows and jobs as columns.
The demonstrated rule uses row minima only.

Prerequisites

Lower bound as a least-cost estimate
Worked 4x4 assignment cost matrix

Worked 4x4 assignment cost matrix

Clear evidence

Shown in the video

Evidence

Diagram
Observation
A handwritten 4x4 matrix appears with row labels a, b, c, d and column labels 1, 2, 3, 4.
Audio
Observation
The speaker says there are four persons and four jobs and that the cost given here should be the least.

Definition

Explanation

The example instantiates the assignment problem with four persons and four jobs. The matrix entries are costs for assigning each person to each job, and the task is to choose one entry from each row and column so that the total cost is minimized.

Formula

\begin{pmatrix} 9 & 2 & 7 & 8 \\ 6 & 4 & 3 & 7 \\ 5 & 8 & 1 & 8 \\ 7 & 6 & 2 & 4 \end{pmatrix}

Conditions

Rows correspond to persons a, b, c, d.
Columns correspond to jobs 1, 2, 3, 4.
Entries are nonnegative integer costs.

Prerequisites

Assignment problem objective

State space tree as the next stage

Clear evidence

Shown in the video

Evidence

Audio
Observation
The speaker says the further procedure will be done through the state space tree.

Uncertainties

No state space tree is actually drawn or explained within this 150-second excerpt.

Method

Explanation

After introducing the lower-bound step, the speaker states that the rest of the branch-and-bound procedure will proceed through a state space tree. The clip ends before that tree is constructed or analyzed.

Formula

Conditions

An initial lower bound has been computed.

Prerequisites

Branch and bound applied to assignment problems
Computing the initial lower bound from row minima

Branching on the first assignment variable

Clear evidence

Shown in the video

Evidence

Audio
Observation
The speaker says, 'State space tree second level' and then explains taking the A row/person one and making four blocks.
Diagram
Observation
A root box labeled LB = $2+3+1+2 = 8$ is expanded into four child boxes labeled $a = 1$ , $a = 2$ , $a = 3$ , $a = 4$ .

Method

Explanation

In this assignment-problem example, the next level of the state-space tree is formed by fixing the job assigned to person a. The root lower-bound node is branched into four children corresponding to $a = 1$ , $a = 2$ , $a = 3$ , and $a = 4$ .

Formula

Conditions

The problem is an assignment problem with four persons and four jobs.
Branching is done by assigning one job to the selected person.

Lower bound at a child node after fixing one assignment

Clear evidence

Shown in the video

Evidence

Audio
Observation
The speaker says they need to find out the lowest cost for assignments of 1, 2, 3, and 4 to person A.
Formula
Observation
Under $a = 1$ the expression $9+4+1+4 = 18$ is written; under $a = 2$ the expression $2+5+1+4 = 12$ is written.

Method

Explanation

For each child node, the lower bound is computed by adding the fixed assignment cost for person a and then, for each remaining job, taking the minimum cost among the unassigned persons. The video demonstrates this rule explicitly for $a = 1$ and $a = 2$ .

Formula

Conditions

One assignment has been fixed at the current node.
Remaining jobs are evaluated using minima over rows not already assigned.

Prerequisites

Branching on the first assignment variable

Branch and Bound Method for Assignment Problem

Clear evidence

Shown in the video

Evidence

Diagram
Observation
The title on the paper reads 'ASSIGNMENT PROBLEM BRANCH AND BOUND METHOD'.
Animation
Observation
The video shows a search tree being drawn and expanded step-by-step.

Method

Explanation

A systematic approach to solving the assignment problem by exploring a search tree of partial assignments. At each node, a lower bound on the cost of any complete assignment extending the partial one is calculated. The algorithm selects the most promising node (usually the one with the lowest bound) to expand next.

Formula

Conditions

Applicable to combinatorial optimization problems like the assignment problem.
Requires a method to calculate a valid lower bound for partial assignments.

Lower Bound Calculation

Clear evidence

Shown in the video

Evidence

Diagram
Observation
Calculations like 'LB = $2+3+1+2 = 8$ ' and ' $9+4+1+4 = 18$ ' are shown at tree nodes.
Audio
Observation
The speaker explains how to find the minimum values from the remaining columns after fixing an assignment.

Formula

Explanation

For a given partial assignment, the lower bound is calculated by summing the fixed assignment costs and the minimum remaining costs from the unassigned rows and available columns.

Formula

LB = \sum_{\text{fixed } i} C_{i, j_i} + \sum_{\text{unassigned } k} \min_{j \in \text{available}} C_{k, j}

Conditions

The set of available columns must exclude columns already assigned to fixed rows.
The set of unassigned rows must exclude rows that have been fixed.

Prerequisites

Branch and Bound Method for Assignment Problem

Cost Matrix for Assignment Problem

Clear evidence

Shown in the video

Evidence

Diagram
Observation
A 4x4 cost matrix is drawn with rows a, b, c, d and columns 1, 2, 3, 4.

Definition

Explanation

The problem is defined by a 4x4 matrix where rows represent persons (a, b, c, d) and columns represent jobs (1, 2, 3, 4). The entry in each cell represents the cost of assigning that specific job to that specific person.

Formula

\begin{bmatrix} 9 & 2 & 7 & 8 \\ 6 & 4 & 3 & 7 \\ 5 & 8 & 1 & 3 \\ 7 & 6 & 2 & 4 \end{bmatrix}

Conditions

Each person must be assigned exactly one job.
Each job must be assigned to exactly one person.

Branch and Bound State Space Tree

Clear evidence

Shown in the video

Evidence

Diagram
Observation
A state space tree is drawn below the matrix, branching out from a root node labeled 'LB = $2+3+1+2 = 8$ '.

Method

Explanation

The solution is explored using a state space tree. The root node calculates an initial lower bound by summing the minimum cost of each column. Subsequent nodes branch by fixing an assignment for a person to a specific job, and new lower bounds are calculated for the remaining unassigned jobs.

Formula

Conditions

Used to systematically explore the solution space of the assignment problem.
Prunes branches whose lower bound exceeds the best known feasible solution.

Prerequisites

Cost Matrix for Assignment Problem

Claims and conditions · 3

Initial lower bound for the example equals 8

Clear evidence

Shown in the video

Evidence

Formula
Observation
The boxed result reads LB = $2 + 3 + 1 + 2 = 8$ .
Audio
Observation
The speaker says this gives the lower bound value, that is the eight, and that the total cost of this assignment will have lowest value eight.

Uncertainties

The spoken conclusion is stronger than what the displayed computation alone proves; the video presents 8 as the lower bound from row minima, not as a completed proof of optimality.

Proposition

Statement

For the displayed 4x4 cost matrix, the initial lower bound computed by summing the row minima is 8.

Hypotheses

The matrix entries are as shown.
Rows represent persons and columns represent jobs.
The lower bound is computed by adding the minimum entry in each row.

Quantifiers

For the specific worked example matrix shown in the video.

Branch and bound can solve the assignment problem

Clear evidence

Shown in the video

Evidence

Audio
Observation
“So this is how we find out the assignment and we solve the assignment problem by using the branch and bound method.”

Proposition

Statement

The assignment problem instance shown is solved by applying the branch and bound method to a search tree of partial assignments and cost bounds.

Hypotheses

An assignment problem with variables a, b, c, d is given.
A branch-and-bound tree is constructed over feasible assignments.
Node costs and bounds are computed as shown.

Quantifiers

For the worked example displayed in the clip.

The optimal cost is between the displayed lower and upper bounds

Clear evidence

Shown in the video

Evidence

Audio
Observation
“the cost value will be between eight that is the lower bound and between thirteen.”
Formula
Observation
Visible values LB = 8 and UB = 13.

Uncertainties

The clip does not restate the general theorem behind bounding; it applies the idea to this example.

Proposition

Statement

For the example in the clip, the optimal assignment cost lies between the lower bound 8 and the upper bound 13.

Hypotheses

LB = 8 is valid for the problem.
UB = 13 comes from a feasible complete assignment.

Quantifiers

For the specific assignment problem instance shown.

Derivations and proofs · 18

Derivation of the initial lower bound from the cost matrix

Clear evidence

Shown in the video

Evidence

Audio
Observation
The speaker explains that the lower bound is found by getting the minimum value of each of these.
Diagram
Observation
The pen indicates the minimum in each row: 2 in row a, 3 in row b, 1 in row c, and 2 in row d.
Formula
Observation
The written line becomes LB = $2 + 3 + 1 + 2 = 8$ .

Numerical verification

Steps

Expression
$\min(9,2,7,8)=2$
Explanation
From row a, the smallest cost is 2.
Justification
Direct inspection of the first row of the displayed matrix.
Shown in the video
Expression
$\min(6,4,3,7)=3$
Explanation
From row b, the smallest cost is 3.
Justification
Direct inspection of the second row of the displayed matrix.
Shown in the video
Expression
$\min(5,8,1,8)=1$
Explanation
From row c, the smallest cost is 1.
Justification
Direct inspection of the third row of the displayed matrix.
Shown in the video
Expression
$\min(7,6,2,4)=2$
Explanation
From row d, the smallest cost is 2.
Justification
Direct inspection of the fourth row of the displayed matrix.
Shown in the video
Expression
$LB = 2 + 3 + 1 + 2 = 8$
Explanation
The four row minima are added to obtain the initial lower bound.
Justification
The video states that the lower bound is obtained by taking the minimum value of each row and then writing their sum.
Shown in the video

Conclusion

The initial lower bound for the example is 8.

Derivation of the lower bound for branch $a = 1$

Clear evidence

Shown in the video

Evidence

Audio
Observation
The speaker says: 'So for the A1 ... we will write nine here. Nine plus ... for the second one we have to write the minimum value that is four except this ... Next is one. Then four.'
Formula
Observation
The written line under $a = 1$ is $9+4+1+4 = 18$ .
Diagram
Observation
The pen points to entry (a,1)=9, then to column minima among rows b,c,d: 4 in column 2, 1 in column 3, and 4 in column 4.

Numerical verification

Steps

Expression
$9$
Explanation
Take the fixed assignment cost for person a to job 1 from the matrix.
Justification
This is the cost of the chosen branch $a = 1$ .
Shown in the video
Expression
$4$
Explanation
For job 2, take the minimum cost among the remaining persons b, c, d.
Justification
Row a is excluded because person a is already assigned; the visible column-2 entries in rows b,c,d are 4,8,6, so the minimum is 4.
Shown in the video
Expression
$1$
Explanation
For job 3, take the minimum cost among the remaining persons b, c, d.
Justification
The visible column-3 entries in rows b,c,d are 3,1,2, so the minimum is 1.
Shown in the video
Expression
$4$
Explanation
For job 4, take the minimum cost among the remaining persons b, c, d.
Justification
The visible column-4 entries in rows b,c,d are 7,8,4, so the minimum is 4.
Shown in the video
Expression
$9+4+1+4=18$
Explanation
Add the fixed cost and the three remaining-column minima to obtain the node lower bound.
Justification
This is the summation shown on the page and spoken by the presenter.
Shown in the video

Conclusion

The lower bound at node $a = 1$ is 18.

Derivation of the lower bound for branch $a = 2$

Clear evidence

Shown in the video

Evidence

Audio
Observation
The speaker says: 'Now for the A is equals to two value ... Now we will search for the minimum value in the first except the first row that is the A. So the minimum value is five. Plus the minimum of this is one, minimum of this is four. This gives us the value twelve.'
Formula
Observation
The written line under $a = 2$ is $2+5+1+4 = 12$ .
Diagram
Observation
The pen points to entry (a,2)=2, then to column minima among rows b,c,d: 5 in column 1, 1 in column 3, and 4 in column 4.

Numerical verification

Steps

Expression
$2$
Explanation
Take the fixed assignment cost for person a to job 2 from the matrix.
Justification
This is the cost of the chosen branch $a = 2$ .
Shown in the video
Expression
$5$
Explanation
For job 1, take the minimum cost among the remaining persons b, c, d.
Justification
The visible column-1 entries in rows b,c,d are 6,5,7, so the minimum is 5.
Shown in the video
Expression
$1$
Explanation
For job 3, take the minimum cost among the remaining persons b, c, d.
Justification
The visible column-3 entries in rows b,c,d are 3,1,2, so the minimum is 1.
Shown in the video
Expression
$4$
Explanation
For job 4, take the minimum cost among the remaining persons b, c, d.
Justification
The visible column-4 entries in rows b,c,d are 7,8,4, so the minimum is 4.
Shown in the video
Expression
$2+5+1+4=12$
Explanation
Add the fixed cost and the three remaining-column minima to obtain the node lower bound.
Justification
This is the summation shown on the page and spoken by the presenter.
Shown in the video

Conclusion

The lower bound at node $a = 2$ is 12.

Derivation of Root Lower Bound

Clear evidence

Shown in the video

Evidence

Diagram
Observation
Root node shows 'LB = $2+3+1+2 = 8$ '.
Audio
Observation
Speaker says 'minimum of first is 2, second is 3, third is 1, fourth is 2'.

Numerical verification

Steps

Expression
$\min(9, 6, 5, 7) = 5$
Explanation
Minimum cost in column 1.
Justification
Observing the first column of the cost matrix.
Derived from the video
Expression
$\min(2, 4, 8, 6) = 2$
Explanation
Minimum cost in column 2.
Justification
Observing the second column of the cost matrix.
Derived from the video
Expression
$\min(7, 3, 1, 2) = 1$
Explanation
Minimum cost in column 3.
Justification
Observing the third column of the cost matrix.
Derived from the video
Expression
$\min(8, 7, 5, 4) = 4$
Explanation
Minimum cost in column 4.
Justification
Observing the fourth column of the cost matrix.
Derived from the video

Conclusion

The video uses row minima $2+3+1+2=8$ , a valid root lower bound. Summing column minima $5+2+1+4=12$ gives another valid, tighter lower bound for this matrix.

Derivation of Lower Bound for Branch $a=1$

Clear evidence

Shown in the video

Evidence

Diagram
Observation
Node ' $a=1$ ' shows ' $9+4+1+4 = 18$ '.
Audio
Observation
Speaker says 'starts with 9... minimum of second is 4, third is 1, fourth is 4... gives us 18'.

Numerical verification

Steps

Expression
$C_{a,1} = 9$
Explanation
Fixed cost for assigning person a to job 1.
Justification
From the cost matrix.
Shown in the video
Expression
$\min(4, 8, 6) = 4$
Explanation
Minimum cost in column 2 excluding row a.
Justification
From the cost matrix, ignoring row a.
Derived from the video
Expression
$\min(3, 1, 2) = 1$
Explanation
Minimum cost in column 3 excluding row a.
Justification
From the cost matrix, ignoring row a.
Derived from the video
Expression
$\min(7, 5, 4) = 4$
Explanation
Minimum cost in column 4 excluding row a.
Justification
From the cost matrix, ignoring row a.
Derived from the video
Expression
$9 + 4 + 1 + 4 = 18$
Explanation
Summing the fixed cost and the minimum remaining costs.
Justification
Applying the lower bound formula.
Shown in the video

Conclusion

The lower bound for the branch where person a is assigned to job 1 is 18.

Derivation of Lower Bound for Branch $a=2$

Clear evidence

Shown in the video

Evidence

Diagram
Observation
Node ' $a=2$ ' shows ' $2+5+1+4 = 12$ '.
Audio
Observation
Speaker says 'starts with 2... minimum of first is 5, third is 1, fourth is 4... gives us 12'.

Numerical verification

Steps

Expression
$C_{a,2} = 2$
Explanation
Fixed cost for assigning person a to job 2.
Justification
From the cost matrix.
Shown in the video
Expression
$\min(6, 5, 7) = 5$
Explanation
Minimum cost in column 1 excluding row a.
Justification
From the cost matrix, ignoring row a.
Derived from the video
Expression
$\min(3, 1, 2) = 1$
Explanation
Minimum cost in column 3 excluding row a.
Justification
From the cost matrix, ignoring row a.
Derived from the video
Expression
$\min(7, 5, 4) = 4$
Explanation
Minimum cost in column 4 excluding row a.
Justification
From the cost matrix, ignoring row a.
Derived from the video
Expression
$2 + 5 + 1 + 4 = 12$
Explanation
Summing the fixed cost and the minimum remaining costs.
Justification
Applying the lower bound formula.
Shown in the video

Conclusion

The lower bound for the branch where person a is assigned to job 2 is 12.

Derivation of Lower Bound for Branch $a=3$

Clear evidence

Shown in the video

Evidence

Diagram
Observation
Node ' $a=3$ ' shows ' $7+5+4+4 = 20$ '.
Audio
Observation
Speaker says 'starts with 7... minimum of first is 5, second is 4, fourth is 4... gives us 20'.

Numerical verification

Steps

Expression
$C_{a,3} = 7$
Explanation
Fixed cost for assigning person a to job 3.
Justification
From the cost matrix.
Shown in the video
Expression
$\min(6, 5, 7) = 5$
Explanation
Minimum cost in column 1 excluding row a.
Justification
From the cost matrix, ignoring row a.
Derived from the video
Expression
$\min(4, 8, 6) = 4$
Explanation
Minimum cost in column 2 excluding row a.
Justification
From the cost matrix, ignoring row a.
Derived from the video
Expression
$\min(7, 5, 4) = 4$
Explanation
Minimum cost in column 4 excluding row a.
Justification
From the cost matrix, ignoring row a.
Derived from the video
Expression
$7 + 5 + 4 + 4 = 20$
Explanation
Summing the fixed cost and the minimum remaining costs.
Justification
Applying the lower bound formula.
Shown in the video

Conclusion

The lower bound for the branch where person a is assigned to job 3 is 20.

Derivation of Lower Bound for Branch $a=4$

Clear evidence

Shown in the video

Evidence

Diagram
Observation
Node ' $a=4$ ' shows ' $8+5+4+1 = 17$ '.
Audio
Observation
Speaker says 'starts with 8... minimum of first is 5, second is 4, third is 1... gives us 17'.

Numerical verification

Steps

Expression
$C_{a,4} = 8$
Explanation
Fixed cost for assigning person a to job 4.
Justification
From the cost matrix.
Shown in the video
Expression
$\min(6, 5, 7) = 5$
Explanation
Minimum cost in column 1 excluding row a.
Justification
From the cost matrix, ignoring row a.
Derived from the video
Expression
$\min(4, 8, 6) = 4$
Explanation
Minimum cost in column 2 excluding row a.
Justification
From the cost matrix, ignoring row a.
Derived from the video
Expression
$\min(3, 1, 2) = 1$
Explanation
Minimum cost in column 3 excluding row a.
Justification
From the cost matrix, ignoring row a.
Derived from the video
Expression
$8 + 5 + 4 + 1 = 17$
Explanation
Summing the fixed cost and the minimum remaining costs.
Justification
Applying the lower bound formula.
Shown in the video

Conclusion

The lower bound for the branch where person a is assigned to job 4 is 17.

Derivation of Lower Bound for Branch $b=1$ (given $a=2$ )

Clear evidence

Shown in the video

Evidence

Diagram
Observation
Node ' $b=1$ ' under ' $a=2$ ' shows ' $6+2+1+4 = 13$ '.
Audio
Observation
Speaker says 'b equals to 1 value is 6... minimum of second row is 2, third column is 1, fourth is 8... total of 13'.

Numerical verification

Steps

Expression
$C_{a,2}+C_{b,1}=2+6=8$
Explanation
Sum the two fixed assignments.
Justification
Read the original matrix.
Derived from the video
Expression
$\min(C_{c,3},C_{d,3})=\min(1,2)=1$
Explanation
Take the minimum for unassigned job 3.
Justification
Only c and d remain.
Derived from the video
Expression
$\min(C_{c,4},C_{d,4})=\min(8,4)=4$
Explanation
Take the minimum for unassigned job 4.
Justification
Only c and d remain.
Derived from the video
Expression
$LB=2+6+1+4=13$
Explanation
Fixed costs plus the two remaining-job minima.
Justification
A valid lower bound for this branch.
Shown in the video

Conclusion

The $b=1$ branch under $a=2$ has lower bound 13, matching the written source calculation.

Derivation of Lower Bound for Branch $b=3$ (given $a=2$ )

Clear evidence

Shown in the video

Evidence

Diagram
Observation
Node ' $b=3$ ' under ' $a=2$ ' shows ' $3+5$ +...'.
Audio
Observation
Speaker says 'b equals to 3 is 3... minimum of first row is 5... 3 plus 5 plus minimum of...'

Uncertainties

The calculation is incomplete in the provided clip.

Numerical verification

Steps

Expression
$C_{a,2}+C_{b,3}=2+3=5$
Explanation
Sum fixed assignments.
Justification
Original matrix.
Derived from the video
Expression
$\min(C_{c,1},C_{d,1})=\min(5,7)=5$
Explanation
Minimum for remaining job 1.
Justification
Rows c and d remain.
Derived from the video
Expression
$\min(C_{c,4},C_{d,4})=\min(8,4)=4$
Explanation
Minimum for remaining job 4.
Justification
Rows c and d remain.
Derived from the video
Expression
$LB=2+3+5+4=14$
Explanation
Compute the branch lower bound.
Justification
Fixed costs plus remaining-job minima.
Shown in the video

Conclusion

The $b=3$ branch under $a=2$ has lower bound 14.

Calculation of Root Lower Bound

Clear evidence

Shown in the video

Evidence

Diagram
Observation
Root node shows LB = $2 + 3 + 1 + 2 = 8$ .
Audio
Observation
Speaker explains taking the minimum of the columns.

Numerical verification

Steps

Expression
$\min(9, 6, 5, 7) = 5$
Explanation
Find the minimum cost in Job 1 column.
Justification
Column minimum calculation.
Derived from the video
Expression
$\min(2, 4, 8, 6) = 2$
Explanation
Find the minimum cost in Job 2 column.
Justification
Column minimum calculation.
Derived from the video
Expression
$\min(7, 3, 1, 2) = 1$
Explanation
Find the minimum cost in Job 3 column.
Justification
Column minimum calculation.
Derived from the video
Expression
$\min(8,7,8,4)=4$
Explanation
Find the minimum cost in Job 4 column.
Justification
Column minimum calculation.
Derived from the video
Expression
$LB=5+2+1+4=12$
Explanation
Sum the column minimums to get the initial lower bound.
Justification
Definition of lower bound for assignment problem.
Derived from the video

Conclusion

The source root bound 8 is the sum of row minima; this independently derived sum of column minima is 12. Both are valid lower bounds, with 12 tighter here.

Lower Bound for Node $a=2$ , $b=1$

Clear evidence

Shown in the video

Evidence

Diagram
Observation
Node ' $a=2$ ' has child ' $b=1$ ' with calculation $6 + 2 + 1 + 4 = 13$ .
Audio
Observation
Speaker says 'the value is 6... plus the minimum of fourth one is 4... gives us the value 14'.

Uncertainties

Audio says 14, but written calculation and final circled number is 13.

Numerical verification

Steps

Expression
$C_{b,1} = 6$
Explanation
Cost of assigning Job 1 to Person b.
Justification
Reading from cost matrix.
Shown in the video
Expression
$C_{a,2} = 2$
Explanation
Cost of assigning Job 2 to Person a.
Justification
Reading from cost matrix.
Shown in the video
Expression
$\min(C_{c,3}, C_{d,3}) = \min(1, 2) = 1$
Explanation
Minimum cost for remaining Job 3 among available persons c and d.
Justification
Column minimum for unassigned rows.
Derived from the video
Expression
$\min(C_{c,4},C_{d,4})=\min(8,4)=4$
Explanation
Minimum cost for remaining Job 4 among available persons c and d.
Justification
Column minimum for unassigned rows.
Derived from the video
Expression
$LB=6+2+1+4=13$
Explanation
Sum of fixed costs and remaining minimums.
Justification
Lower bound calculation method.
Derived from the video

Conclusion

The source writes $6+2+1+4=13$ , a correct lower bound after fixing $a=2$ and $b=1$ .

Worked examples · 5

Four-person, four-job assignment example

Clear evidence

Shown in the video

Evidence

Diagram
Observation
A 4x4 handwritten cost matrix with row labels a, b, c, d and column labels 1, 2, 3, 4 is shown.
Audio
Observation
The speaker says there are four persons and four jobs and that we need to assign each person a particular job with least cost.
Formula
Observation
The lower-bound calculation LB = $2 + 3 + 1 + 2 = 8$ is written below the matrix.

Uncertainties

The full optimal assignment itself is not found within this excerpt.

Problem

Given a 4x4 cost matrix for four persons and four jobs, begin solving the assignment problem by branch and bound and compute the initial lower bound.

Given

Persons: a, b, c, d.
Jobs: 1, 2, 3, 4.
Cost matrix: [[9, 2, 7, 8], [6, 4, 3, 7], [5, 8, 1, 8], [7, 6, 2, 4]].

Goal

Find the initial lower bound for the total assignment cost before proceeding to the state space tree.

Steps

Expression
$\text{Identify the minimum entry in each row.}$
Explanation
The method starts by scanning each person’s row for the cheapest available job cost.
Justification
The speaker says the lower bound is obtained by getting the minimum value of each of these.
Shown in the video
Expression
$2,\ 3,\ 1,\ 2$
Explanation
The row minima are 2 for row a, 3 for row b, 1 for row c, and 2 for row d.
Justification
These values are read directly from the displayed matrix.
Shown in the video
Expression
$LB = 2 + 3 + 1 + 2 = 8$
Explanation
Adding the four row minima gives the initial lower bound.
Justification
This is exactly the written computation shown in the box.
Shown in the video

Answer

LB = 8

Verification

The arithmetic $2 + 3 + 1 + 2 = 8$ is correct, and the selected numbers match the visible row minima of the matrix.

Second-level branching example for an assignment problem

Clear evidence

Shown in the video

Evidence

Diagram
Observation
The page title reads ASSIGNMENT PROBLEM and BRANCH AND BOUND METHOD, with a 4x4 cost matrix and a partially built state-space tree.
Audio
Observation
The speaker explains building the second level of the state space tree and computing lower bounds for branches $a = 1$ and $a = 2$ .

Uncertainties

The calculations for $a = 3$ and $a = 4$ are only begun verbally and are not completed within the clip.

Problem

Given a 4x4 assignment cost matrix with persons a,b,c,d and jobs 1,2,3,4, construct the second level of the branch-and-bound state-space tree by branching on the job assigned to person a, and compute lower bounds for the resulting child nodes.

Given

Cost matrix rows: $a=(9,2,7,8)$ , $b=(6,4,3,7)$ , $c=(5,8,1,8)$ , $d=(7,6,2,4)$ .
Root lower bound shown as LB = $2+3+1+2 = 8$ .
Branching variable is the job assigned to person a.

Goal

Create child nodes $a = 1$ , $a = 2$ , $a = 3$ , $a = 4$ and evaluate their lower bounds using the demonstrated rule.

Steps

Expression
$a=1,\ a=2,\ a=3,\ a=4$
Explanation
Branch the root into four children according to the four possible jobs for person a.
Justification
This is the construction described as the second level of the state space tree.
Shown in the video
Expression
$9+4+1+4=18$
Explanation
Compute the lower bound for node $a = 1$ .
Justification
Fixed cost $c_{a1}=9$ plus column minima over rows b,c,d for jobs 2,3,4.
Shown in the video
Expression
$2+5+1+4=12$
Explanation
Compute the lower bound for node $a = 2$ .
Justification
Fixed cost $c_{a2}=2$ plus column minima over rows b,c,d for jobs 1,3,4.
Shown in the video
Expression
$7+\cdots$
Explanation
Begin the lower-bound computation for node $a = 3$ by writing the fixed cost 7.
Justification
The speaker says 'Similarly we have to do for the A is equals to three value ... So A is equals to three value here is seven,' but the rest is not completed in the clip.
Shown in the video

Answer

Within this clip, the completed child-node bounds are: $a = 1$ gives 18, and $a = 2$ gives 12. The branches $a = 3$ and $a = 4$ are introduced but not fully evaluated before the segment ends.

Verification

The written sums on the page match the spoken arithmetic: $9+4+1+4=18$ and $2+5+1+4=12$ .

Solving a 4x4 Assignment Problem using Branch and Bound

Clear evidence

Shown in the video

Evidence

Diagram
Observation
A 4x4 cost matrix is provided, and a branch and bound tree is constructed to solve it.

Problem

Find the optimal assignment of 4 persons (a, b, c, d) to 4 jobs (1, 2, 3, 4) that minimizes the total cost, given the cost matrix.

Given

Cost matrix $C = [[9, 2, 7, 8], [6, 4, 3, 7], [5, 8, 1, 5], [7, 6, 2, 4]]$

Goal

Determine the sequence of assignments and the minimum total cost.

Steps

ExpressionCalculate root LB
Explanation
Compute the initial lower bound for the entire problem.
Justification
Standard first step in branch and bound.
Shown in the video
ExpressionBranch on person a
Explanation
Create four child nodes representing $a=1$ , $a=2$ , $a=3$ , $a=4$ .
Justification
Exploring all possible assignments for the first person.
Shown in the video
ExpressionCalculate LB for each branch of a
Explanation
For each child node, compute the lower bound given the fixed assignment for a.
Justification
To evaluate the promise of each branch.
Shown in the video
ExpressionSelect most promising branch
Explanation
Choose the branch with the lowest LB ( $a=2$ , LB=12) to expand further.
Justification
Greedy strategy to find the optimal solution efficiently.
Shown in the video
ExpressionBranch on person b
Explanation
Under the $a=2$ node, create child nodes for $b=1$ , $b=3$ , $b=4$ ( $b=2$ is excluded as job 2 is taken).
Justification
Continuing the exploration of partial assignments.
Shown in the video
ExpressionCalculate LB for branches of b
Explanation
Compute the lower bounds for the new nodes.
Justification
To guide the next selection.
Shown in the video

Answer

The video does not reach a final answer within the 150-second clip. It demonstrates the process of calculating lower bounds and expanding the search tree.

Verification

The correctness of the method relies on the lower bound being a valid underestimate of the true cost of any completion of the partial assignment.

Solving Assignment Problem via Branch and Bound

Clear evidence

Shown in the video

Evidence

Diagram
Observation
Full problem setup with matrix and tree is visible throughout.
Audio
Observation
Speaker narrates the entire process of solving the assignment problem.

Problem

Find the optimal assignment of 4 jobs to 4 persons that minimizes the total cost, given the cost matrix.

Given

Cost matrix: [[9,2,7,8],[6,4,3,7],[5,8,1,3],[7,6,2,4]]
Rows are persons a,b,c,d; columns are jobs 1,2,3,4.

Goal

Determine the assignment with the minimum total cost.

Steps

Expression
$\text{Explore branch } a=2$
Explanation
Select person 'a' to take job '2' as it offers a low cost.
Justification
Heuristic choice to start branching.
Shown in the video
Expression
$\text{Explore sub-branches } b=1, b=3, b=4$
Explanation
For the remaining persons, assign job options to 'b' and calculate lower bounds.
Justification
Systematic exploration of the state space.
Shown in the video
Expression
$\text{Select node with lowest LB } (b=1, LB=13)$
Explanation
Choose the branch with the smallest lower bound to continue exploring.
Justification
Branch and bound pruning strategy.
Shown in the video
Expression
$\text{Evaluate leaves under } b=1$
Explanation
Calculate exact total costs for the two possible complete assignments remaining.
Justification
Reaching a feasible solution requires assigning all persons.
Shown in the video
Expression
$\text{Compare leaf costs: } 13 \text{ vs } 18$
Explanation
Identify the minimum cost among the evaluated feasible solutions.
Justification
Objective is minimization.
Shown in the video

Answer

The video concludes the optimal assignment is $a=2$ , $b=1$ , $c=3$ , $d=4$ with a total cost of 13.

Verification

Independent enumeration of all 24 possible complete assignments confirms 13 is the global minimum; the tree bounds exclude every other branch.

Worked example: feasible assignment giving UB = 13

Clear evidence

Shown in the video

Evidence

Diagram
Observation
A leaf box on the handwritten tree reads “ $a = 2$ , $b = 1$ , $c = 3$ , $d = 4$ ” with “ $2 + 6 + 1 + 4 = 13$ UB” beneath it.
Audio
Observation
“B the job one, C three and D four. And it gives us the upper bound … between eight … and … thirteen.”

Uncertainties

The full original cost matrix is not visible in this clip, so only the displayed arithmetic can be verified.

Problem

From the branch-and-bound tree for an assignment problem, evaluate the complete assignment $a=2$ , $b=1$ , $c=3$ , $d=4$ and use it to bound the optimal cost.

Given

A branch-and-bound tree is drawn for an assignment problem with variables a, b, c, d.
The root lower bound is shown as LB = $2 + 3 + 1 + 2 = 8$ .
One leaf assignment is shown as $a = 2$ , $b = 1$ , $c = 3$ , $d = 4$ .
The corresponding cost sum at that leaf is written as $2 + 6 + 1 + 4 = 13$ .

Goal

Find the total cost of the displayed feasible assignment and state the resulting bound interval for the optimal cost.

Steps

Expression
$a=2,\ b=1,\ c=3,\ d=4$
Explanation
Read the complete feasible assignment from the leaf node.
Justification
Directly visible in the handwritten box.
Shown in the video
Expression
$2+6+1+4=13$
Explanation
Compute the total cost of that assignment using the costs shown under the leaf.
Justification
Explicit arithmetic written on the page.
Shown in the video
Expression
$UB=13$
Explanation
Treat this feasible total cost as an upper bound on the optimum.
Justification
The page labels the value as “UB” and the speaker calls it the upper bound.
Shown in the video
Expression
$LB=8$
Explanation
Recall the root lower bound already written at the top of the tree.
Justification
Visible formula “LB = $2 + 3 + 1 + 2 = 8$ ”.
Shown in the video
Expression
$8 \leq \text{optimal cost} \leq 13$
Explanation
Combine the lower and upper bounds to describe the range containing the optimum.
Justification
Bounding argument for a minimization problem; stated verbally in the clip.
Derived from the video

Answer

The feasible assignment (a,b,c,d)=(2,1,3,4) has cost 13, so the optimal cost is bounded by 8 ≤ optimal cost ≤ 13.

Verification

The answer matches the visible labels “LB = 8” and “13 UB” and the spoken statement that the cost lies between eight and thirteen.

Visual events · 9

Title page with topic headings

Clear evidence

Shown in the video

Evidence

Diagram
Observation
The camera stays on a white sheet with red handwritten headings ASSIGNMENT PROBLEM and BRANCH AND BOUND METHOD.

Objects

White paper
Red handwritten title ASSIGNMENT PROBLEM
Red handwritten subtitle BRANCH AND BOUND METHOD

Changes

The framing shifts slightly while the same title remains visible.

Invariants

The two red headings remain on screen throughout this interval.

Interpretation

The visual establishes the lesson topic before any numerical example is introduced.

Introduction of the cost matrix and its axes

Clear evidence

Shown in the video

Evidence

Diagram
Observation
A new sheet reveals a 4x4 matrix with row labels a, b, c, d and column labels 1, 2, 3, 4.
Animation
Observation
The presenter writes Persons near the rows and Jobs near the columns.

Objects

4x4 handwritten matrix
Row labels a, b, c, d
Column labels 1, 2, 3, 4
Handwritten labels Persons and Jobs

Changes

The matrix becomes the main focus.
Axis annotations are added to clarify that rows are persons and columns are jobs.

Invariants

The numeric entries of the matrix remain unchanged during this interval.

Interpretation

The visual converts the abstract assignment problem into a concrete cost table.

Writing and boxing the lower-bound calculation

Clear evidence

Shown in the video

Evidence

Animation
Observation
A rectangular box is drawn below the matrix.
Formula
Observation
Inside the box the presenter writes LB = $2 + 3 + 1 + 2 = 8$ and circles the final 8.
Diagram
Observation
The pen points to the row minima in the matrix while the sum is assembled.

Objects

Rectangular answer box
Expression LB = $2 + 3 + 1 + 2 = 8$
Circled final value 8

Changes

The box is drawn.
The terms 2, 3, 1, and 2 are inserted one by one.
The total 8 is written and emphasized by circling.

Invariants

The underlying cost matrix remains visible above the box.

Interpretation

The animation highlights the computational step that supplies the initial bound for branch and bound.

Expansion of the root node into four branches

Clear evidence

Shown in the video

Evidence

Animation
Observation
A hand draws lines from the root box LB = $2+3+1+2 = 8$ down to four child boxes labeled $a = 1$ , $a = 2$ , $a = 3$ , $a = 4$ .
Diagram
Observation
The cost matrix remains visible above the tree while the new nodes are added below it.

Objects

Root node box with LB = $2+3+1+2 = 8$
Four child node boxes labeled $a = 1$ , $a = 2$ , $a = 3$ , $a = 4$
Connecting branch lines

Changes

The tree grows from one root node to four child nodes.
Each child node receives a label specifying the job assigned to person a.

Invariants

The cost matrix itself does not change.
The root lower bound remains 8.

Interpretation

The visual expansion represents branching on the assignment decision for person a, creating one subproblem for each possible job.

Writing lower-bound expressions under child nodes

Clear evidence

Shown in the video

Evidence

Animation
Observation
The pen writes $9+4+1+4=18$ under node $a = 1$ and later writes $2+5+1+4=12$ under node $a = 2$ .
Diagram
Observation
While writing, the pen points to specific matrix entries used in each sum.

Objects

Expression $9+4+1+4=18$ under $a = 1$
Expression $2+5+1+4=12$ under $a = 2$
Cost matrix cells referenced by the pen

Changes

Numeric lower-bound expressions are added beneath the first two child nodes.
The pen moves between matrix entries and the written sums.

Invariants

The branching labels $a = 1$ and $a = 2$ remain unchanged.
The matrix values stay fixed.

Interpretation

The written expressions show how each child-node bound is assembled from one fixed assignment cost and three column-wise minima over the remaining rows.

Construction of the Branch and Bound Search Tree

Clear evidence

Shown in the video

Evidence

Animation
Observation
A hand draws a tree structure on paper, adding nodes and edges sequentially while writing calculations.

Objects

Cost matrix
Search tree nodes
Edges connecting nodes
Handwritten calculations

Changes

New nodes are added to the tree as branches are explored.
Lower bound values are calculated and written next to each node.
Lines are drawn to connect parent nodes to child nodes.

Invariants

The cost matrix remains unchanged throughout the clip.
The overall structure of the tree grows downwards from a single root node.

Interpretation

The visual event demonstrates the step-by-step execution of the branch and bound algorithm, showing how the search space is systematically explored and evaluated.

State Space Tree Diagram

Clear evidence

Shown in the video

Evidence

Diagram
Observation
A hierarchical tree diagram is drawn on paper, starting from a single root box and branching downwards.

Objects

Root node box
Branching lines
Child node boxes
Cost calculations inside boxes

Changes

New nodes are added as the speaker explores different assignments.
Lines connect parent nodes to child nodes.
Calculations are written inside the node boxes.

Invariants

The overall structure remains a tree.
The root node stays at the top.

Interpretation

The visual represents the systematic exploration of possible assignments in the branch and bound algorithm.

Branch-and-bound tree for the assignment problem

Clear evidence

Shown in the video

Evidence

Diagram
Observation
The page shows a hand-drawn tree with a root node labeled LB = $2 + 3 + 1 + 2 = 8$ , branches labeled $a=1$ , $a=2$ , $a=3$ , $a=4$ , then subbranches $b=1$ , $b=3$ , $b=4$ , and leaf boxes with complete assignments and cost totals.
Animation
Observation
A pen points to different nodes while the camera remains mostly fixed on the sheet.

Uncertainties

Some right-side nodes are partially cut off or blurred, so not every branch label is fully legible.

Objects

Root node with LB = 8
Branch nodes labeled $a=1$ , $a=2$ , $a=3$ , $a=4$
Subbranch nodes labeled $b=1$ , $b=3$ , $b=4$
Leaf boxes with assignments such as $a=2$ , $b=1$ , $c=3$ , $d=4$ and $a=2$ , $b=1$ , $c=4$ , $d=3$
Handwritten cost sums and circled totals

Changes

The pen indicates the leaf assignment $a=2$ , $b=1$ , $c=3$ , $d=4$ and its cost 13.
The view shifts slightly upward and leftward near the end, revealing more of the upper-left table area.
The speaker writes or emphasizes the interval 8–13 below the tree.

Invariants

The tree structure remains the same throughout the clip.
The root lower bound stays displayed as 8.
The highlighted feasible leaf cost stays displayed as 13.

Interpretation

The visual layout encodes a search over assignments: each path fixes values for a, b, c, d, and the written sums give node costs used for bounding.

Emphasis on the lower and upper bounds

Clear evidence

Shown in the video

Evidence

Diagram
Observation
Below the tree, the numbers 8 and 13 are emphasized in speech and writing as the bounds.
Audio
Observation
“the cost value will be between eight that is the lower bound and between thirteen.”

Uncertainties

The exact handwritten punctuation around the interval is not fully clear in every frame.

Objects

Number 8 from the root LB
Number 13 from the feasible leaf UB
Handwritten interval notation below the tree

Changes

Attention moves from the leaf cost 13 back to the global bound comparison.
The interval 8–13 is presented as the result for the example.

Invariants

8 remains identified as the lower bound.
13 remains identified as the upper bound.

Interpretation

This segment visually and verbally summarizes the bounding result of the branch-and-bound procedure.

Misconceptions · 6

Confusing the initial lower bound with the proven optimum

Clear evidence

Derived from the video

Evidence

Audio
Observation
The speaker says the total cost of this assignment will be lowest value will be eight.
Formula
Observation
Only the row-minimum sum LB = 8 is shown; no complete assignment is exhibited.

Uncertainties

This is flagged as a potential misunderstanding from the wording, not as a confirmed error in the mathematics of the method.

Misconception

One may infer from the spoken wording that 8 is already the final optimal assignment cost.

Clarification

What the clip actually demonstrates is the computation of an initial lower bound from row minima. The video does not yet show a full branching search or a verified optimal assignment within this excerpt.

Do not reuse the already assigned row when computing remaining minima

Clear evidence

Shown in the video

Evidence

Audio
Observation
The speaker says, 'for the second one we have to write the minimum value that is four except this. We cannot include this one.'
Diagram
Observation
When computing the bound for $a = 1$ , the pen skips row a and chooses minima from rows b, c, d only.

Misconception

One might incorrectly take column minima from all rows, including the row already assigned at the current node.

Clarification

After fixing $a = j$ , the remaining contributions must come only from the unassigned persons, so row a is excluded from the minima for the other columns.

Row and column bounds are both valid

Clear evidence

Derived from the video

Evidence

Audio
Observation
At 0:00, the speaker calculates the root LB as ' $2+3+1+2=8$ ', which corresponds to the minimums of the rows, not the columns.
Diagram
Observation
The standard method for assignment problems typically uses column minimums for the initial lower bound.

Misconception

Only one direction of matrix minima can produce a lower bound.

Clarification

Summing row minima gives 8; summing column minima gives 12. Both bound the optimum below, and the tighter bound depends on the matrix.

Do not count assigned jobs again

Clear evidence

Derived from the video

Evidence

Diagram
Observation
At 2:00, the calculation for node ' $b=1$ ' is written as ' $6+2+1+4=13$ '.
Audio
Observation
The speaker verbally describes the components of the calculation, but the written numbers do not match the correct application of the method.

Misconception

After fixing $a=2$ , $b=1$ , include job 2 again among remaining jobs.

Clarification

The fixed costs are $2+6=8$ . Only jobs 3 and 4 remain, with minima 1 and 4, so the bound is $8+1+4=13$ .

Check matrix entries against the source

Clear evidence

Derived from the video

Evidence

Diagram
Observation
The original table and the second leaf both show c-to-job-4 cost 8; the second leaf totals $2+6+8+2=18$ .
Audio
Observation
Speaker sometimes states a result (e.g., 14) that contradicts the written number (e.g., 13).

Misconception

Misread the handwritten c-to-job-4 cost as 3 instead of 8.

Clarification

Using 8 yields the source bounds and leaf totals correctly; the earlier automated extraction created false error claims by reading it as 3.

An upper bound is not automatically the proven optimum unless all better branches are excluded

Approximate timing

Supplementary explanation

Evidence

Audio
Observation
The speaker says the cost will be between 8 and 13 and calls this the optimal solution range for the example.
Formula
Observation
The page labels 13 as UB rather than explicitly as the unique optimum within this clip.

Uncertainties

This caution is not explicitly stated in the clip; it is added as a conceptual clarification.

Misconception

One might think that any feasible cost labeled UB is immediately the final optimal value without further pruning or comparison.

Clarification

In branch and bound, a feasible solution provides an upper bound on the minimum; optimality requires that no unexplored branch can yield a smaller cost. In this clip, the spoken conclusion treats 8–13 as the bounding result for the worked example.

Concept relations · 12

Branch and bound applied to assignment problems → Assignment problem objective

Clear evidence

Shown in the video

Evidence

Audio
Observation
The speaker says the video will solve the assignment problem by using the branch and bound method.
Caption evidence
Observation
The title pairs ASSIGNMENT PROBLEM with BRANCH AND BOUND METHOD.

Application

Explanation

Branch and bound is presented as the solution technique being applied to the assignment problem.

Computing the initial lower bound from row minima → State space tree as the next stage

Clear evidence

Shown in the video

Evidence

Audio
Observation
The speaker first says to find the lower bound and then says the further procedure will be done through the state space tree.

Prerequisite

Explanation

In the narrated workflow, computing the initial lower bound comes before exploring the state space tree.

Worked 4x4 assignment cost matrix → Assignment problem objective

Clear evidence

Shown in the video

Evidence

Diagram
Observation
The abstract discussion is followed by a concrete 4x4 cost matrix.
Audio
Observation
The speaker says, let us understand this by the help of an example.

Special case

Explanation

The 4x4 matrix is a specific instance of the general assignment problem described earlier.

Computing the initial lower bound from row minima → Lower bound as a least-cost estimate

Clear evidence

Shown in the video

Evidence

Audio
Observation
The definition of lower bound is given verbally before the numerical rule is applied.
Formula
Observation
The later boxed computation implements that idea on the example matrix.

Application

Explanation

The row-minimum summation procedure is the concrete application of the video’s informal lower-bound concept.

Branching on the first assignment variable → Lower bound at a child node after fixing one assignment

Clear evidence

Shown in the video

Evidence

Diagram
Observation
The child nodes $a = 1$ , $a = 2$ , $a = 3$ , $a = 4$ are drawn first, and then lower-bound expressions are written beneath them.
Audio
Observation
The speaker first describes making four blocks and then says they have to find out the lowest cost for those assignments.

Application

Explanation

The branching step creates the subproblems to which the child-node lower-bound rule is applied.

Lower bound at a child node after fixing one assignment → Second-level branching example for an assignment problem

Clear evidence

Shown in the video

Evidence

Formula
Observation
The general rule is instantiated as $9+4+1+4=18$ and $2+5+1+4=12$ in the worked example.

Application

Explanation

The example demonstrates the child-node lower-bound method on concrete matrix data.

Branch and Bound Method for Assignment Problem → Lower Bound Calculation

Clear evidence

Shown in the video

Evidence

Diagram
Observation
The title explicitly links 'ASSIGNMENT PROBLEM' and 'BRANCH AND BOUND METHOD'.

Application

Explanation

The branch and bound method is applied to solve the assignment problem, and its core mechanism relies on calculating lower bounds for partial assignments.

Branch and Bound State Space Tree → Cost Matrix for Assignment Problem

Clear evidence

Shown in the video

Evidence

Diagram
Observation
Title 'ASSIGNMENT PROBLEM BRANCH AND BOUND METHOD' links the two concepts.

Application

Explanation

The branch and bound method is applied to solve the assignment problem defined by the cost matrix.

Assignment problem solved by branch and bound → Root lower bound LB = 8

Clear evidence

Shown in the video

Evidence

Audio
Observation
The speaker links the assignment problem solution directly to the branch and bound method.
Diagram
Observation
The tree displays both LB and UB values as part of the method.

Contains

Explanation

The branch-and-bound solution method includes computing and using a lower bound at the root node.

Assignment problem solved by branch and bound → Upper bound from feasible assignment (a,b,c,d)=(2,1,3,4)

Clear evidence

Shown in the video

Evidence

Diagram
Observation
A leaf of the tree produces the value labeled UB = 13.
Audio
Observation
The speaker says this assignment gives the upper bound.

Contains

Explanation

The same branch-and-bound procedure also generates an upper bound from a feasible complete assignment.

Root lower bound LB = 8 → Optimal cost lies between 8 and 13

Clear evidence

Shown in the video

Evidence

Audio
Observation
“the cost value will be between eight … and … thirteen.”
Formula
Observation
LB = 8 and UB = 13 are both visible.

Application

Explanation

The root lower bound is applied together with the feasible upper bound to state the optimal-cost interval.

Upper bound from feasible assignment (a,b,c,d)=(2,1,3,4) → Optimal cost lies between 8 and 13

Clear evidence

Shown in the video

Evidence

Audio
Observation
The speaker combines the upper bound 13 with the lower bound 8 into a final range.
Formula
Observation
The leaf value 13 is labeled UB.

Application

Explanation

The feasible assignment’s cost is used as the upper endpoint of the bounding interval.

Find an answer · 17

What is the assignment problem in this branch-and-bound lesson?

Clear evidence

Shown in the video

Evidence

Audio
Observation
The speaker defines the task as assigning jobs to persons with least cost.

Knowledge points

Assignment problem objective

How is the initial lower bound computed from a cost matrix in this video?

Clear evidence

Shown in the video

Evidence

Formula
Observation
The written line LB = $2 + 3 + 1 + 2 = 8$ shows the exact rule used.

Knowledge points

Computing the initial lower bound from row minima
Lower bound as a least-cost estimate

Why does the example give LB = 8?

Clear evidence

Shown in the video

Evidence

Formula
Observation
The boxed result is LB = 8.

Knowledge points

Derivation of the initial lower bound from the cost matrix
Initial lower bound for the example equals 8

What step follows the lower-bound calculation in the branch-and-bound method?

Clear evidence

Shown in the video

Evidence

Audio
Observation
The speaker says the further procedure will be done through the state space tree.

Knowledge points

State space tree as the next stage

How should the 4x4 matrix be interpreted in the assignment example?

Clear evidence

Shown in the video

Evidence

Diagram
Observation
Rows are labeled by persons and columns by jobs.

Knowledge points

Worked 4x4 assignment cost matrix

What does the second level of the state space tree represent in this assignment-problem branch-and-bound example?

Clear evidence

Shown in the video

Evidence

Audio
Observation
The speaker explicitly says 'State space tree second level'.
Diagram
Observation
Four child nodes are drawn from the root.

Knowledge points

Branching on the first assignment variable
Expansion of the root node into four branches

How is the lower bound 18 for node $a = 1$ calculated from the cost matrix?

Clear evidence

Shown in the video

Evidence

Formula
Observation
The written expression $9+4+1+4=18$ appears under node $a = 1$ .
Audio
Observation
The speaker explains choosing 9 and then minima 4, 1, and 4 from the remaining rows.

Knowledge points

Lower bound at a child node after fixing one assignment
Derivation of the lower bound for branch $a = 1$

Why is row a excluded when computing the remaining column minima for a child node?

Clear evidence

Shown in the video

Evidence

Audio
Observation
The speaker says they cannot include the already chosen row when finding the minimum.

Knowledge points

Do not reuse the already assigned row when computing remaining minima
Lower bound at a child node after fixing one assignment

How is the lower bound 12 for node $a = 2$ obtained?

Clear evidence

Shown in the video

Evidence

Formula
Observation
The written expression $2+5+1+4=12$ appears under node $a = 2$ .
Audio
Observation
The speaker says the minimum in the first column except row A is five, then one, then four, giving twelve.

Knowledge points

Lower bound at a child node after fixing one assignment
Derivation of the lower bound for branch $a = 2$

How is the lower bound calculated for a specific branch in the assignment problem using the branch and bound method?

Clear evidence

Derived from the video

Evidence

Audio
Observation
The speaker repeatedly explains how to calculate the lower bound for different branches.

Knowledge points

Lower Bound Calculation
Derivation of Lower Bound for Branch $a=1$
Derivation of Lower Bound for Branch $a=2$

What is the rule for selecting which node to expand next in the branch and bound search tree?

Clear evidence

Derived from the video

Evidence

Animation
Observation
The video visually demonstrates the expansion of the search tree.

Knowledge points

Branch and Bound Method for Assignment Problem
Construction of the Branch and Bound Search Tree

What is the optimal assignment and its cost according to the video?

Clear evidence

Derived from the video

Evidence

Audio
Observation
Speaker concludes with the optimal assignment at the end of the clip.

Knowledge points

Cost Matrix for Assignment Problem
Branch and Bound State Space Tree
Solving Assignment Problem via Branch and Bound

Coverage and review notes

Covered · Title page and spoken introduction to solving the assignment problem by branch and bound.

Covered · Verbal explanation of the assignment problem and the goal of minimizing cost.

Covered · Informal definition of the lower bound and transition toward an example.

Covered · The 4x4 cost matrix is shown, annotated as persons versus jobs, and the next procedural stage is named.

Covered · The row-minimum lower-bound calculation is performed and boxed as LB = 8.

Covered · The clip opens on the assignment-problem board and the root lower-bound node, then the presenter explains and draws the second level of the state-space tree with branches $a = 1$ , $a = 2$ , $a = 3$ , $a = 4$ .

Covered · The presenter computes lower bounds for the first two child nodes, writes $9+4+1+4=18$ and $2+5+1+4=12$ , and begins but does not finish the discussion of $a = 3$ before the clip ends.

Covered · The entire clip covers the setup and initial steps of solving an assignment problem using the branch and bound method, including lower bound calculations and tree expansion.

Covered · Entire clip covers the setup and execution of the branch and bound method for the assignment problem, including calculations and conclusion.

Covered · The clip opens on the branch-and-bound tree and highlights the feasible leaf assignment $a=2$ , $b=1$ , $c=3$ , $d=4$ with cost 13 labeled as UB.

Covered · The speaker combines the root lower bound 8 and the feasible upper bound 13 into the interval 8–13 for the optimal cost.

Covered · The camera lingers on the full tree while the speaker summarizes that the assignment problem is solved by the branch and bound method.

Explore the knowledge in this video

Reviewed subject paths

Assignment problem by branch and bound method

The explanation, unpacked.

Chapters

Learning script

Knowledge cards

Assignment problem objective

Branch and bound as the solution method

Lower bound idea

4x4 cost matrix example

Initial lower bound from row minima

State space tree comes next

Caution: lower bound is not yet a proved optimum

Branch-and-bound setup for the assignment problem

Second level of the state-space tree

How to compute a child-node lower bound

Lower bound for branch a=1a = 1a=1

Why the assigned row is excluded

Lower bound for branch a=2a = 2a=2

Branch and Bound Method

Lower Bound Calculation

Search Tree Expansion

Common Pitfall: Incorrect LB Calculation

Assignment Problem Cost Matrix

Branch and Bound Method

Lower Bound Calculation

Optimal Solution Identification

Branch-and-bound tree for an assignment problem

Root lower bound LB = 8

Feasible assignment giving UB = 13

Detailed learning notes

LB

a, b, c, d

1, 2, 3, 4

cost matrix

Cost matrix entries

LB

a=ja = ja=j

a

b

c

d

1, 2, 3, 4

Assignment problem objective

Branch and bound applied to assignment problems

Lower bound as a least-cost estimate

Computing the initial lower bound from row minima

Worked 4x4 assignment cost matrix

State space tree as the next stage

Branching on the first assignment variable

Lower bound at a child node after fixing one assignment

Branch and Bound Method for Assignment Problem

Lower Bound Calculation

Cost Matrix for Assignment Problem

Branch and Bound State Space Tree

Initial lower bound for the example equals 8

Branch and bound can solve the assignment problem

The optimal cost is between the displayed lower and upper bounds

Derivation of the initial lower bound from the cost matrix

Derivation of the lower bound for branch a=1a = 1a=1

Derivation of the lower bound for branch a=2a = 2a=2

Derivation of Root Lower Bound

Derivation of Lower Bound for Branch a=1a=1a=1

Derivation of Lower Bound for Branch a=2a=2a=2

Derivation of Lower Bound for Branch a=3a=3a=3

Derivation of Lower Bound for Branch a=4a=4a=4

Derivation of Lower Bound for Branch b=1b=1b=1 (given a=2a=2a=2)

Derivation of Lower Bound for Branch b=3b=3b=3 (given a=2a=2a=2)

Calculation of Root Lower Bound

Lower Bound for Node a=2a=2a=2, b=1b=1b=1

Four-person, four-job assignment example

Second-level branching example for an assignment problem

Solving a 4x4 Assignment Problem using Branch and Bound

Solving Assignment Problem via Branch and Bound

Worked example: feasible assignment giving UB = 13

Title page with topic headings

Introduction of the cost matrix and its axes

Writing and boxing the lower-bound calculation

Expansion of the root node into four branches

Writing lower-bound expressions under child nodes

Construction of the Branch and Bound Search Tree

Lower bound for branch $a = 1$

Lower bound for branch $a = 2$

$a = j$

Derivation of the lower bound for branch $a = 1$

Derivation of the lower bound for branch $a = 2$

Derivation of Lower Bound for Branch $a=1$

Derivation of Lower Bound for Branch $a=2$

Derivation of Lower Bound for Branch $a=3$

Derivation of Lower Bound for Branch $a=4$

Derivation of Lower Bound for Branch $b=1$ (given $a=2$ )

Derivation of Lower Bound for Branch $b=3$ (given $a=2$ )

Lower Bound for Node $a=2$ , $b=1$

How is the lower bound 18 for node $a = 1$ calculated from the cost matrix?

How is the lower bound 12 for node $a = 2$ obtained?