A combinatorial optimization problem asks for the best solution among discrete sets, combinations, or permutations. Choosing which parcels to load on a cargo bike is one example; choosing the order in which to visit cities is another. Unlike a continuous variable such as speed, these decisions concern selections or arrangements. section 2.1.1 section 1.3.3
Count the choices before searching
Suppose a fitness plan selects three activities from five. If order does not matter, the plan is a combination: there are 10 choices without repetition, or 35 if activities may repeat. If order matters, the choices are permutations. This distinction determines what counts as a different candidate solution. section 2.1.1
Combinations and permutations—permutations respect order and are thus ordered combinations. Both combinations and permutations have variants with and without repetition.
Use the combinations-and-permutations figure to check whether order and repetition change the solution space. section 2.1.1
A candidate must also be judged against an objective and any constraints. For cargo-bike loading, parcels have profit and weight, while the bike has a capacity. One soft-constraint approach permits an overweight selection but applies a penalty; the penalty can become stricter as a search progresses. In a traveling-salesman problem, candidates are routes through the cities, judged by a criterion such as distance or time. section 1.3.3 section 2.1.1
Machine learning can support the search in three distinct ways:
- Learn to produce a solution directly from a problem instance. section 11.5
- Learn settings for an optimization algorithm, such as a simulated-annealing cooling schedule or genetic-algorithm mutation parameter. section 11.5
- Let an optimization algorithm consult a model repeatedly as its state changes. section 11.5
