Enumeration of Dominant Solutions An Application in Transport Network Design

A one-dimensional binary integer programming problem (1db-ipp) is concerned with selectinga subset from a set of k items in budget constraint to optimize a goal function. in this problema dominant solution is defined as a feasible selection to which no further item could be added inbudget constraint. this paper presents a simple algorithm for enumeration of dominant solutions(eds) and investigates its functionality. the algorithm is then applied on the formulationof the network design problem (ndp) with fixed travel-time links. the problem is a case studyof 1db-ipps in the transportation planning literature which arises in the networks where the linktravel-times are not sensitive to the amount of flow. the results are reported in detail for three illustrativeexamples and compared with the results of the branch-and-bound (b&b) algorithm.these examples suggest that in lower budget levels up to 40.2, 40.3 and 27.1 percentages the edsalgorithm outperforms the b&b algorithm. however, the overall performance of the b&b algorithmis notably faster in higher budget levels.