definition · term 12 of 25
NP-hard.
A class of problems for which no known algorithm finds a proven optimum in polynomial time. Effort can grow exponentially with size.
worked exampleone more stop, many more routesA sequence of 10 stops has about 3.6 million orders. With 15 stops it is about 1.3 trillion. Effort can grow that fast, which is why a stated gap matters.
in plain language
Routing, scheduling and bin packing are NP-hard. That does not mean they cannot be solved. It means no shortcut is known that works for every instance. In practice, exact methods with strong pruning solve many real instances to proven optimality. For the rest, they report how close the best plan found is.
NP-hard, on your own decision.
Bring one recurring decision. Your planners see the terms of this glossary applied to their own rules and data.
- Glossary
- all 25 terms, a to z
- Problem types
- the decisions kint solves
- Comparisons
- kint next to other approaches
- Contact
- hello@kint.pro