3. Search, Optimization, and Constraint Satisfaction

Introduction and Context

Artificial intelligence systems frequently operate in environments where the correct action is not given directly. Instead, the system must discover a sequence of actions, select among competing alternatives, satisfy several conditions simultaneously, or improve a solution through repeated experimentation. Search, optimization, and constraint satisfaction provide the principal computational frameworks for these tasks.

A route-planning system searches through possible journeys. A game-playing program searches through future positions. A university timetable generator seeks an arrangement that satisfies institutional constraints while minimizing conflicts. A machine-learning system may optimize parameters by minimizing a loss function. Although these applications appear different, each involves a state space, possible decisions, evaluation criteria, and computational limits.

Search methods are commonly divided into uninformed and informed approaches. Uninformed search uses only the formal problem definition, whereas informed search uses additional knowledge, usually expressed through a heuristic. Local and metaheuristic methods are useful when the state space is very large and retaining complete search trees is impractical. Adversarial search addresses competition between agents, particularly in games. Constraint-satisfaction techniques represent problems through variables, domains, and constraints. Evolutionary computation and related optimization methods explore populations or neighborhoods of candidate solutions.

The central challenge is not merely to find a solution, but to find one that is correct, efficient, robust, and appropriate to the available computational resources.

Learning Objectives

After completing this chapter, the learner should be able to:

1. Formulate AI problems using states, actions, transition models, goals, and costs.

2. Explain and compare breadth-first, depth-first, uniform-cost, iterative-deepening, greedy, and A* search.

3. Assess heuristic functions using admissibility, consistency, informativeness, and computational cost.

4. Apply local search, simulated annealing, genetic algorithms, and other metaheuristics to optimization problems.

5. Construct game trees and explain minimax decision-making and alpha–beta pruning.

6. Model real problems as constraint-satisfaction problems and apply propagation and backtracking methods.

7. Select algorithms by considering completeness, optimality, time, memory, uncertainty, and problem structure.

8. Identify practical, ethical, and governance issues in automated search and optimization systems.

From Problems to Search Spaces

A search problem is defined by a representation of possible situations and the actions that transform one situation into another. The standard components are:

• Initial state: the situation from which problem solving begins.
• Actions or operators: the legal decisions available in a state.
• Transition model: a description of the state produced by an action.
• Goal test: a procedure that determines whether a state satisfies the objective.
• Path cost: a numerical measure of the resources consumed by a sequence of actions.

A solution is a path from the initial state to a goal state. The quality of a solution may depend on path length, financial cost, energy consumption, risk, execution time, or a weighted combination of these measures.

Consider a delivery vehicle that must visit several customers. If the state records only the current location, the model is incomplete because it does not indicate which customers have already been served. A suitable state might therefore contain the current location and the set of unvisited customers. State representation is a modelling decision: a representation that omits relevant information can produce invalid solutions, while one that includes unnecessary detail can make search expensive.

A search tree records paths generated from the initial state; a state-space graph records distinct states and their connections. Different paths may lead to the same state. Graph-search algorithms therefore maintain an explored set to avoid repeated expansion. Duplicate detection is important in domains such as route planning, puzzle solving, and automated planning, where cycles and alternative paths are common.

The principal measures used to compare search algorithms are:

• Completeness: whether the method is guaranteed to find a solution when one exists.
• Optimality: whether it is guaranteed to find the least-cost solution.
• Time complexity: the number of nodes generated or expanded.
• Space complexity: the amount of memory required.

If the branching factor is represented by b, the depth of the shallowest solution by d, and the maximum depth by m, these parameters help describe theoretical performance, although actual performance also depends on duplicate states, action costs, and heuristic quality.

Uninformed Search: Systematic Exploration

Uninformed, or blind, search has no domain-specific estimate of the distance to a goal. It relies on the problem definition and a frontier data structure.

Breadth-first search (BFS) expands the shallowest nodes first. With equal action costs, it is complete and optimal because the first goal encountered has the smallest number of actions. Its principal disadvantage is memory consumption: all nodes at a given depth may need to remain in the frontier.

Depth-first search (DFS) follows one branch as deeply as possible before backtracking. It uses relatively little memory, but it is not generally optimal and may fail to terminate in an infinite or cyclic space unless suitable safeguards are used. DFS can be appropriate when solutions are expected to be deep and memory is severely constrained, but it is dangerous when shallow solutions are preferred.

Uniform-cost search (UCS) expands the frontier node with the lowest accumulated path cost, usually denoted g(n). It is complete and optimal when every step cost is positive and a minimum positive cost exists. UCS is appropriate when actions have unequal costs; BFS is not, because few actions do not necessarily mean low cost.

Depth-limited search imposes a maximum depth on DFS. It prevents infinite descent but may miss solutions below the limit. Iterative-deepening depth-first search (IDDFS) repeatedly applies depth-limited search with increasing limits. It combines the low memory requirement of DFS with the completeness and, under equal costs, optimality of BFS. Repeated expansion of shallow nodes is usually acceptable because most nodes lie near the deepest explored level.

A practical comparison is useful. Suppose a network contains a direct route requiring four expensive actions and an alternative route requiring seven inexpensive actions. BFS may select the four-action route, whereas UCS selects the route with the lower total cost. The choice of algorithm must therefore follow the meaning of “best.”

Informed Search and the Design of Heuristics

Informed search uses an estimate of the remaining cost. A heuristic function h(n) estimates the cost from node n to a goal. The evaluation function used by A* is:

f(n) = g(n) + h(n)

where g(n) is the cost already incurred and h(n) is the estimated cost remaining. A* balances progress from the initial state with estimated progress toward the goal.

A heuristic is admissible if it never overestimates the true remaining cost. For example, straight-line distance is admissible for road travel when the actual route cannot be shorter than a direct geometric distance. With an admissible heuristic and suitable graph-search conditions, A is optimal. A heuristic is consistent, or monotonic, if for every action from n to n′*,

h(n) ≤ cost(n,n′) + h(n′).

Consistency implies admissibility and ensures that the estimated total cost does not decrease along a path. It also allows graph-search A* to avoid reopening already expanded nodes in standard settings.

A heuristic can be admissible but weak. The trivial heuristic h(n)=0 is admissible and reduces A* to UCS. A stronger heuristic usually reduces node expansion, but calculating it may be expensive. Heuristic design is therefore an engineering trade-off between search guidance and evaluation cost.

Useful heuristics are often derived by relaxing the original problem. If a puzzle is simplified by ignoring obstacles or allowing an action that is not actually legal, the cost of the relaxed problem can provide a lower bound for the original problem. Multiple admissible heuristics can sometimes be combined using their maximum; the maximum remains admissible and is at least as informative as each individual heuristic.

Greedy best-first search selects the node with the smallest h(n). It may reach a goal quickly, but it ignores the cost already paid and is not generally optimal or complete in unrestricted spaces. A* is more cautious because it considers both accumulated and estimated cost.

In practical systems, heuristic quality should be evaluated empirically as well as theoretically. Important measures include the number of expanded nodes, solution cost, planning time, and sensitivity to unusual instances. A heuristic that performs well on average may still be unsafe where worst-case guarantees are required.

Local Search and Metaheuristic Optimization

Many optimization problems have enormous or continuous state spaces. Maintaining a complete frontier is then infeasible. Local search begins with one or more candidate solutions and repeatedly moves to alternatives in their neighborhoods. It is especially useful when the objective is to locate a high-quality solution rather than to prove global optimality.

Hill climbing moves from the current state to a better neighboring state. Variants include steepest-ascent, which examines all available neighbors and chooses the best, and stochastic hill climbing, which selects a promising neighbor probabilistically. Hill climbing can become trapped at a local optimum, plateau, or ridge. Random restart hill climbing addresses some of these difficulties by conducting multiple searches from different initial states.

Simulated annealing occasionally accepts a worse move. The probability of accepting a deterioration is commonly related to a temperature parameter that decreases over time. Early exploration reduces the chance of becoming trapped; later exploitation concentrates the search around good regions. Its performance depends strongly on the cooling schedule, neighborhood structure, and stopping rule.

Tabu search records recently visited solutions or moves in a tabu list to discourage cycling. It can accept non-improving moves and uses memory to explore beyond local optima. The tabu tenure must be chosen carefully: a short tenure may permit cycling, while a long tenure can exclude useful regions.

Beam search retains only a fixed number of the most promising states at each level. It reduces memory compared with exhaustive methods but may discard the path leading to the best solution. Beam width is therefore a key quality–resource parameter.

Optimization objectives may be single or multi-objective. In multi-objective optimization, improving one criterion may worsen another, producing a set of Pareto-optimal solutions. For example, a data-centre schedule may trade energy consumption against latency. A weighted sum is simple but requires meaningful weights; Pareto methods preserve alternatives for later decision-making.

Evolutionary Computation

Evolutionary algorithms treat candidate solutions as a population. A typical genetic algorithm follows this cycle:

1. Generate an initial population.

2. Evaluate each individual using a fitness function.

3. Select individuals with greater reproductive potential.

4. Apply crossover to combine selected representations.

5. Apply mutation to introduce variation.

6. Form the next generation and repeat until a stopping condition is met.

The representation is crucial. A binary chromosome may encode a subset-selection problem, while a permutation is appropriate for a travelling-salesperson tour. Operators must preserve meaningful structure. Ordinary crossover on permutations can create invalid tours unless it is specially designed.

Selection pressure affects diversity. Strong pressure accelerates exploitation but may cause premature convergence. Mutation maintains variation but excessive mutation can turn the algorithm into random search. Elitism preserves high-quality solutions but can further reduce diversity.

The fitness function may include penalties for violating constraints. Penalty design is difficult: an inadequate penalty permits infeasible solutions, whereas an excessive penalty can prevent exploration of promising regions. Hybrid approaches, often called memetic algorithms, combine evolutionary search with local improvement.

Evolutionary algorithms do not generally guarantee an optimal solution in finite practical time. Their value lies in robust exploration of difficult, discontinuous, noisy, or combinatorial landscapes. Reproducibility requires recording random seeds, population settings, operators, stopping criteria, and evaluation data.

Adversarial Search: Decision-Making Against an Opponent

In single-agent search, the environment is usually treated as passive. In adversarial search, another agent actively attempts to reduce the quality of the first agent’s outcome. A game tree represents alternating decisions.

For a two-player, zero-sum, deterministic, perfect-information game, minimax assigns utility to terminal positions. MAX chooses an action that maximizes the eventual utility, while MIN chooses an action that minimizes it. The value of a node is computed recursively:

• At a MAX node, select the maximum child value.
• At a MIN node, select the minimum child value.
• At a terminal node, return its utility.

Minimax is optimal when the complete game tree is available and both players act rationally. In realistic games, complete expansion is impossible. The system therefore searches to a depth limit and applies an evaluation function to nonterminal positions. A good evaluation function correlates with winning chances and reflects strategically relevant features rather than superficial signals.

Alpha–beta pruning improves minimax without changing its result. Alpha is the best value MAX can guarantee along the current path; beta is the best value MIN can guarantee. A branch can be pruned when it cannot influence the final decision, typically when alpha is greater than or equal to beta. The benefit depends on move ordering. With excellent ordering, alpha–beta can examine far fewer nodes; with poor ordering, the result approaches ordinary minimax.

Iterative deepening searches successively greater depths and uses earlier results to order moves. This is valuable when a fixed time limit applies. Transposition tables store values for positions reached through different move sequences. In games involving chance, such as backgammon, expectiminimax incorporates chance nodes and probability-weighted expected values.

Game-playing systems also face horizon effects, where a harmful consequence lies just beyond the search depth. Quiescence search extends analysis of unstable positions, such as those involving immediate captures, before evaluation is applied.

Constraint-Satisfaction Problems

A constraint-satisfaction problem (CSP) consists of variables, domains, and constraints. Variables represent unknowns, domains specify possible values, and constraints define permitted combinations. A solution assigns a value to every variable while satisfying all constraints.

In map colouring, regions are variables, colours are domains, and neighboring regions must receive different colours. In examination scheduling, examinations, rooms, and time slots can be represented through variables and domains, with constraints involving student conflicts, room capacity, invigilation, and availability.

CSP solving commonly uses backtracking search. A partial assignment is extended by selecting an unassigned variable and trying a domain value. If a constraint is violated, the algorithm backtracks. Intelligent variable and value ordering can greatly reduce search:

• Minimum remaining values (MRV): choose the variable with the smallest remaining domain.
• Degree heuristic: among tied variables, choose the one constraining the greatest number of others.
• Least-constraining value: try the value that eliminates the fewest options for neighboring variables.

Constraint propagation detects failure earlier. Forward checking removes values from neighboring domains after each assignment. Arc consistency requires that every value in one variable’s domain has a compatible value in the connected variable’s domain. The AC-3 algorithm repeatedly revises arcs until no more values can be removed or a domain becomes empty.

Hard constraints must be satisfied; soft constraints express preferences and may be optimized. Weighted CSPs assign costs to violations, while constraint optimization problems search for the least-cost feasible assignment. In practice, scheduling often uses a combination of propagation, backtracking, integer programming, and local repair.

CSPs differ from ordinary path-search problems because the order in which variables are assigned usually does not define the final solution. This makes propagation and structural analysis particularly important. If the constraint graph is sparse, decomposition may permit independent subproblems. Tree-structured CSPs can often be solved more efficiently than densely connected ones.

An Illustrative Case Study: University Examination Timetabling

Background

Consider a fictional public university that must schedule end-semester examinations for several thousand students. Each examination requires a room and time slot, and students may be enrolled in multiple examinations.

Situation and Problem

The timetable must satisfy hard constraints: a student cannot sit two examinations simultaneously; a room cannot exceed its capacity; examinations requiring special equipment need suitable rooms; and designated periods may be unavailable. The university also wants to minimize consecutive examinations for students, distribute large examinations across the week, and use rooms efficiently.

Analysis

A naive approach generates complete timetables and tests them afterward. This is computationally wasteful because most partial assignments already contain conflicts. The problem is naturally modelled as a CSP. Examination events are variables, time-room combinations are domain values, and student conflicts, capacity, equipment, and availability are constraints. Soft preferences are represented by penalties.

The conflict graph is constructed by connecting examinations sharing at least one student. Examinations with high degree are highly constrained and should be assigned early. MRV identifies events with few feasible slots, while the degree heuristic breaks ties. Forward checking removes incompatible slots from neighboring examinations. A repair-based local search can then improve the feasible timetable by swapping rooms or periods.

Approach and Solution

The university first applies hard-constraint propagation to reduce domains. A backtracking solver assigns the most constrained examination next and uses least-constraining values to preserve flexibility. Once a feasible schedule is found, simulated annealing explores swaps that reduce soft-constraint penalties. A large penalty is assigned to hard violations, but a separate feasibility checker ensures that no final timetable contains them.

The system records the reason for each rejection, enabling timetable administrators to diagnose bottlenecks. Human staff review the final Pareto alternatives, choosing between lower room utilization and fewer student back-to-back examinations.

Outcome

The illustrative system produces a feasible timetable and several alternatives rather than presenting one unexplained answer. The decision-makers retain control over policy choices, such as whether student convenience should outweigh room utilization.

Learning Points

The case demonstrates that modelling precedes algorithm selection. Constraint propagation is more useful than blind enumeration when conflicts are explicit. Optimization should occur after, or jointly with, feasibility management. Finally, human-readable explanations and policy controls are essential when algorithmic schedules affect many people.

Choosing Methods in Professional Practice

Algorithm selection should begin with the structure of the task. If actions have uniform cost and a shallow solution is desired, BFS or IDDFS may be suitable. If action costs differ, UCS is safer. If a reliable lower-bound heuristic exists, A* can provide optimal solutions with much less exploration. If the state space is too large for systematic search and approximate quality is acceptable, local or evolutionary methods may be preferable.

For adversarial decisions, minimax with alpha–beta pruning is appropriate for deterministic, competitive settings, whereas stochastic or imperfect-information environments require extensions such as expectiminimax, belief-state search, or simulation-based methods. CSP techniques are particularly suitable when the solution is an assignment subject to explicit relations rather than a path through sequential states.

Operational systems should define stopping criteria, time limits, fallback behaviour, and monitoring metrics. Important metrics include solution quality, feasibility rate, runtime, memory usage, stability across runs, and sensitivity to input changes. In high-stakes contexts, a system should be tested on rare and adverse instances, not only average cases.

Challenges, Risks, and Limitations

Search algorithms can suffer from combinatorial explosion. A small increase in variables or branching factor may make exhaustive methods unusable. Poor state representations create redundant work, while weak heuristics provide little guidance. Local and evolutionary methods may return different results on different runs and may offer no proof of global optimality.

Objective functions can also distort behaviour. An optimization system improves what is measured, not necessarily what an organization truly values. A scheduling model that rewards room utilization may create unacceptable student workloads if those effects are omitted. Penalties can hide priorities and make outcomes difficult to explain.

Common implementation mistakes include confusing path cost with depth, using inadmissible heuristics while claiming optimality, failing to detect duplicate states, applying genetic operators that produce invalid representations, and treating all constraints as equally important. In game search, poor evaluation functions and weak move ordering can produce strategically unsound decisions.

Ethical, Governance, and Professional Considerations

Automated optimization can distribute opportunities, costs, and inconvenience. Timetabling, staff rostering, admissions, and resource allocation may affect individuals unequally. Developers should identify stakeholders, document objective functions, test for systematic disadvantage, and provide mechanisms for review and appeal.

Explainability is particularly important where a solution is imposed by an institution. The system should distinguish hard constraints from preferences and report infeasibility when no valid solution exists rather than silently relaxing important rules. Data used to construct constraints must be protected, especially when it reveals health, disability, employment, or educational information.

Professional governance also requires version control for models, reproducible experiments, audit logs, access controls, and monitoring after deployment. Human oversight is not merely a communication feature; it is a safeguard against incorrect assumptions and unforeseen consequences.

Current Developments and Best Practices

Modern systems increasingly combine exact and approximate methods. Constraint programming, mixed-integer optimization, SAT solving, heuristic search, and machine learning may be used together. Learned heuristics can estimate promising actions from previous instances, but they require validation because distribution shifts may make them unreliable.

Parallel search distributes frontier nodes, population evaluations, or neighborhood exploration across processors. Cloud and GPU infrastructures support large-scale simulation and evolutionary evaluation, although communication overhead can reduce gains. Neural systems are also being used to guide tree search, as in learned policy and value estimation, while classical search provides structure and verification.

Strong practice includes:

• define the objective and constraints before selecting an algorithm;
• separate feasibility from preference optimization;
• use benchmark instances and meaningful baselines;
• record assumptions, random seeds, parameters, and stopping rules;
• test robustness under changed costs, constraints, and incomplete data;
• report solution quality together with runtime and resource consumption;
• preserve human review for consequential decisions;
• use exact methods where guarantees matter and metaheuristics where scale makes approximation necessary.

Chapter Summary

Search formulates problem solving as movement through a state space defined by an initial state, actions, transitions, goals, and costs. Uninformed methods such as BFS, DFS, UCS, and IDDFS differ in completeness, optimality, time, and memory. Informed methods use heuristics; A* combines accumulated cost with estimated remaining cost and can be optimal when its heuristic satisfies appropriate conditions.

Local search and metaheuristics address large optimization spaces through neighborhoods, controlled randomness, memory, or populations. Genetic algorithms use selection, crossover, and mutation, but their effectiveness depends on representation, diversity, and fitness design. Adversarial search models competing agents through minimax, with alpha–beta pruning reducing computation without changing the result. CSPs represent variables, domains, and constraints, and are solved using backtracking, propagation, and intelligent ordering. Across all methods, modelling, objective design, resource limits, validation, explainability, and human governance are as important as algorithmic sophistication.

Key Terms

Admissible heuristic: A heuristic that never overestimates the true remaining cost to a goal.

Alpha–beta pruning: A minimax technique that removes branches unable to affect the final decision.

Arc consistency: A property in which every value of a variable has compatible values in connected variables.

Backtracking: A systematic method that reverses earlier assignments when a partial solution cannot be extended.

Constraint-satisfaction problem: A problem defined by variables, domains, and constraints on allowable assignments.

Consistency: A heuristic property ensuring that estimated costs obey a local triangle inequality.

Evaluation function: A function estimating the value of a nonterminal state, especially in game search.

Fitness function: A measure of candidate quality in an evolutionary algorithm.

Frontier: The collection of generated but not yet expanded search nodes.

Genetic algorithm: A population-based optimization method using selection, crossover, and mutation.

Goal test: A procedure that determines whether a state satisfies the problem objective.

Heuristic: Domain-informed knowledge used to guide search.

Hill climbing: A local search method that repeatedly moves toward a better neighboring state.

Minimax: An adversarial decision rule in which one player maximizes utility and the opponent minimizes it.

Metaheuristic: A general strategy for guiding approximate search across difficult optimization spaces.

Path cost: The cumulative cost of actions along a search path.

Pareto-optimal solution: A solution that cannot improve one objective without worsening another.

Propagation: The removal of domain values that cannot participate in any valid assignment.

State space: The set of possible states and transitions relevant to a problem.

Uniform-cost search: Search that expands the node with the lowest accumulated path cost.

Review Questions

Short Answer Questions

1. What are the five basic components of a search problem?

2. Why is uniform-cost search preferable to breadth-first search when action costs differ?

3. Define an admissible heuristic and explain its significance for A*.

4. What is the purpose of forward checking in a constraint-satisfaction problem?

5. How does alpha–beta pruning preserve the result of minimax?

Long Answer Questions

1. Compare BFS, DFS, UCS, and IDDFS with respect to completeness, optimality, time, and memory.

2. Explain A search in detail, including the roles of g(n), h(n)*, admissibility, and consistency.

3. Discuss the design choices and failure modes of hill climbing, simulated annealing, and genetic algorithms.

4. Explain minimax search, evaluation functions, depth limits, move ordering, and alpha–beta pruning.

5. Describe CSP modelling and explain how MRV, degree heuristics, least-constraining values, and arc consistency work together.

Analytical / Application Questions

1. A logistics problem has unequal action costs and a reliable lower-bound estimate of remaining fuel use. Which search method would you select, and what conditions would be required for an optimal result?

2. Design a CSP formulation for allocating employees to shifts when availability, qualifications, staffing levels, and fairness preferences must be considered. Identify hard and soft constraints.

3. A genetic algorithm repeatedly converges to similar mediocre solutions. Analyze at least three possible causes and propose corrective changes to representation, selection, mutation, or population management.

22. Multiple Choice Questions with Answers

Question 1

Which search method is guaranteed to find a least-cost solution when all action costs are positive, even when costs are unequal?

A. Depth-first search

B. Uniform-cost search

C. Greedy best-first search

D. Hill climbing

Correct Answer: B. Uniform-cost search

Question 2

For A* graph search, which property of a heuristic ensures that estimated costs do not decrease along a path?

A. Randomness

B. Completeness

C. Consistency

D. Branching

Correct Answer: C. Consistency

Question 3

A route planner uses straight-line distance as a heuristic for road travel. Why can this heuristic be admissible?

A. Road routes cannot be shorter than the direct geometric distance

B. It always equals the actual road distance

C. It ignores the accumulated path cost

D. It guarantees that every route has equal cost

Correct Answer: A. Road routes cannot be shorter than the direct geometric distance

Question 4

Which technique is most directly intended to escape a local optimum by occasionally accepting a worse move?

A. Uniform-cost search

B. Simulated annealing

C. Arc consistency

D. Minimax

Correct Answer: B. Simulated annealing

Question 5

At a MIN node in a minimax game tree, the algorithm selects the child with:

A. The highest utility for MAX

B. The lowest utility for MAX

C. The lowest branching factor

D. The greatest path depth

Correct Answer: B. The lowest utility for MAX

Question 6

Alpha–beta pruning is correct because a pruned branch:

A. Has already been shown to contain a goal state

B. Cannot change the backed-up minimax decision

C. Always has a higher evaluation than the current move

D. Contains no legal actions

Correct Answer: B. Cannot change the backed-up minimax decision

Question 7

In a CSP, the minimum-remaining-values heuristic selects:

A. The variable with the largest domain

B. The variable with the smallest remaining domain

C. The least-constraining value

D. The variable assigned most recently

Correct Answer: B. The variable with the smallest remaining domain

Question 8

What is the principal purpose of forward checking?

A. To expand every possible complete assignment

B. To remove incompatible values from neighboring domains after an assignment

C. To guarantee global optimality in every CSP

D. To replace all hard constraints with soft constraints

Correct Answer: B. To remove incompatible values from neighboring domains after an assignment

Question 9

A genetic algorithm produces invalid permutations after crossover. The most appropriate response is to:

A. Use representation-specific crossover or repair operators

B. Remove the fitness function

C. Increase the search depth of minimax

D. Apply breadth-first search to the population

Correct Answer: A. Use representation-specific crossover or repair operators

Question 10

In the examination-timetabling case, why should hard feasibility constraints be separated from soft preferences?

A. Soft preferences are always more important than feasibility

B. It prevents the system from treating an invalid timetable as acceptable merely because it scores well

C. It eliminates the need for search

D. It guarantees that all objectives have identical weights

Correct Answer: B. It prevents the system from treating an invalid timetable as acceptable merely because it scores well