Is an objective enough to define the problem?

No. The permitted domain and constraints determine which decisions can be compared.

Can a feasible answer still be poor?

Yes. Feasibility only means the restrictions are satisfied; it does not mean the objective is good.

Can changing one constraint change the best answer?

Yes. It can change the optimum, create several optima, or make the problem infeasible.

AI Glossary / Mathematics and optimization / Intermediate

Optimization problem

Definition

An optimization problem is a mathematical specification of decisions to be chosen, an objective to minimize or maximize, and the set of permitted choices. A solution is a feasible decision attaining the desired best value, when such a decision exists. The problem defines the target; an optimization method supplies a procedure for seeking a solution.

What it means

A common notation is “minimize f(w) subject to w belonging to W.” Here w is the decision variable, f is the objective function, and W is the feasible set. Fixed data, such as demand forecasts or observed training examples, help define f and W but are not themselves decisions unless the formulation explicitly makes them so.

The minimizing decision and the minimum objective value are different objects. A staffing problem can return a schedule and its cost. Two schedules may share the same minimum cost, so a unique objective value does not necessarily identify one unique decision.

How it works

Build the formulation by stating the variables and their units. Write the objective in those variables and specify equality, inequality, and domain restrictions. Nonnegativity, integrality, and probability-sum constraints all change what counts as an allowed answer.

Examine the feasible set before choosing a solution method. If no point satisfies all requirements, the problem is infeasible. If the objective can decrease without limit, a minimization problem is unbounded below. A finite lower limit may also exist without being attained: minimizing w over w > 0 has infimum zero but no minimizing feasible w.

Classify useful structure, such as linearity or convexity, and consider whether a reformulation preserves the original decisions and objective. Relaxing an integer restriction can provide a useful bound, but its fractional answer is not automatically a solution to the original problem.

Three practical examples

1. Model fitting: choose coefficients to minimize prediction loss on specified data, possibly with constraints or a regularization term.

2. Shift planning: choose whole numbers of staff assigned to shifts, requiring minimum coverage and respecting availability.

3. Mixture design: choose nonnegative proportions that sum to one while meeting composition limits and minimizing ingredient cost.

Think of it this way

Think of a contest rulebook that defines legal entries and how they are scored. The optimization problem is the rulebook; the optimization method is a participant's strategy for producing an entry. A beautifully executed strategy cannot fix missing rules, and the highest score under the rulebook may omit qualities the organizers forgot to include.

Worked example

A workshop makes standard packs x and premium packs y. Suppose each standard pack earns 3 units of contribution and each premium pack earns 5. Available packing time imposes x + 2y ≤ 8, and a separate handling limit imposes x + y ≤ 5. Both variables must be nonnegative integers.

The problem is to maximize 3x + 5y under those restrictions. For each possible y, the best x is the largest allowed nonnegative integer, because its contribution is positive.

If y = 0, x may be 5, giving contribution 15. If y = 1, x may be 4, giving 17. For y = 2, x may be 3, giving 19. For y = 3, x may be 2, giving 21. For y = 4, x must be 0, giving 20. Larger y violates the packing-time limit.

Thus the unique best integer plan is x = 2, y = 3, with objective value 21. It uses all 8 packing-time units and all 5 handling units. The proposed plan x = 1, y = 4 earns 23 but uses 9 packing-time units, so it is infeasible.

If an additional mandatory requirement demands y ≥ 5, the formulation becomes infeasible, since 2y already exceeds 8. This is a conflict in the stated requirements, not a request for the optimizer to search longer. The small problem was checked by enumeration by hand; the quantities are invented teaching data.

Illustrative case study

Fictional case: Birch Supplies asks for a weekly fulfillment plan with every order completed and overtime prohibited. The available regular hours cannot meet the requested workload, so the model reports no feasible plan.

Rather than presenting a partially valid answer as optimal, the team identifies which requirements conflict. Management then chooses whether to allow additional capacity or explicitly permit delayed orders with a stated cost. Each choice creates a revised optimization problem. The distinction matters because quietly removing a constraint would change the decision being authorized. No operating result is claimed for this fictional organization.

Common misconceptions and mistakes

An optimization problem need not have a solution, even when its formula looks simple. Existence depends on the objective and feasible set. Nor is every constraint a penalty: a hard constraint excludes a decision, while a finite penalty can leave a violation selectable if the tradeoff is attractive enough.

The direction of optimization matters. Maximizing revenue and minimizing negative revenue are equivalent when the feasible set is unchanged, but minimizing revenue would be a different task. Units matter as well: adding hours to currency without an explicit conversion weight does not create an interpretable business objective.

Business use

Use the formulation as a reviewable agreement about what the system may choose. Stakeholders should be able to identify the meaning of every variable, which inputs are forecasts, and which requirements are mandatory. Store the problem version with each recommendation.

When several goals matter, make the tradeoff explicit through priorities, constraints, or a stated multiobjective treatment. Avoid promising one universally “best” answer when stakeholders disagree about how outcomes should be ranked.

Check your understanding

In “minimize w over w > 0,” why is zero not a solution?

Answer: Zero is outside the feasible set. Positive values approach zero, but none attains it. The infimum exists while a minimizing decision does not.

Related terms

Objective function
Optimization method
feasible set
constraint
decision variable
optimal value
infeasibility
relaxation

Learn next

write a small integer allocation problem and enumerate its feasible choices, then examine how its continuous relaxation differs from the original decision space.

Sources

Primary sources: Aalto Dictionary of Machine Learning, optimization problem: https://aaltodictionaryofml.github.io/ADictML_Main.pdf ; Boyd and Vandenberghe, Convex Optimization introductory slides: https://web.stanford.edu/~boyd/cvxbook/bv_cvxslides.pdf . Formulation passages were read. This entry focuses on scalar objectives; broader ordered or multiobjective formulations need an explicit comparison rule. The packing example and fictional case are original.

Previous: Optimization method Next: Optimizer