ISSN:
1432-5217
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Notes:
Abstract A class of optimization problems over subsets of zero-one vectors of then-dimensional unit cube given by a special linear congruence relation is considered. The general problem is formulated as a zero-one linear program, minimal and complete descriptions of the associated polytopes by linear inequalities are derived and an $$\mathcal{O}(n \log n)$$ time algorithm for the optimization problems is given. Since the number of inequalities that completely describe the polytope grows exponentially withn, we also give a separation algorithm that identifies violated inequalities in time $$\mathcal{O}(n^2 )$$ . A particular variation of the bin packing problem is a special case of our problem and can thus be solved in polynomial time.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01415061
Permalink
