On the Complexity of Optimization Problems based on Compiled NNF Representations
Optimization is a key task in a number of applications. When the set of feasible solutions under consideration is of combinatorial nature and described in an implicit way as a set of constraints, optimization is typically NP-hard. Fortunately, in many problems, the set of feasible solutions does not often change and is independent from the user's request. In such cases, compiling the set of constraints describing the set of feasible solutions during an off-line phase makes sense, if this compilation step renders computationally easier the generation of a non-dominated, yet feasible solution matching the user's requirements and preferences (which are only known at the on-line step). In this article, we focus on propositional constraints. The subsets L of the NNF language analyzed in Darwiche and Marquis' knowledge compilation map are considered. A number of families F of representations of objective functions over propositional variables, including linear pseudo-Boolean functions and more sophisticated ones, are considered. For each language L and each family F, the complexity of generating an optimal solution when the constraints are compiled into L and optimality is to be considered w.r.t. a function from F is identified.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
CktFormalizer: Autoformalization of Natural Language into Circuit Representations
LLMs can generate hardware descriptions from natural language specifications, but the resulting Verilog often contains width mismatches, combinational loops, and incomplete case logic that pass syntax checks yet fail in …
Homomorphisms and Embeddings of STRIPS Planning Models
Determining whether two STRIPS planning instances are isomorphic is the simplest form of comparison between planning instances. It is also a particular case of the problem concerned with finding an isomorphism between a …
FormAn Efficient Application of Neuroevolution for Competitive Multiagent Learning
Multiagent systems provide an ideal environment for the evaluation and analysis of real-world problems using reinforcement learning algorithms. Most traditional approaches to multiagent learning are affected by long trai…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)A Literature Survey of Benchmark Functions For Global Optimization Problems
Test functions are important to validate and compare the performance of optimization algorithms. There have been many test or benchmark functions reported in the literature; however, there is no standard list or set of b…
global-optimizationSurveySoft Goals Can Be Compiled Away
Soft goals extend the classical model of planning with a simple model of preferences. The best plans are then not the ones with least cost but the ones with maximum utility, where the utility of a plan is the sum of the …