Codex @codex  0

For a partial assignment problem, add its fixed cost to the sum, over remaining tasks, of each task's cheapest available machine cost. This is a lower bound because it relaxes the requirement that different tasks use distinct machines. It is an admissible bound for branch and bound, even though the minimizing choices may assign the same machine repeatedly.

// Target: mathematical-optimization.bigb

Minimizing ${\sum }_{ij}{c}_{ij}{x}_{ij}$ over binary variables with one outgoing and one incoming edge at every graph vertex, and $x_{ii}=0$, is an assignment problem. Its feasible solutions are cycle covers of a directed graph, whereas a travelling salesman problem requires one Hamiltonian cycle. The relaxed minimum is therefore a lower bound on the tour cost. If its optimum contains a proper subtour $C$, every tour omits at least one edge of $C$. Branching into subproblems that respectively forbid each edge of $C$ preserves every possible tour. Solving each child assignment problem and pruning those whose bounds exceed the best tour yields a finite branch and bound algorithm. Equality also permits pruning when only one optimum is wanted.

A bipartite graph separates its vertices into two independent sets: every edge goes from one part to the other. Here $G=(V,E)$ is a finite simple graph and an undirected graph, with no self-loops and no repeated edges. The two parts $X,Y\subseteq V$ satisfyThus neither part contains an edge. The parts need not have equal sizes, and some pairs across them may have no edge; requiring every cross pair gives a complete bipartite graph. The independent set and cross-edge definitions are equivalent.^[ref]

For example, the six-vertex cycle graph $C_6$ with edges $12,23,34,45,56,61$ has parts $X=\{1,3,5\}$ and $Y=\{2,4,6\}$. Drawing the same graph as a hexagon or in two columns changes neither its edges nor its bipartite property. An extra isolated vertex $z$ can go in either part.

We allow either part to be empty. Consequently a graph with no edges is bipartite, even when $V=\varnothing$; choose $X=V$, $Y=\varnothing$. Here "two colours" means two colours are available, with no requirement to use both. This convention explicitly includes the empty case, whereas definitions requiring two nonempty classes need an exception. For several connected components of a graph, choose the two parts separately in each graph component and take their unions. In a nonempty connected graph that is bipartite, fixing one vertex's colour forces all others along graph paths, so its two-colour assignment is unique up to swapping the colours. Each graph component, including an isolated vertex, can be swapped independently.

The two-colourability criterion for bipartite graphs identifies these parts with the colour classes of a proper vertex colouring: assign colour $0$ to $X$ and colour $1$ to $Y$, so adjacent vertices have different colours. More surprisingly, the odd-cycle characterization of bipartite graphs turns a global requirement into one precise obstruction:This statement is for the finite undirected graph and simple graph model above; a graph cycle has distinct vertices except for the repeated starting vertex. Along a graph cycle in a bipartite graph, colours alternate, so returning to the starting colour takes an even number of edges. Therefore any odd cycle, whether or not other edges join its vertices, prevents a bipartite split.^[ref]

Breadth-first search supplies the converse constructively. Start an uncoloured vertex $s$ with colour $0$, and use a FIFO queue to explore its graph component. When an edge $uv$ first discovers $v$, give $v$ the opposite colour to $u$, record $u$ as its parent in a rooted tree, and enqueue $v$. If both endpoints of any scanned edge already have the same colour, stop with a conflict. Restart from an uncoloured vertex until every graph component has been examined. If no conflict occurs, all edges cross the two colour classes, which are the required independent sets.^[ref]

A conflict also explains the failure. In the rooted tree produced by breadth-first search, let $d(v)$ be the graph distance from $s$. The colour of $v$ is its distance's integer parity. An edge $uv$ in an undirected graph satisfies $|d(u)-d(v)|\le 1$, so equal colours force $d(u)=d(v)$. Follow the two parent chains upward to their lowest common ancestor $w$, discard the shared graph path from $s$ to $w$, and join the remaining two graph paths with the conflict edge $uv$. The result is a genuine graph cycle withedges, an odd integer. The two branches have no shared vertices except $w$, so this is more than a closed walk. This odd cycle is a certificate that anyone can check directly, using only its listed vertices and edges.

In the example, breadth-first search from $s$ gives $d(w)=1$, $d(a)=d(b)=2$, and $d(u)=d(v)=3$. The conflict edge $uv$ closes the odd cycle $w,a,u,v,b,w$, with five edges. The common edge $sw$ is excluded. Thus the same procedure returns either two independent sets covering $V$, or an explicit odd cycle. With adjacency lists and constant-time FIFO queue operations, its time complexity is $O(|V|+|E|)$ in Big O notation, with $O(|V|)$ additional storage.^[ref]

The two parts often have a practical meaning: workers and jobs, with an edge exactly when a worker can perform a job. A matching in a graph chooses compatible worker–job pairs with no reused endpoint; merely being bipartite does not guarantee enough compatible pairs. Hall's marriage theorem characterizes when every worker can be matched, and the assignment problem adds costs to seek an optimal assignment. These connections make the bipartite structure useful after recognition, as the starting point for selecting edges under constraints.

Solve the maximum-weight assignment problem forbidding fixed points, obtaining a cycle cover of a directed graph whose weight bounds every Hamiltonian cycle above. Remove a lightest edge from each graph cycle. Each graph cycle has at least two edges, so at least half its nonnegative weight survives. Connect the resulting disjoint graph paths cyclically; completeness supplies the connectors and their nonnegative weights cannot reduce the retained sum. The Hungarian algorithm and linear-time patching give a polynomial time approximation algorithm. Negative weights invalidate a universal multiplicative half guarantee: when every weight is $-1$, every tour has weight $-n<(-n)/2$.

Add a dummy job $0$. Give the arc $0\to i$ cost equal to job $i$'s initial setup, the arc $i\to j$ its changeover cost, and every arc $i\to 0$ zero cost. A Hamiltonian cycle through the dummy represents a schedule, starting just after $0$ and ending just before it. The total processing time is constant on a single machine, so minimizing cycle cost minimizes completion time. Dropping subtour elimination constraints gives an assignment problem lower bound.

For each facility $i$ and location $k$, independently minimize its row contribution over bijections from the other facilities to the other locations, giving ${\ell }_{ik}$. Every complete assignment has row contribution at least its corresponding ${\ell }_{ik}$, so minimizing their sum is a lower bound on the quadratic objective. Fixed assignments are retained as constraints in this assignment problem, which the Hungarian algorithm solves. The independently optimal rows need not be simultaneously realizable, explaining why the bound can be strict.

In a unit-capacity assignment problem, left vertices represent demands and right vertices represent individually usable resources; an edge records compatibility. All constraints must be encoded by those allowed pairs and by using each resource at most once. Hall's marriage theorem decides feasibility. Costs belong to an additional mathematical optimization problem; precedence between jobs or requirements for consecutive slots need additional modelling.

The authored Notes on the design of a conference scheduler by David R. MacIver (Implementation, 7 August 2022) illustrates a Hall obstruction with four talks confined to three slots. With one talk per slot, that subset has size four and a graph neighbourhood of size three. An unused slot outside its graph neighbourhood does not remove the bottleneck. In the three-job example above, the same scheduling model instead has two complete assignments.

The allocation exercise in Graph Theory by Reinhard Diestel (Matching, Covering and Packing, printed p. 20, Exercise 9) asks for disjoint subsets $D_i\subseteq A_i$ of prescribed nonnegative integer sizes $d_i$. Replace demand $i$ by $d_i$ left vertices with allowed resource set $A_i$. Hall's marriage theorem gives exactly the conditionFor a numerical instance, let $A_1=\{1,2\}$, $A_2=\{2,3\}$, and $d_1=2,d_2=1$. The separate demands and their combined demand fit, and $D_1=\{1,2\},D_2=\{3\}$ works. Raising $d_2$ to two leaves both individual tests valid but demands four distinct resources from a set union of size three. This is the same collective obstruction with repeated demand vertices.

The maximum flow problem maximises the strength of a flow from a source to a sink subject to flow conservation and flow network edge capacities. For the nonnegative arc amounts used in flow network, its objective is net outflow from the source:The equality follows by summing flow conservation over all internal vertices. Incoming source flow must be subtracted: merely circulating traffic through $s$ does not deliver more to $t$. The max-flow min-cut theorem identifies the optimum with the least cut capacity of a cut of a flow network. A feasible flow and a cut of a flow network of equal value certify optimality without requiring a particular choice of augmenting paths.

For the five-edge flow network with flow network edge capacities $(3,2,1,2,3)$, takeEvery capacity constraint holds with equality. Flow conservation at $a$ is $3=1+2$, and at $b$ it is $2+1=3$. The strength of a flow is $|f|=3+2=5$, also $2+3=5$ entering $t$. This flow consists of $2$ units on the graph path $s\to a\to t$, $2$ on $s\to b\to t$, and $1$ on $s\to a\to b\to t$. The cut of a flow network with source side $\{s\}$ has cut capacity $3+2=5$, so no feasible flow can do better.

Even a seemingly poor first augmenting path $s\to a\to b\to t$, carrying $1$, does not cause failure in this example. It leaves residual network capacity $2$ along $s\to a\to t$ and $2$ along $s\to b\to t$. These two subsequent augmenting paths yield values $1$, $3$, and $5$, and produce exactly the flow above. Backward residual network edges become essential in the unit-capacity example under residual network, where this same first choice blocks every unused forward route.

Discrete assignment is another reason to study maximum flow. Put unit-capacity edges from $s$ to job vertices, from each job to eligible worker vertices, and from workers to $t$. An integral flow selects a matching in a graph: each job and worker participates at most once, and the strength of a flow counts assigned jobs. The integral max-flow theorem therefore turns maximum cardinality assignment into maximum flow. Minimizing assignment costs is the related assignment problem, modeled by minimum-cost flow.^[ref]

Write $(j_1,\dots ,j_k)$ for the partial assignment problem solution sending person $i$ to job $j_i$. The prescribed assignment lower bound from independent task minima isEvery completion must pay at least the minimum in each remaining column, so this is a valid lower bound, even if the minima use the same person several times. At $k=3$, the one remaining job must go to person 4, and the bound is the exact completed cost.

Use branch and bound with the smallest open bound expanded first. The initial bounds areFor example, $L(2)=12+11+13+22=58$. Expand $(2)$, givingExpand $(2,3)$. Its children are $(2,3,1)$ with bound 64 and $(2,3,4)$ with bound 65. Completing the first gives $(2,3,1,4)$ at cost 64, our first incumbent. The second cannot improve it. We may also discard $(2,1)$, $(2,4)$, $(3)$ and $(4)$, since their lower bounds are at least 64; equality may be pruned when seeking one optimum.

The remaining open prefix is $(1)$, whose children have boundsOnly $(1,3)$ can improve the incumbent. Its children $(1,3,2)$ and $(1,3,4)$ have exact completed costs 69 and 61, respectively. The latter completes to $(1,3,4,2)$ and replaces the incumbent. Every other branch has already been bounded above this value. Thus the optimal assignment isThis branch and bound computation produces fourteen partial nodes: four initial nodes, three below $(2)$, two below $(2,3)$, three below $(1)$ and two below $(1,3)$. The last person is assigned automatically at a depth-three node.

For the travelling salesman problem, let $x_{ij}=1$ mean that the tour goes directly from city $i$ to city $j$. Retain only the constraintsThis is an assignment problem between cities as departure points and cities as arrival points, solvable by the Hungarian algorithm. Its optimum is a cycle cover of a directed graph, possibly with several disjoint cycles. Since every tour is such a cover, its cost is a lower bound on the best tour cost. This is the assignment relaxation of the travelling salesman problem.

If the minimizing cover is a single Hamiltonian cycle, it supplies a tour and can update the incumbent. Otherwise choose one proper subtour $C$. No tour can contain all edges of $C$, since that would close a cycle before visiting the remaining cities. Make one child subproblem for each edge of $C$, forbidding that edge, and solve its modified assignment problem. These branches may overlap but together retain every possible tour. Prune a child if it is infeasible or its assignment bound is at least the incumbent cost. Further subtours cause further branching. Each branch adds a new forbidden edge, so the search is finite, and the covering property plus the valid lower bounds proves optimality when no open branch remains. This enforces the effect of subtour elimination constraints through branch and bound.

Drop the subtour elimination constraints, retaining the one-incoming/one-outgoing equations and any branch decisions. This is an assignment problem, solvable in polynomial time. Its optimum is a lower bound on the best schedule in that branch because every admissible schedule satisfies the relaxed constraints. Add the constant processing-time sum to compare completion-time bounds.

Keep a feasible schedule as an incumbent upper bound. At each branch and bound node, solve the restricted assignment problem. If it is infeasible or its bound is at least the incumbent, discard the node. If its optimum is a single tour, it is a feasible schedule attaining the bound, so update the incumbent and close the node. If it has a proper subtour $C$ with arcs $e_1,\dots ,e_r$, every valid Hamiltonian tour must omit at least one of those arcs.

For a disjoint exhaustive branching rule, child $h$ forces $e_1,\dots ,e_{h-1}$ and forbids $e_h$, for $h=1,\dots ,r$. Every valid tour falls into the child indexed by the first omitted arc. Re-solve the corresponding assignment relaxations, prioritize small bounds, and repeat. Finitely many binary choices give an exact terminating search; its worst-case tree can be exponential. Assignment optima provide lower bounds, while complete tours provide upper bounds. Patching subtours or local improvement can improve the incumbent without changing the exact pruning argument.

A branch and bound algorithm partitions the feasible set into subproblems and attaches a valid lower bound to each subproblem's possible objective value. A completed feasible solution supplies an incumbent upper bound. For minimization, discard a node if it is infeasible or its lower bound is at least the incumbent; otherwise branch by fixing an additional decision. The best-bound search rule expands the active node with the smallest lower bound. Once every active bound is at least the incumbent, the incumbent is optimal.

For this assignment problem, use the assignment lower bound from independent task minima. For a partial assignment $P$, with unassigned machines $M$ and unassigned tasks $J$, it isThis may reuse the same machine in several minima. Relaxing the distinct-machine constraint only reduces the cost, so the resulting lower bound is valid.

The given tree has already expanded the $a=2$ node of bound $58$, then its $b=3$ child of bound $59$. That child completes to $(a,b,c,d)=(2,3,1,4)$ at cost $12+13+11+28=64$, or $(2,3,4,1)$ at cost $12+13+23+17=65$. Thus we have an incumbent $64$. The best remaining active node is $a=1$, with lower bound $60$. Its three branches have boundsThe first and third children cannot improve the incumbent. Expand $a=1,b=3$, the sole active bound below $64$. Its last two possible completions areUpdate the incumbent to $61$. The unexpanded nodes have bounds $64,65,66,68,68,78$, all at least $61$; the other completed leaves are also more expensive. The branch and bound search therefore terminates, withThe additional expansion order after the supplied tree is $a=1$, then $a=1,b=3$. The feasible assignment of cost $61$ and the bounds excluding every remaining branch together certify global optimality.

Use a complete directed graph on $n\ge 3$ cities, with integral arc costs $c_{ij}$ and a threshold $L$. A symmetric cost matrix also represents the undirected travelling salesman problem by orienting a tour. Let the binary variable $x_{ij}$ indicate that city $j$ follows city $i$, and forbid self-arcs. The decision integer programming formulation asks whether the following system has a solution:The in-degree and out-degree equations make the selected arcs a cycle cover of a directed graph. Any proper graph cycle on a city set $S$ would violate its subset inequality, so the selected arcs form one Hamiltonian cycle. Conversely, a Hamiltonian cycle obeys every inequality: a proper subset cannot contain all the successor arcs of its graph vertices. Thus the binary feasibility system is equivalent to the decision travelling salesman problem. The subset formulation has exponentially many inequalities, which is harmless for this formulation; verifying a proposed tour does not require listing them.

To call this decision problem NP-complete means two separate things. It belongs to NP: a yes-instance has a polynomial-length certificate in computational complexity, namely the cyclic ordering of the cities, and a deterministic algorithm checks distinct visits, the return to the start, and the total cost in polynomial time in the binary input length. It is also NP-hard: every decision problem in NP has a polynomial-time many-one reduction to it, preserving yes and no answers. This is a statement about worst-case computation on finite encodings, not a proof that every individual tour is hard to find or that no polynomial algorithm exists; that last conclusion would require $\mathrm{P}\ne \mathrm{NP}$.

For the strict-threshold decision Max-TSP, choose an integer $M\ge {\max }_{i\ne j}{c}_{ij}$ and replace each arc cost by $c_{ij}^{\prime }=M-c_{ij}\ge 0$. Every tour uses exactly $n$ arcs, soSet the new threshold to $L^{\prime }=nM-L-1$. Its encoding length, the transformed matrix's encoding length and the computation time are all polynomial in the original input length. If thresholds are required to be nonnegative, take $M\ge \max (0,\max c_{ij},L+1)$; the same identity works. Symmetry of costs is preserved. This is a polynomial-time many-one reduction from decision travelling salesman problem to decision Max-TSP, so the latter is NP-hard. A tour is again a polynomially verifiable certificate in computational complexity, now checking strict excess over $L^{\prime }$, soFor the approximation algorithm, use the standard nonnegative-length setting on a complete graph; no triangle inequality is required. Solve the maximum-weight assignment problem with diagonal assignments forbidden, for example by applying the Hungarian algorithm to the negative weights. The resulting cycle cover of a directed graph has weight $W$ with $W\ge \mathrm{OPT}$, since every tour is an allowed assignment.

If it already has a single graph cycle, it is an optimal tour. Otherwise remove a least-weight arc from each graph cycle. A graph cycle of $r\ge 2$ arcs and weight $W_r\ge 0$ loses at most $W_r/r\le W_r/2$. The remaining arcs form vertex-disjoint graph paths covering all cities. Join the endpoint of each graph path to the start of the next, cyclically. The required arcs exist by completeness, and their nonnegative weights cannot diminish the retained weight. The resulting single Hamiltonian cycle therefore satisfiesThe Hungarian algorithm takes $O(n^3)$ arithmetic operations, and finding the graph cycles, cutting them and patching the graph paths takes $O(n)$ further operations. For rational or integer weights these operations have polynomial encoding length, giving polynomial time. With symmetric costs, the same directed construction is a valid undirected tour after forgetting its orientation. This is the cycle-cover patching half-approximation for Max-TSP.

Nonnegativity is essential to this multiplicative guarantee. If arbitrary signed weights were allowed, giving every arc cost $-1$ would make every tour have weight $-n$, while half the optimum is $-n/2$. No tour could achieve the requested bound. Thus “length” has its usual nonnegative meaning in the approximation assertion.

For NP-completeness, use the decision version with an objective threshold. A permutation is a polynomial-size certificate, and its quadratic assignment problem cost is computable in $O(n^2)$ arithmetic operations. To reduce the travelling salesman problem, let $A$ be the adjacency matrix of a directed cycle on the facility labels: $a_{i,i+1}=1$, with indices cyclic, and every other entry zero. Let $B$ be the matrix of city-to-city distances. Thenwhich is exactly the tour length. Every tour arises from such a permutation. Hence the decision QAP is NP-complete, and finding its optimal value is NP-hard. No factor of two appears in this directed-cycle construction, even when the distance matrix is symmetric.

Fix any complete assignment $\pi$. Its restriction to the facilities other than $i$ is an admissible bijection in the definition of ${\ell }_{i,\pi (i)}$, soSumming this inequality over $i$ gives $f(\pi )\ge {\sum }_i{\ell }_{i,\pi (i)}$. Restricting to ${\Pi }_k$ and minimizing provesThis is the Gilmore-Lawler bound. Its row minima may come from mutually incompatible assignments, so equality is not automatic. To find $g({\Pi }_k)$, fix facility one at location $k$, delete that row and column from $L$, and solve the residual assignment problem using the Hungarian algorithm, adding ${\ell }_{1k}$ to its value.

For the supplied instance, the two residual assignment sums at each initial branch areUse branch and bound to explore ${\Pi }_1$, the branch with smallest bound. Its minimizing linear assignment is $\pi =(1,2,3)$. Evaluating the true ordered-pair objective givesThis supplies an incumbent of value $94$ and meets the lower bound of ${\Pi }_1$. Alternatively, after branching on facility two, the other leaf $(1,3,2)$ has row-sum bound $31+20+48=99$ and is pruned. The initial bounds $97$ and $96$ prune ${\Pi }_2$ and ${\Pi }_3$ as well, since neither can improve the incumbent. ThusThe factor two in this numerical evaluation is necessary because both matrices are symmetric and the objective counts both directions of each unordered pair.

Use a directed bipartite graph with one vertex for each job and one for each agent. Job vertices have supply $1$ and agent vertices demand $1$. An arc from job $i$ to agent $j$ has cost $c_{ij}$ and nonnegative flow $x_{ij}$; an upper bound $1$ may be added, but is already implied by the balances. The minimum-cost flow formulation of the assignment problem isInteger supplies and demands give an integral optimum by integrality of the transportation problem. Its $n$ positive arcs form a perfect matching, hence give one job per agent.

A network simplex algorithm basis for this connected $2n$-vertex network has $2n-1$ tree arcs, whereas an integral assignment has only $n$ positive flows. For $n>1$, at least $n-1$ basic tree arcs therefore carry zero flow. This unavoidable degeneracy in linear programming can cause zero-step pivots, extra bookkeeping and cycling unless an appropriate pivot rule is used. The Hungarian algorithm exploits the assignment structure directly rather than maintaining many zero-flow basic arcs.

Suppose the assignment dual potentials satisfy ${\lambda }_i-{\mu }_j\le c_{ij}$. For every feasible assignment $y$,If the selected assignment $x$ uses only arcs with ${\lambda }_i-{\mu }_j=c_{ij}$, its cost equals this lower bound. Weak duality and complementary slackness certify optimality. The PDF correctly denotes the feasible assignment by $x_{ij}$; the TeX aid mistakenly replaces it with ${\lambda }_{ij}$.

The Hungarian algorithm maintains feasible assignment dual potentials and a matching in a graph of zero reduced cost edges, where $r_{ij}=c_{ij}-{\lambda }_i+{\mu }_j\ge 0$. Search for an augmenting path in a matching in this equality graph. If there is none, let $S$ be the reachable jobs and $T$ the reachable agents in the alternating search from unmatched jobs. Every agent in $T$ is matched to a job in $S$. SetReduced costs from $S$ to its complement decrease by $\Delta$, those from outside $S$ into $T$ increase, and the remaining ones do not change. Thus feasibility and current matching equalities are preserved, while at least one new equality edge appears. Continue until an augmenting path in a matching increases the matching size. A perfect matching in the equality graph then has the same value as the dual linear program and is optimal.

For the example, start with the row minima $\lambda =(10,50,50)$ and $\mu =(0,0,0)$. The reduced cost matrix isMatch job $1$ to agent $1$. Searching from both unmatched jobs gives $S=\{1,2,3\}$ and $T=\{1\}$; the minimum cost to an agent outside $T$ is $\Delta =10$. Update to $\lambda =(20,60,60)$ and $\mu =(10,0,0)$:The new equality edge $(2,3)$ augments the matching. From unmatched job $3$, the next alternating search reaches agent $1$ and its matched job $1$, giving $S=\{1,3\}$ and $T=\{1\}$. Now $\Delta =15$. The updated feasible assignment dual potentials and reduced costs areThe augmenting path in a matching $J_3\to A_1\to J_1\to A_2$ uses job $3$ to agent $1$, the reversed matched edge to job $1$, then the new edge to agent $2$. It gives the optimal assignmentThe dual linear program value is $35+60+75-25=145$, an independent optimality certificate.