Add a new constraint to the current set of bounding constraints: x_j <= bound or x_j >= bound (e.
Add a new constraint to the current set of bounding constraints: x_j <= bound or x_j >= bound (e.g., x_1 <= 2. or x_0 >= 4.).
the index of variable x_j
whether it is a "less than or equal to" (le) constraint
the bounding value
Starting with the original constraints (a, b) add the current set of bounding constraints.
Return j such that x_j has a fractional (non-integer) value, -1 otherwise.
Return j such that x_j has a fractional (non-integer) value, -1 otherwise. Make sure that j is not in the exclusion list.
the vector to check
Return the optimal (maximal) integer solution.
Solve the Integer Linear Programming (ILP) problem by using Branch and Bound and the Two-Phase Simplex Algorithm, recursively.
Solve the Integer Linear Programming (ILP) problem by using Branch and Bound and the Two-Phase Simplex Algorithm, recursively.
the current depth of recursion
the current set of original and new constraints (a x <= b)
This class solves Integer Linear Programming (ILP) and Mixed Integer Linear Programming (MILP) problems recursively using the Simplex algorithm. First, an LP problem is solved. If the optimal solution vector x is entirely integer valued, the ILP is solved. If not, pick the first x_j that is not integer valued. Define two new LP problems which bound x_j to the integer below and above, respectively. Branch by solving each of these LP problems in turn. Prune by not exploring branches less optimal than the currently best integer solution. This technique is referred to as Branch and Bound. An exclusion set may be optionally provided for MILP problems. TODO: Use the Dual Simplex Algorithm for better performance.
Given a constraint matrix 'a', limit/RHS vector 'b' and cost vector 'c', find values for the solution/decision vector 'x' that maxmize the objective function f(x), while satisfying all of the constraints, i.e.,
maximize f(x) = c x subject to a x <= b, x >= 0, x must be a vector of integers
Make b_i negative to indicate a ">=" constraint