Is discrete optimization the same as integer programming?

Integer programming is one major modeling approach; combinatorial problems can also be expressed and solved through other structures.

Can a problem contain continuous variables too?

Yes. Mixed-integer optimization combines discrete and continuous decisions.

Does an optimizer always prove the best answer?

No. Some algorithms are heuristic, and exact methods may stop before proving optimality. The returned status matters.

AI Glossary / Mathematics and optimization / Intermediate

Discrete optimization

Definition

Discrete optimization chooses the best feasible solution when some or all decisions must come from discrete sets, such as whole numbers, yes/no selections, assignments, or routes. It combines an objective to minimize or maximize with rules defining allowable combinations. The challenge is finding a good combination without necessarily examining every possibility individually.

What it means

Many real decisions cannot be divided arbitrarily. A project is selected or not, a worker receives one assignment, and a route visits locations in a particular order. A continuous value such as “select 0.4 of this indivisible project” may be mathematically convenient but operationally meaningless.

Integer programming represents decisions with integer-valued variables, often including binary zero-or-one choices. Combinatorial optimization also works directly with structures such as matchings, sequences, and paths. Mixed-integer models combine discrete choices with continuous quantities, such as opening a facility and choosing its production volume.

How it works

Translate decisions into variables or combinatorial objects, define the objective, and express feasibility requirements. These might include budgets, capacities, exclusivity, precedence, or coverage. Choose an algorithm suited to the structure rather than assuming every discrete problem needs the same search strategy.

Some important classes have efficient specialized algorithms. Other classes can be computationally difficult, motivating branch-and-bound, dynamic programming, cutting planes, constraint programming, or heuristics. A continuous relaxation can supply a useful bound even when its solution is not directly implementable.

Evaluate the returned solution against the original discrete constraints. Distinguish a feasible candidate from a proven optimum and report any remaining gap. The quality of the mathematical result also depends on whether the objective and constraints faithfully describe the intended decision.

Three practical examples

1. Project selection: choose a portfolio of indivisible initiatives whose total cost fits a budget and whose modeled benefit is as large as possible.

2. Staff assignment: allocate people to tasks while respecting qualifications, workload limits, and mutually exclusive assignments.

3. Routing: select an ordered set of visits that satisfies service requirements and minimizes a defined travel or operating cost.

Think of it this way

Think of choosing pieces for a puzzle under rules about which pieces fit together. The quality of the finished arrangement depends on the combination, not just on whether each individual piece looks attractive.

Unlike a simple physical puzzle, an optimization model may have many valid arrangements with different scores. The scoring rule is designed by people and can omit important considerations; finding its best arrangement does not automatically resolve every business trade-off.

Worked example

Consider an original project-selection problem with budget 7. Project A costs 4 and provides value 7; B costs 3 and provides value 5; C costs 5 and provides value 9. Each project is either fully selected or not selected.

The empty selection has value 0. The single-project choices A, B, and C are feasible with values 7, 5, and 9. Pair A+B costs 7 and provides value 12. A+C costs 9 and B+C costs 8, so both are infeasible. Selecting all three costs 12 and is also infeasible.

Thus A+B is the exact best discrete selection, with value 12. This is a complete enumeration of all eight binary combinations, so the conclusion is certified for this small model.

A value-per-cost greedy rule selects C first because 9/5=1.8 exceeds A's 7/4=1.75 and B's 5/3≈1.67. It then has only 2 units of budget left and stops at value 9. The locally attractive first choice misses the best combination.

If fractions were permitted, C plus half of A would cost 7 and provide 12.5. That is feasible for the relaxed model, not for the original indivisible-project decision.

Illustrative case study

Fictional case: Pine Services uses a binary project-selection model to allocate a limited improvement budget. Managers initially expect sorting by benefit-to-cost ratio to be enough, but a small example exposes the interaction between indivisibility and unused budget.

The team checks dependencies and required projects before solving the full model. It presents selected projects, excluded alternatives, and any remaining optimality gap, then tests whether uncertain benefit estimates would change the decision. No actual savings or solver performance is asserted in this scenario.

Common misconceptions and mistakes

Discrete does not mean small. With n independent binary decisions, there are 2ⁿ possible assignments before constraints reduce the search space.

Do not assume greedy choices always work. They are optimal for some structures and fail for others, as the worked portfolio shows.

Rounding a continuous relaxation can violate budgets, coverage, or logical rules and can produce a poor objective. Also, not all discrete problems are equally hard: shortest-path and assignment structures can behave very differently from general integer models.

Business use

Discrete optimization helps make interdependent selections consistently and exposes the cost of constraints. A useful deployment includes clear data ownership, explainable rules, and a process for reviewing infeasibility or unexpected choices.

Validate units, duplicate requirements, and all-or-nothing decisions before solving. Compare the chosen plan with a simple baseline and examine sensitivity to uncertain inputs. If the run ends early, report the best feasible plan and its bound separately. A strong mathematical score should remain traceable to the assumptions that produced it.

Check your understanding

Why does choosing project C first fail in the worked example even though it has the highest value-to-cost ratio?

Answer: C leaves budget 2, insufficient for another whole project. A+B uses the budget completely and provides value 12 rather than 9. The ratio does not capture the effect of indivisible combinations.

Related terms

Binary variable
Dynamic programming
Integer programming
combinatorial optimization
mixed-integer programming
feasible set
knapsack problem
branch-and-bound
continuous relaxation

Learn next

Build a small binary-selection model and enumerate all combinations to check your formulation. Compare it with a greedy rule and a continuous relaxation. Then study one structured problem, such as shortest paths or assignment, to see why exploiting mathematical structure can be more important than using a general-purpose search method.

Shortest Paths

Sources

Primary source: NEOS Guide, “Optimization Problem Types”, https://neos-guide.org/guide/types/ . Its discrete, continuous, integer, and combinatorial distinctions were read. The project table, exhaustive comparison, and fictional scenario are original teaching material; no external company outcomes or solver execution are claimed.

Previous: Discrete Fourier transform Next: Discrete phase-type distribution