Accelerating the B&B algorithm for integer programming based on flatness information: an approach applied to the multidimensional knapsack problem
This paper presents a new branching rule based on the flatness of a polyhedron associated to the set of constraints in an integer linear programming problem. The rule called Flatness II is a heuristic technique used with the branch-and-bound method. The rule is concerned with the minimum integer wid...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Croatian Operational Research Society
2017-01-01
|
| Series: | Croatian Operational Research Review |
| Online Access: | http://hrcak.srce.hr/file/267766 |
| Summary: | This paper presents a new branching rule based on the flatness of a polyhedron associated to the set of constraints in an integer linear programming problem. The rule called Flatness II is a heuristic technique used with the branch-and-bound method. The rule is concerned with the minimum integer width vector. Empirical evidence supports the conjecture that the direction with the highest value of the vector’s components indicates a suitable branching direction. The paper provides theoretical results demonstrating that the columns of the matrix A corresponding to a set of constraints Ax≤b may be used to estimate the minimum integer width vector; this fact is used for constructing a new version of the branching rule as was reported in a previous paper by the authors. In addition, the new rule uses a branching direction that chooses the child node closest to the integer value (either up or down). Thus, it uses a variable rule for descending the tree. Every time a new sub-problem is solved, the list of remaining unsolved sub-problems is analyzed, with priority given to those problems with a minimum objective function value estimate. The conclusions of the work are based on knapsack problems from the knapsack OR-Library. From the results, it is concluded that the new rule Flatness II presents low execution times and minimal number of nodes generated. |
|---|---|
| ISSN: | 1848-0225 1848-9931 |