A production planner may have hundreds of jobs to arrange, each with its own requirements. In principle, the planner could compare every possible schedule and select the best. In practice, there are far too many arrangements, and the answer is needed long before exhaustive comparison could finish.
The remarkable thing about optimization algorithms is how much they can accomplish without looking at everything. They use information about the problem to decide where to begin, what to change and which possibilities can safely be left unexplored. Sometimes that information comes from a simple practical rule. Sometimes it comes from a mathematical argument strong enough to eliminate thousands or millions of choices at once.
Build a useful starting point
One way to approach a scheduling problem is to construct a plan a job at a time. We might start with work that has an early deadline, then assign the next job to a suitable machine and continue until the schedule is complete. A vehicle-routing method might similarly extend a route by choosing the next promising customer.
These are construction heuristics: methods that build a candidate solution through a sequence of choices. A good construction heuristic can produce a useful plan quickly, especially when each choice takes operational constraints into account. But it does not necessarily produce the best plan. A job selected early may occupy the machine another job urgently needs, while a locally convenient delivery stop may make the remaining route awkward.
The point is not that the simple rule is foolish. It has done something valuable: turned an enormous space of possibilities into one concrete plan we can examine. Now there is something to improve.
Improve what you already have
Improvement heuristics start with an existing solution and look for changes that make it better. In a production schedule, the algorithm might exchange two jobs, move one task to a different position or rearrange a group of related jobs. It evaluates the consequences and keeps useful changes, perhaps repeating the process many times.
If every remaining changeover takes nonnegative time, finishing that candidate cannot produce a better answer.
The set of solutions reachable through a chosen kind of change is called a neighborhood. If the allowed move is swapping two jobs, the neighborhood consists of schedules produced by those swaps. If the algorithm can instead rearrange an entire block of work, it explores a different neighborhood. The choice matters: small moves are often cheap to evaluate, but an improvement that requires several coordinated changes may be invisible to them.
Local search is a familiar improvement approach. It explores neighborhoods of a current solution, moving toward attractive alternatives. More elaborate methods may change neighborhoods, accept temporary setbacks or restart from another part of the search space to avoid becoming trapped near a mediocre solution. Many practical algorithms combine construction and improvement, building a reasonable plan quickly and then refining it.
Know when a possibility cannot win
Some algorithms can do more than identify promising changes. They can prove that certain alternatives are not worth considering.
Suppose we are minimizing the total changeover time between production jobs, and we already have a complete schedule requiring 35 minutes of changeovers. Another candidate has accumulated 40 minutes before all its jobs have even been placed. If every remaining changeover takes nonnegative time, finishing that candidate cannot produce a better answer. The algorithm can abandon that entire line of search.
This is pruning. Sophisticated methods derive stronger mathematical bounds, often by solving a simplified version of the problem. Branch-and-bound algorithms use such information to explore alternatives selectively and discard groups of solutions that cannot beat the best result already found. When the necessary conditions hold and the search completes, the result can include a proof of optimality.
Other problems allow similarly powerful methods because of properties that are less obvious when the problem is described in ordinary language.
There is an important distinction here. A heuristic may skip a region because experience suggests it is unlikely to help. A bound can establish that the region cannot help. Both kinds of information are useful, but only the second supports that particular mathematical guarantee.
Sometimes the problem gives away more structure
Not every optimization problem needs an elaborate search. For shortest paths in a graph with nonnegative edge costs, specialized algorithms can exploit the graph's structure to find an optimal route efficiently. They do not have to enumerate all possible paths. Other problems allow similarly powerful methods because of properties that are less obvious when the problem is described in ordinary language.
This is why two models containing similar numbers of decisions can behave very differently. The number of possibilities matters, but so does the structure connecting them. A good formulation can expose relationships that make the search dramatically more effective.
What makes a better algorithm?
An improvement can take several forms. An algorithm might reach a strong feasible solution sooner, find a better solution within the same time limit or establish a tighter bound on how far the current result could be from optimal. Which improvement matters depends on the application. A live scheduling service may need a useful answer in seconds; a major one-off planning decision may justify a longer computation.
Algorithm development is therefore partly the art of choosing where computation should go. A construction heuristic gives the search a starting point. An improvement heuristic explores alternatives close to or deliberately far from that point. Mathematical bounds prevent effort from being wasted where an improvement is impossible. The strongest systems often bring these ideas together.
The goal is not to search every possibility faster. It is to learn enough about the problem that most possibilities never need to be searched at all.
Continue learning
New to Optimization, part 5 of 6. Previous: Variables, constraints and objectives. Next: Your first optimization model. View the full learning path.