What is brute force search?
Brute force search is a method that solves a problem by generating every possible candidate and checking each one. It is simple to write, easy to verify, and guaranteed to find the best answer. Its cost is time. The number of candidates in most real problems grows explosively with size, so a method that finishes in seconds on a small case may never finish on a slightly larger one.
Sequencing ten jobs on one machine has about 3.6 million possible orders, which a laptop checks in seconds. Sequencing twenty jobs has over two quintillion possible orders, beyond any computer. The second problem has the same shape as the first, but brute force no longer applies, which is what intractable means in practice.
Brute force search in practice
Several machine learning tools are brute force under another name. Grid search tries every combination of hyperparameter values. Exact nearest neighbor search compares a query against every stored vector, which is why vector databases use approximate indexes once collections grow. In production scheduling, routing, and inventory planning, real sizes rule out exhaustive search, so vendors use optimization solvers, heuristics, and pruning methods that discard most candidates unexamined.
What to watch for
- For small problems, brute force is the right answer and a useful check on anything cleverer.
- Ask a scheduling or routing vendor how far from optimal its heuristic can be.
- Accept a near-optimal answer in minutes over an exact one that takes days, and record the gap.