Skoči na glavni sadržaj

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: 643

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.213 *