The exponentiated subgradient algorithm for heuristic Boolean programming

摘要: Boolean linear programs (BLPs) are ubiquitous in AI. Satisfiability testing, planning with resource constraints, and winner determination combinatorial auctions all examples of this type problem. Although increasingly well-informed by work OR, current AI research has tended to focus on specialized algorithms for each BLP task only loosely patterned new effective methods from other tasks. In paper we introduce a single general-purpose local search procedure that can be simultaneously applied the entire range problems, without modification. one might suspect algorithm not perform as well algorithms, find is case here. Our experiments show our generic achieves performance comparable state art satisfiability auctions-- two very different problems. simple, combines an old idea OR recent ideas