Premium
An Integer Linear Programming Problem with Multi‐Criteria and Multi‐Constraint Levels: a Branch‐and‐Partition Algorithm
Author(s) -
Li Jun,
Shi Yong
Publication year - 2001
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/1475-3995.00328
Subject(s) - integer programming , branch and cut , linear programming relaxation , branch and price , partition (number theory) , linear programming , mathematics , mathematical optimization , simplex algorithm , partition problem , relaxation (psychology) , linear fractional programming , algorithm , integer (computer science) , basis (linear algebra) , computer science , combinatorics , psychology , social psychology , geometry , programming language
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.