A linear expected-time algorithm for deriving all logical conclusions implied by a set of boolean inequalities
Hansen, Pierre; Jaumard, Brigitte; Minoux, Michel (1986), A linear expected-time algorithm for deriving all logical conclusions implied by a set of boolean inequalities, Mathematical Programming, 34, 2, p. 223-231. http://dx.doi.org/10.1007/BF01580586
TypeArticle accepté pour publication ou publié
Journal nameMathematical Programming
MetadataShow full item record
Abstract (EN)Consider a set R of m binary relations on a set of n boolean variables. R may imply a contradiction, the fixation of some variables at 0 or at 1 and/or the identification of some pairs of variables in direct or complemented form. An O(n) expected-time algorithm is given for the derivation of all such logical conclusions. Computational experiments with problems involving up to 2000 variables are reported on. The proposed algorithm is more than 100 times faster than previous methods when n ≥ 100.
Subjects / KeywordsBoolean Inequalities; Implication Graph; Depth-First Search; Strongly Connected Components; Transitive Closure; 0–1 Programming
Showing items related by title and author.
An efficient algorithm for the transitive closure and a linear worst-case complexity result for a class of sparse graphs Jaumard, Brigitte; Minoux, Michel (1986) Article accepté pour publication ou publié
An optimal column-generation-with-ranking algorithm for very large scale set partitioning problems in traffic assignment Ribeiro, Celso Carneiro; Minoux, Michel; Penna, Manoel Camillo (1989) Article accepté pour publication ou publié
A new approach for crew pairing problems by column generation with an application to air transportation Lavoie, Sylvie; Minoux, Michel; Odier, Edouard (1988) Article accepté pour publication ou publié