Skoči na glavni sadržaj

Croatian Operational Research Review, Vol. 8 No. 1, 2017.

Izvorni znanstveni članak

https://doi.org/10.17535/crorr.2017.0008

Accelerating the B&B algorithm for integer programming based on flatness information: an approach applied to the multidimensional knapsack problem

Ivan S. Derpich orcid id orcid.org/0000-0001-9759-7285 ; Industrial Engineering Department, Universidad de Santiago de Chile, 3363 Av.Estación Central, Santiago, Chile
Juan M. Sepúlveda orcid id orcid.org/0000-0003-3755-0981 ; Industrial Engineering Department, Universidad de Santiago de Chile, 3363 Av.Estación Central, Santiago, Chile

Puni tekst: engleski pdf 263 Kb

str. 119-136

preuzimanja: 746

citiraj

Sažetak

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.

Ključne riječi

integer programming; branch-and-bound method; branching rule; algorithm efficiency

Hrčak ID:

181653

URI

https://hrcak.srce.hr/181653

Datum izdavanja:

15.4.2017.

Posjeta: 1.749 *