Job Assignment Problem Using Branch And Bound Algorithm In Python

Branch and Bound

I. Introduction

II. Illustration on the Job Assignment Problem

III. The General Branch and Bound Algorithm

IV. Criteria for the Choice of Approximate Cost Functions

V. Implementation of the B&B Job Assignment Algorithm

I. Introduction

  • Branch and bound is a systematic method for solving optimization problems
  • B&B is a rather general optimization technique that applies where the greedy method and dynamic programming fail.
  • However, it is much slower. Indeed, it often leads to exponential time complexities in the worst case.
  • On the other hand, if applied carefully, it can lead to algorithms that run reasonably fast on average.
  • The general idea of B&B is a BFS-like search for the optimal solution, but not all nodes get expanded (i.e., their children generated). Rather, a carefully selected criterion determines which node to expand and when, and another criterion tells the algorithm when an optimal solution has been found.
Back to Top

II. Illustration on the Job Assignment Problem

  • Input: n jobs, n employees, and an n x n matrix A where Aij be the cost if person i performs job j.
  • Problem: find a one-to-one matching of the n employees to the n jobs so that the total cost is minimized.
  • formally, find a permutation f such that C(f), where
    C(f)=A1f(1) + A2f(2) + ... + Anf(n)
    is minimized.
  • A brute-force method would generate the whole solution tree, where every path from the root to any leaf is a solution, then evaluate the C of each solution, and finally choose the path with the minimum cost.
  • Illustration on this specific instance of the job-assignment problem:
  • In informal terms, the problem is to choose a single number from each row such that (1) no two numbers are chosen from the same columns, and (2) the sum of the chosen numbers is minimized.
  • The brute force method:
  • The first idea of B&B is to develop "a predictor" of the likelihood (in a loose sense) of a node in the solution tree that it will lead to an optimal solution. This predictor is quantitative.
  • With such a predictor, the B&B works as follows:
    1. Which node to expand next: B&B chooses the live node with the best predictor value
    2. B&B simply expands that node (i.e., generate all its children)
    3. the predictor value of each newly generated node is computed, the just expanded node is now designated as a dead node, and the newly generated nodes are designated as live nodes.
    4. Termination criterion: When the best node chosen for expansion turn out to be a final leaf (i.e., at level n), that when the algorithm terminates, and that node corresponds to the optimal solution. The proof of optimality will be presented later on.
  • What could that predictor be?
  • In the case of minimization problem, one candidate predictor of any node is the cost so far . That is, each node corresponds to (partial) solution (from the root to that node). The cost-so-far predictor is the cost of the partial solution.
  • Apply this preliminary algorithm on the above specific instance of the job assignment problem
  • A better predictor for the job assignment problem is:
    (cost so far) + (sum of the minimums of the remaining rows)
  • Apply B&B with the new predictor to the same instance of the job assignment problem
  • A yet another predictor is
    cost so far + sumni=k+1p i
    where p i is the minimum value in row i of the cost matrix A, such that p is not in the column of any of the terms chosen in the partial solution so far.
  • Apply B&B with the last predictor to the same instance of the job assignment problem
Back to Top

The General Branch and Bound Algorithm

  • Each solution is assumed to be expressible as an array X[1:n] (as was seen in Backtracking).
  • A predictor, called an approximate cost function CC, is assumed to have been defined.
  • Definitions:
    • A live node is a node that has not been expanded
    • A dead node is a node that has been expanded
    • The expanded node (or E-node for short) is the live node with the best CC value.
  • The general B&B algorithm follows:

Procedure B&B() begin E: nodepointer; E := new(node); -- this is the root node which -- is the dummy start node H: heap; -- A heap for all the live nodes -- H is a min-heap for minimization problems, -- and a max-heap for maximization problems. while (true) do if (E is a final leaf) then -- E is an optimal solution print out the path from E to the root; return; endif Expand(E); if (H is empty) then report that there is no solution; return; endif E := delete-top(H); endwhileend

Procedure Expand(E) begin - Generate all the children of E; - Compute the approximate cost value CC of each child; - Insert each child into the heap H; end
Back to Top

IV. Criteria for the Choice of Approximate Cost Functions

  • Definition of the cost function C: For every node X in the solution tree, the cost function C(X) is the cost of the best solution that goes through node X.
  • Theorem: In the case of minimization problems, if CC(X) <= C(X) for every node X, and if CC(X)=C(X) for every final leaf node X, then the first expanding node (best-CC node) that happens to be a final leaf corresponds to an optimal solution.
  • Proof:
    • Let E be the E-node that happens to be a final leaf.
    • Need to prove that C(E) <= C(X) for any live node X.
    • C(E)=CC(E) because E is a final leaf
    • CC(E) <= CC(X) for any live node X, because E is the expanding node, that is, the minimum-CC node
    • CC(X) <= C(X) by assumption.
    • Therefore, C(E)=CC(E)<=CC(X) <=C(X), leading to C(E)<=C(X). Q.E.D.
  • Therefore, the criteria for the approximate cost function CC for minimization problems are:
    1. CC(X) <= C(X) for all live nodes X
    2. CC(X)=C(X) for all final leaves.
  • The criteria for the approximate cost function CC for maximization problems are:
    1. CC(X) >= C(X) for all live nodes X
    2. CC(X)=C(X) for all final leaves.
  • Because of those criteria, CC is called an underestimate of C (in the case of minimization), and an overestimate of C (in the case of maximization)
  • The closer CC is to C, the faster is the algorithm in reaching an optimal solution.
Back to Top

V. Implementation of the B&B Job Assignment Algorithm

  • We need to define the full record of a node
  • We need to fully implement the Expand procedure
  • Every node corresponds to something like X[i]=j, which signifies that the job X[i] assigned to person i is j.
  • every node must store its CC value.
  • each node must point to its parent so that when an optimal leaf is generated, the path from that leaf to the root can be traced and printed out as the optimal solution.
  • Therefore, a node record structure should look like: Record node Begin Parent: nodepointer; I: integer; -- person I J: integer; -- Job J is assigned to person I CC: real; End
  • Take the 2nd CC formula:
    CC(X at level k) = cost so far + sumni=k+1mi
    where mi is the minimum of row i.
  • observe that if X is a pointer to a node, then
    X->CC = X->Parent->CC + AX->I,A->J - mX->I
  • Write a piece of code that computes the mis for i=1,2,...,n
  • Code for Expand(E):
    Procedure Expand(E) begin /* Generate all the children of E; */ I := E->I; X,p: nodepointer; S[1:n]: Boolean; /* S is a bitmap set initialized to 0*/ /* S will contain all the jobs that have been assigned by the partial path from the root to E */ p := E; while (p is not the root) do S[p->J] := 1; p := p-> Parent; endwhilefor job=1 to n doif S[job] = 0 then X := new(node); X->I := I + 1; X->J := job; X->Parent := E; X->CC := E->CC + AX->I,X->J-mX->I; Insert(X,H); endifendforend
Back to Top

Exercise: The 0/1 knapsack problem is the same as the regular knapsack problem except that one cannot take a fraction of any item: either the whole item is taken, or nothing of that item is taken. Develop a B&B algorithm for the 0/1 knapsack problem.

Hint: take CC(X) to be

the cost so far + the regular knapsack solution for the remaining items.
Show that this approximate cost function CC meets the criteria.

Branch and bound (BB, B&B, or BnB) is an algorithm design paradigm for discrete and combinatorial optimization problems, as well as mathematical optimization. A branch-and-bound algorithm consists of a systematic enumeration of candidate solutions by means of state space search: the set of candidate solutions is thought of as forming a rooted tree with the full set at the root. The algorithm explores branches of this tree, which represent subsets of the solution set. Before enumerating the candidate solutions of a branch, the branch is checked against upper and lower estimated bounds on the optimal solution, and is discarded if it cannot produce a better solution than the best one found so far by the algorithm.

The algorithm depends on the efficient estimation of the lower and upper bounds of a region/branch of the search space and approaches exhaustive enumeration as the size (n-dimensional volume) of the region tends to zero.[clarification needed][citation needed]

The method was first proposed by A. H. Land and A. G. Doig[1] in 1960 for discrete programming, and has become the most commonly used tool for solving NP-hard optimization problems.[2] The name "branch and bound" first occurred in the work of Little et al. on the traveling salesman problem.[3][4]

Overview[edit]

The goal of a branch-and-bound algorithm is to find a value x that maximizes or minimizes the value of a real-valued function f(x), called an objective function, among some set S of admissible, or candidate solutions. The set S is called the search space, or feasible region. The rest of this section assumes that minimization of f(x) is desired; this assumption comes without loss of generality, since one can find the maximum value of f(x) by finding the minimum of g(x) = −f(x). A B&B algorithm operates according to two principles:

  • It recursively splits the search space into smaller spaces, then minimizing f(x) on these smaller spaces; the splitting is called branching.
  • Branching alone would amount to brute-force enumeration of candidate solutions and testing them all. To improve on the performance of brute-force search, a B&B algorithm keeps track of bounds on the minimum that it is trying to find, and uses these bounds to "prune" the search space, eliminating candidate solutions that it can prove will not contain an optimal solution.

Turning these principles into a concrete algorithm for a specific optimization problem requires some kind of data structure that represents sets of candidate solutions. Such a representation is called an instance of the problem. Denote the set of candidate solutions of an instance I by SI. The instance representation has to come with three operations:

  • branch(I) produces two or more instances that each represent a subset of SI. (Typically, the subsets are disjoint to prevent the algorithm from visiting the same candidate solution twice, but this is not required. The only requirement for a correct B&B algorithm is that the optimal solution among SI is contained in at least one of the subsets.[5])
  • bound(I) computes a lower bound on the value of any candidate solution in the space represented by I, that is, bound(I) ≤ f(x) for all x in SI.
  • solution(I) determines whether I represents a single candidate solution. (Optionally, if it does not, the operation may choose to return some feasible solution from among SI.[5])

Using these operations, a B&B algorithm performs a top-down recursive search through the tree of instances formed by the branch operation. Upon visiting an instance I, it checks whether bound(I) is greater than the upper bound for some other instance that it already visited; if so, I may be safely discarded from the search and the recursion stops. This pruning step is usually implemented by maintaining a global variable that records the minimum upper bound seen among all instances examined so far.

Generic version[edit]

The following is the skeleton of a generic branch and bound algorithm for minimizing an arbitrary objective function f.[2] To obtain an actual algorithm from this, one requires a bounding function g, that computes lower bounds of f on nodes of the search tree, as well as a problem-specific branching rule.

  1. Using a heuristic, find a solution xh to the optimization problem. Store its value, B = f(xh). (If no heuristic is available, set B to infinity.) B will denote the best solution found so far, and will be used as an upper bound on candidate solutions.
  2. Initialize a queue to hold a partial solution with none of the variables of the problem assigned.
  3. Loop until the queue is empty:
    1. Take a node N off the queue.
    2. If N represents a single candidate solution x and f(x) < B, then x is the best solution so far. Record it and set Bf(x).
    3. Else, branch on N to produce new nodes Ni. For each of these:
      1. If f(Ni) > B, do nothing; since the lower bound on this node is greater than the upper bound of the problem, it will never lead to the optimal solution, and can be discarded.
      2. Else, store Ni on the queue.

Several different queue data structures can be used. A stack (LIFO queue) will yield a depth-first algorithm. A best-first branch and bound algorithm can be obtained by using a priority queue that sorts nodes on their g-value.[2] The depth-first variant is recommended when no good heuristic is available for producing an initial solution, because it quickly produces full solutions, and therefore upper bounds.[6]

Improvements[edit]

When is a vector of , branch and bound algorithms can be combined with interval analysis[7] and contractor techniques in order to provide guaranteed enclosures of the global minimum.[8][9]

Applications[edit]

This approach is used for a number of NP-hard problems

Branch-and-bound may also be a base of various heuristics. For example, one may wish to stop branching when the gap between the upper and lower bounds becomes smaller than a certain threshold. This is used when the solution is "good enough for practical purposes" and can greatly reduce the computations required. This type of solution is particularly applicable when the cost function used is noisy or is the result of statistical estimates and so is not known precisely but rather only known to lie within a range of values with a specific probability.[citation needed]

Relation to other algorithms[edit]

Nau et al. present a generalization of branch and bound that also subsumes the A*, B* and alpha-beta search algorithms from artificial intelligence.[14]

External links[edit]

  • LiPS — Free easy-to-use GUI program intended for solving linear, integer and goal programming problems.
  • Cbc - (Coin-or branch and cut) is an open-source mixed integer programming solver written in C++.

See also[edit]

References[edit]

  1. ^A. H. Land and A. G. Doig (1960). "An automatic method of solving discrete programming problems". Econometrica. 28 (3). pp. 497–520. doi:10.2307/1910129. 
  2. ^ abcClausen, Jens (1999). Branch and Bound Algorithms—Principles and Examples(PDF) (Technical report). University of Copenhagen. 
  3. ^ abLittle, John D. C.; Murty, Katta G.; Sweeney, Dura W.; Karel, Caroline (1963). "An algorithm for the traveling salesman problem"(PDF). Operations Research. 11 (6): 972–989. doi:10.1287/opre.11.6.972. 
  4. ^Balas, Egon; Toth, Paolo (1983). Branch and bound methods for the traveling salesman problem(PDF) (Report). Carnegie Mellon University Graduate School of Industrial Administration. 
  5. ^ abBader, David A.; Hart, William E.; Phillips, Cynthia A. (2004). "Parallel Algorithm Design for Branch and Bound"(PDF). In Greenberg, H. J. Tutorials on Emerging Methodologies and Applications in Operations Research. Kluwer Academic Press. 
  6. ^Mehlhorn, Kurt; Sanders, Peter (2008). Algorithms and Data Structures: The Basic Toolbox(PDF). Springer. p. 249. 
  7. ^Moore, R. E. (1966). Interval Analysis. Englewood Cliff, New Jersey: Prentice-Hall. ISBN 0-13-476853-1. 
  8. ^Jaulin, L.; Kieffer, M.; Didrit, O.; Walter, E. (2001). Applied Interval Analysis. Berlin: Springer. ISBN 1-85233-219-0. 
  9. ^Hansen, E.R. (1992). Global Optimization using Interval Analysis. New York: Marcel Dekker. 
  10. ^Conway, Richard Walter; Maxwell, William L.; Miller, Louis W. (2003). Theory of Scheduling. Courier Dover Publications. pp. 56–61. 
  11. ^Fukunaga, Keinosuke; Narendra, Patrenahalli M. (1975). "A branch and bound algorithm for computing k-nearest neighbors". IEEE Transactions on Computers: 750–753. doi:10.1109/t-c.1975.224297. 
  12. ^Narendra, Patrenahalli M.; Fukunaga, K. (1977). "A branch and bound algorithm for feature subset selection"(PDF). IEEE Transactions on Computers. C–26 (9): 917–922. doi:10.1109/TC.1977.1674939. 
  13. ^Nowozin, Sebastian; Lampert, Christoph H. (2011). "Structured Learning and Prediction in Computer Vision". Foundations and Trends in Computer Graphics and Vision. 6 (3–4): 185–365. doi:10.1561/0600000033. ISBN 978-1-60198-457-9. 
  14. ^Nau, Dana S.; Kumar, Vipin; Kanal, Laveen (1984). "General branch and bound, and its relation to A∗ and AO∗"(PDF). Artificial Intelligence. 23 (1): 29–58. doi:10.1016/0004-3702(84)90004-3. 

0 Replies to “Job Assignment Problem Using Branch And Bound Algorithm In Python”

Lascia un Commento

L'indirizzo email non verrà pubblicato. I campi obbligatori sono contrassegnati *