An integer linear programming problem with multi-criteria and multi-constraint levels: A branch-and-partition algorithm

In this paper, we propose a branch-and-partition algorithm to solve the integer linear programming problem with multi-criteria and multi-constraint levels (MC²-ILP). The procedure begins with the relaxation problem that is formed by ignoring the integer restrictions. In this branch-and-partition procedure, an MC² linear programming problem is adopted by adding a restriction according to a basic decision variable that is not integer. Then the MC²-simplex method is applied to locate the set of all potential solutions over possible changes of the objective coefficient parameter and the constraint parameter for a regular MC² linear programming problem. We use parameter partition to divide the (λ, γ) space for integer solutions of MC² problem. The branch-and-partition procedure terminates when every potential basis for the relaxation problem is a potential basis for the MC²-ILP problem. A numerical example is used to demonstrate the proposed algorithm in solving the MC²-ILP problems. The comparison study and discussion on the applicability of the proposed method are also provided.