On the calculation of true and pseudo penalties in multiple choice integer programming (Q1183620): Difference between revisions

Let \(S\) be the set of 0/1 variables whose sum in some linear optimization problem must be 1. If the problem is solved by a branch and bound algorithm, using LP relaxation, then an effective branching strategy is to partition \(S\) into two almost equal (in cardinality) subsets \(S_ 1\) and \(S_ 2\) and to generate two branches subject to the requirement that the sum of the variables over \(S_ i\) is equal to 0. Using a transformation technique the autors show how to calculate penalties from the optimal LP tableau, when \(S\) is covered by specially arranged subsets. But is seems easier to calculate such penalties, simply by doing one dual pivot on a row (corresponding to a given restriction), implicitly added to the optimal tableau. At least such an alternative should have been considered.