[go: up one dir, main page]

Lagoudakis et al., 2001 - Google Patents

Learning to select branching rules in the DPLL procedure for satisfiability

Lagoudakis et al., 2001

View PDF
Document ID
10655695340460356395
Author
Lagoudakis M
Littman M
Publication year
Publication venue
Electronic Notes in Discrete Mathematics

External Links

Snippet

The DPLL procedure is the most popular complete satisfiability (SAT) solver. While its worst case complexity is exponential, the actual running time is greatly affected by the ordering of branch variables during the search. Several branching rules have been proposed, but none …
Continue reading at www.cs.ubc.ca (PDF) (other versions)

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06N—COMPUTER SYSTEMS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N3/00—Computer systems based on biological models
    • G06N3/12—Computer systems based on biological models using genetic models
    • G06N3/126—Genetic algorithms, i.e. information processing using digital simulations of the genetic system
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06Q—DATA PROCESSING SYSTEMS OR METHODS, SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL, SUPERVISORY OR FORECASTING PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL, SUPERVISORY OR FORECASTING PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q10/00—Administration; Management
    • G06Q10/06—Resources, workflows, human or project management, e.g. organising, planning, scheduling or allocating time, human or machine resources; Enterprise planning; Organisational models
    • G06Q10/063—Operations research or analysis
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06N—COMPUTER SYSTEMS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N5/00—Computer systems utilising knowledge based models
    • G06N5/02—Knowledge representation
    • G06N5/022—Knowledge engineering, knowledge acquisition
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06N—COMPUTER SYSTEMS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N5/00—Computer systems utilising knowledge based models
    • G06N5/04—Inference methods or devices
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/50—Computer-aided design
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for programme control, e.g. control unit
    • G06F9/06—Arrangements for programme control, e.g. control unit using stored programme, i.e. using internal store of processing equipment to receive and retain programme
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F17/00—Digital computing or data processing equipment or methods, specially adapted for specific functions
    • G06F17/30—Information retrieval; Database structures therefor; File system structures therefor
    • G06F17/30943—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type
    • G06F17/30946—Information retrieval; Database structures therefor; File system structures therefor details of database functions independent of the retrieved data type indexing structures
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06Q—DATA PROCESSING SYSTEMS OR METHODS, SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL, SUPERVISORY OR FORECASTING PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL, SUPERVISORY OR FORECASTING PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q10/00—Administration; Management
    • G06Q10/04—Forecasting or optimisation, e.g. linear programming, "travelling salesman problem" or "cutting stock problem"
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06Q—DATA PROCESSING SYSTEMS OR METHODS, SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL, SUPERVISORY OR FORECASTING PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL, SUPERVISORY OR FORECASTING PURPOSES, NOT OTHERWISE PROVIDED FOR
    • G06Q10/00—Administration; Management
    • G06Q10/10—Office automation, e.g. computer aided management of electronic mail or groupware; Time management, e.g. calendars, reminders, meetings or time accounting
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06N—COMPUTER SYSTEMS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N99/00—Subject matter not provided for in other groups of this subclass
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING; COUNTING
    • G06F—ELECTRICAL DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled

Similar Documents

Publication Publication Date Title
Lagoudakis et al. Learning to select branching rules in the DPLL procedure for satisfiability
US6031984A (en) Method and apparatus for optimizing constraint models
Walser Integer optimization by local search: A domain-independent approach
Wei et al. A new approach to model counting
Scrich et al. Tardiness minimization in a flexible job shop: A tabu search approach
Baker et al. Search based approaches to component selection and prioritization for the next release problem
Marques-Silva The impact of branching heuristics in propositional satisfiability algorithms
Kheiri et al. A sequence-based selection hyper-heuristic utilising a hidden Markov model
Kianfar et al. Study of stochastic sequence-dependent flexible flow shop via developing a dispatching rule and a hybrid GA
Kroese et al. Network reliability optimization via the cross-entropy method
US20090228414A1 (en) Systems and methods for applying evolutionary search to generate robust search strategies
Tsang et al. A family of stochastic methods for constraint satisfaction and optimization
Giunchiglia et al. Evaluating search heuristics and optimization techniques in propositional satisfiability
Mamoulis et al. Algorithms for quantified constraint satisfaction problems
Sun et al. A light-robust-optimization model and an effective memetic algorithm for an open vehicle routing problem under uncertain travel times
Fanti et al. Genetic multi-criteria approach to flexible line scheduling
Kapsalis et al. The radio link frequency assignment problem: A case study using genetic algorithms
Perez-Salazar et al. Adaptive bin packing with overflow
Cicirello Weighted tardiness scheduling with sequence-dependent setups: a benchmark library
Leucker et al. Parallel Model Checking for LTL, CTL∗, and L2μ
Voudouris et al. Guided local search joins the elite in discrete optimisation
Kern-Isberner Solving the inverse representation problem
Galli Algorithms for integer programming
Beccuti et al. Efficient simulation of stochastic well-formed nets through symmetry exploitation
Kato et al. Cost-based abduction using binary decision diagrams