1EECS 261A Project:
Fall Quarter 2022
Due Date: Friday December 9, 2022
2I. PROJECT DESCRIPTION
Implement the branch-and-bound algorithm as a mean of solving a given Mixed Linear Integer
Programming (MLIP) problem with the following formulation.
max ζ = cT x
S.T. A x ≤ b
x ≥ 0
xi ∈ Z, i ∈ {1, · · · , n}
whereA , c, and b are of dimensions m × n, n × 1, and m × 1, respectively . Further, Z is the
set of positive integer numbers. Note that in the general case of the problem above, either all or
some of the variables are integer variables. While in the former case the problem is classified as
a Linear Integer Problem (LIP) problem, in the latter case it is classified as an MLIP problem.
The implementation should accept matrix A, vector c, vector b, and the indices associated
with the integer variables. It should then generate the enumeration tree associated with a given
problem. Each node of the enumeration tree has to illustrate the optimal value of the objective
function ζ as well as the associated vector x. Alternatively, a tree node may be labeled infeasible
if an optimal solution does not exist. Further, the illustration of the tree should distinguish
between a leaf node and a regular node. The FINAL optimal node is to be uniquely distinguished
in the tree. The output of the program should include the complete enumeration tree associated
with a given problem.
II. IMPLEMENTATION
Since the emphasis of the project is on the implementation of branch and bound algorithm, it is
NOT required to implement the simplex method and/or any other alternative to solve a standard
LP problem. Matlab may be used to implement the project with the consideration of the fact that
only standard function calls of the optimization toolbox such as linprog are allowed.