Discrete problem

As explained in Optimization Algorithms: AI techniques for design, planning, and control problems

A problem with a finite or countable set of distinct configurations, decisions, or values rather than continuously varying ones.

A discrete problem selects from distinct configurations, decisions, or values rather than continuously varying quantities. In optimization, integer-valued variables define discrete problems; solutions formed from sets, combinations, or permutations are combinatorial problems. section 2.1.1

Classify a problem by the structure of its decisions:

• Use integer or discrete optimization when variables take integer values. section 2.1.1
• Use mixed-integer optimization when continuous and integer decisions appear together, such as elevator motion and passenger-pickup order. section 2.1.1
• Use combinatorial optimization when solutions are sets, combinations, or permutations; order distinguishes permutations from combinations. section 2.1.1

From exercise plans to routes

A weekly fitness plan choosing three activities from five, with repetition allowed, produces 35 combinations. A traveling-salesperson problem instead searches ordered routes through cities, where changing the order changes the solution. Constraint problems provide another form: a 7-queens arrangement is discrete because each queen occupies a position on a discrete chessboard. section 2.1.1 section 6.3

Combinations and permutations—permutations respect order and are thus ordered combinations. Both combinations and permutations have variants with and without repetition.

Compare combinations and permutations visually, including variants with and without repetition. section 2.1.1

How Optimization Algorithms: AI techniques for design, planning, and control problems covers it

How deep it goes

Defines integer, mixed-integer, and combinatorial forms, then illustrates combinations, permutations, routes, and chess configurations.

Examples

Uses fitness-plan combinations, traveling-salesperson routes, delivery routing, and 7-queens configurations.

What it assumes

Assumes basic optimization vocabulary and decision variables while defining the distinction between continuous and discrete choices.

What you can do after

Evaluate optimization models by identifying integer, combinatorial, permutation, or mixed-integer decision structures.

How it connects

Connects discrete problems to continuous optimization, mixed-integer optimization, combinatorial optimization, constraint satisfaction, and metaheuristic search.

liveBookmanning.com

Read Optimization Algorithms: AI techniques for design, planning, and control problems on liveBook Get the book at manning.com

Related concepts

• simulated annealingaddressed by · Simulated annealing is a stochastic optimization method that gradually reduces the probability of accepting worse solutions to escape local optima.
• genetic algorithmused by · A genetic algorithm is an evolutionary optimization method that improves a population of candidate solutions through fitness-based selection and variation, often including recombination and mutation.
• problemkind of · A problem is a difficulty, obstacle, or undesirable condition requiring investigation, mitigation, or resolution.
• discrete variableequivalent to · A discrete variable is a variable whose possible values belong to a finite or countable set of distinct alternatives rather than a continuous range.
• mixed-integer optimization problemincludes · An optimization problem containing both continuous-valued and integer-valued decision variables.

This explainer was generated by Manning's knowledge graph from the text of Optimization Algorithms: AI techniques for design, planning, and control problems. The section links point to the parts of the book it draws on.