Please use this identifier to cite or link to this item:
Type: Artigo de periódico
Title: Mixed-integer column generation algorithms and the probabilistic maximum satisfiability problem
Author: Hansen, P
Jaumard, B
de Aragao, MP
Abstract: The column generation approach to large-scale linear programming is extended to the mixed-integer case. Two general algorithms, a dual and a primal one, are presented. Both involve finding k-best solutions to combinatorial optimization subproblems. Algorithms for these subproblems must be tailored to each specific application. Their use is illustrated by applying them to a new combinatorial optimization problem with applications in Artificial Intelligence: Probabilistic Maximum Satisfiability. This problem is defined as follows: consider a set of logical sentences together with probabilities that they are true, assume this set of sentences is not satisfiable in the probabilistic sense, i.e., there is no probability distribution on the set of possible worlds (truth assignments to the sentences corresponding to at least one truth assignment to the logical variables they contain) such that for each sentence the sum of probabilities of the possible worlds in which it is true is equal to its probability of being true; determine a minimum set of sentences to be deleted in order to make the remaining set of sentences satisfiable. Computational experience with both algorithms is reported on. (C) 1998 Published by Elsevier Science B.V.
Subject: linear programming
mixed-integer programming
column generation
maximum satisfiability
probabilistic satisfiability
Country: Holanda
Editor: Elsevier Science Bv
Rights: fechado
Identifier DOI: 10.1016/S0377-2217(97)00059-3
Date Issue: 1998
Appears in Collections:Unicamp - Artigos e Outros Documentos

Files in This Item:
File Description SizeFormat 
WOS000074332600014.pdf950.08 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.