Accelerating the B&B algorithm for integer programming based on flatness information: an approach applied to the MKP
The present paper develops a branching rule based on the flatness of the polyhedron. The base of this rule is the vector of minimal integer width. There is empirical evidence supporting the conjecture that the direction with the highest value of the components of this vector is a good direction for branching. In this paper, it is provided theoretical results demonstrating that the columns of the matrix A corresponding to the set of constraints may be used to estimate the vector of minimal integer width; this fact is used for building a new version of the branching rule reported earlier. In addition, the new rule is implemented by using a branching direction choosing the child node which is closest to the integer value (either up or down). Thus, a variable rule for descending the tree is used. Every time that a new sub-problem is solved, the list of yet not-solved sub-problems are analyzed and get priority those problems with minimum estimate of the objective function value. The conclusions of the work are based on the knapsack problems of the Knapsack OR-Library. From the results, it is concluded that the rule designed presents low execution times and minimal number of nodes generated.
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).