Objectives, Decision Variables, Constraints, and Feasibility

A packaging plant runs two products on shared equipment. Every pallet of product 1 consumes 2 machine-hours and 1 labour-hour; every pallet of product 2 consumes 1 machine-hour and 2 labour-hours. Today the plant has 8 machine-hours and 8 labour-hours available, product 1 earns $40 per pallet, and product 2 earns $30 per pallet. The plant manager does not want a prediction of tomorrow's demand. She wants an answer to a decision question: how many pallets of each product should we build with the hours available?

Answering that question requires three separate pieces of work. First we must translate the situation into mathematics: name the quantities we control, write an expression that scores each alternative, and state the rules alternatives must obey. This is formulation. Second we search for a good or provably best alternative, by hand on a small problem or with a solver on a larger one. This is optimization. Third we independently check the returned decision against the model and operational requirements. This is solution validation. A solver status describes its numerical search; it cannot establish that the model represents the plant correctly.

This chapter introduces the formulation vocabulary used throughout constrained optimization: decision variables, domains, objectives, hard constraints, soft penalties, and feasible sets. Factory planning, minimum-cost flow, portfolio optimization, rostering, and routing all require these choices. Their variable domains and constraint functions differ; they are not interchangeable coefficient matrices.

Consider how this differs from unconstrained least-squares fitting in Linear and Generalized Linear Models and Gradient Descent and Numerical Optimization. In that fitting problem the decisions are coefficients $\theta$, the objective measures residual error, and the domain permits any real coefficient vector. Operational optimization instead chooses actions such as production quantities, with explicit resource limits and a value assigned to each action. Fitting can also include constraints, so the distinction is the meaning of the decisions and objective rather than whether constraints exist. A good prediction alone does not specify a feasible production plan.

An explicit formulation makes assumptions inspectable. Record each coefficient with its name, unit, source, and owner so that a planner, analyst, or engineer can check it. When a plan changes, comparing model versions can reveal whether the change came from the objective, a constraint, or the input data.

Bounds can quantify search quality under a fixed model. A feasible incumbent and a valid bound bracket the optimum, allowing us to report the largest remaining improvement consistent with those numbers. Prediction intervals address uncertainty in outcomes; optimization bounds address the objective of the stated decision model. Neither compensates for incorrect coefficients or missing requirements.

A formulation can be re-solved with fresh capacity and demand or extended when requirements change. In suitable continuous models, dual multipliers also describe local sensitivity to a resource limit. A nonzero multiplier identifies a priced resource at that solution, but a binding constraint can have a zero multiplier, and discrete changes need separate analysis.

Finally, a formulation forces us to separate feasibility from profitability. Requirements can conflict before we compare profits. Asking "is the feasible set empty?" separates that question from ranking feasible plans.

The model omits details of the world. An optimum can therefore prescribe a poor operational decision when a relevant requirement is missing or a coefficient is wrong. Conversely, an infeasible model may reveal incompatible requirements, rather than a formulation error. Both possibilities require investigation.

Computational difficulty depends on structure as well as size. General mixed-integer linear optimization is NP-hard, although particular instances can be easy. Continuous nonlinear problems may be convex or nonconvex. A local numerical solver can terminate at a stationary point or on a step or objective tolerance; successful termination alone does not establish a global optimum.

Solver statuses must be read with their tolerances. A mixed-integer optimal status generally means the incumbent and search bound meet the requested stopping criteria, using floating-point feasibility and integrality tolerances. It is stronger than merely finding no better plan, but it is not an exact-arithmetic proof. Tolerance settings depend on the solver and options. Scaling and units affect their physical interpretation and how reliably numerical tests can be met; there is no universal $10^{-9}$ rule.

Formulations can go stale. Coefficients that were correct last quarter can become wrong without an obvious warning when costs, capacities, or operating conditions change. If relevant costs change and the inputs are not updated or revalidated, the model can continue recommending plans based on an obsolete cost structure. Periodic reviews and updates require ongoing work for an actively maintained model.

We will formulate the plant decision in four steps: collect the quantities we control, choose their domains, define the objective, and impose the constraints. Writing those components separately makes it possible to check the meaning of each formula against the production example.

The first layer is the set of quantities under our control. We do not describe them with a paragraph; we collect them into a single vector so that every later operation (scoring, checking constraints, reporting a plan) addresses them positionally.

$$x = (x_1, x_2, \dots, x_n) \in \mathbb{R}^n.$$

where:

• $x$: the full decision vector collecting all $n$ quantities we control
• $x_j$: the $j$-th component, a single decision variable
• $n$: the number of decision variables
• $\mathbb{R}^n$: the ambient space allowing each coordinate to be any real number

Each component $x_j$ is a decision variable: a quantity we are free to set, as opposed to a quantity we observe or predict. In the packaging example $n = 2$, $x_1$ is the number of pallets of product 1, and $x_2$ is the number of pallets of product 2. The choice to treat them as real numbers is already a modelling assumption; it says a fractional pallet makes sense, which we will revisit when integrality enters.

The vector alone permits values the application may rule out, such as negative production or fractional vehicle counts. We choose a domain $X\subseteq\mathbb{R}^n$. Here we use a product of individual variable domains and express coupling requirements as constraints. A domain can also be defined more generally. Nonnegative real variables model divisible quantities, integer variables model counts, and binary variables model yes/no choices.

The third layer is the objective function, a scalar-valued map $f:X\to\mathbb{R}$ that scores a decision. This chapter uses scalar objectives; multiobjective methods require a stated comparison rule. For the general theory we use minimization. The production example is naturally written as profit maximization and is negated before calling a minimization solver. When the extrema are attained,

$$\max_{x \in X} f(x) \;=\; -\,\min_{x \in X}\big(-f(x)\big),$$

where:

• $X$: the domain, the set of individually admissible decisions
• $f$: the objective function being maximized or negated for minimization
• $x$: the decision vector over which the objective is optimized
• $-f(x)$: the negated objective, so the minimum of the negation equals the negative of the maximum of $f$

A maximization of profit therefore becomes a minimization of negative profit. The best decision vectors are the same, while the optimal objective value changes sign. This is why the implementation negates both the coefficients passed to the solver and the returned objective.

The fourth layer is constraints, the rules a decision must satisfy. We write inequality constraints as $g_i(x) \leq 0$ for $i = 1, \dots, m$ and equality constraints as $h_j(x) = 0$ for $j = 1, \dots, p$, where:

• $g_i$: the $i$-th inequality constraint function, moved to the left-hand side so that $g_i(x) > 0$ measures violation
• $h_j$: the $j$-th equality constraint function, moved to the left-hand side so that $h_j(x) = 0$ at every feasible decision
• $m$: the number of inequality constraints
• $p$: the number of equality constraints

The convention that everything is moved to the left-hand side is deliberate: it makes the right-hand side a constant, and it makes the sign of $g_i$ meaningful, since $g_i(x) > 0$ now literally measures violation. Without that convention, a positive value of $g_i$ could mean violation or slack depending on how the modeller wrote the original inequality, and every diagnostic downstream would inherit the ambiguity.

The feasible set collects every decision that breaks no rule:

$$\mathcal{F} = \big\{\, x \in X \;:\; g_i(x) \leq 0 \ \text{for all } i, \ \ h_j(x) = 0 \ \text{for all } j \,\big\}.$$

where:

• $\mathcal{F}$: the feasible set, the collection of all decisions satisfying every constraint
• $x$: a candidate decision vector drawn from the domain $X$
• $X$: the domain of individually admissible decisions
• $g_i(x)$: the $i$-th inequality constraint function, satisfying $g_i(x) \leq 0$
• $h_j(x)$: the $j$-th equality constraint function, satisfying $h_j(x) = 0$

Read the braces as "the set of all $x$ in $X$ such that...". This set is the central object of the chapter. It is not a score, and it does not rank anything; it only says yes or no. When we later ask a solver to minimize, we are asking two questions at once: is $\mathcal{F}$ non-empty, and if so, which of its members minimizes $f$?

A general mathematical program is

$$z^\star = \inf_{x \in \mathcal{F}} f(x),$$

where:

• $x$: the decision vector chosen from the feasible set
• $\mathcal{F}$: the feasible set of admissible decisions defined above
• $f$: the objective function that scores a decision
• $z^\star$: the optimal value, defined as the greatest lower bound of feasible objective values

Read this as the greatest lower bound of $f(x)$ over feasible decisions. If some feasible $x^\star$ attains that value, it is an optimal solution. If $\mathcal{F}=\varnothing$, the problem is infeasible and we conventionally set $z^\star=+\infty$. If feasible objective values decrease without bound, then $z^\star=-\infty$. A fourth possibility is a finite value that is not attained: minimizing $1/x$ over $x>0$ has infimum zero but no minimizer. Infeasibility can reflect incompatible requirements, and unboundedness can be a property of the model; neither automatically proves a modelling error.

For the packaging example, with profit coefficients $c_1 = 40$ and $c_2 = 30$, the problem is

$$\begin{aligned} \max_{x_1,\,x_2} \quad & 40x_1 + 30x_2 \\ \text{subject to} \quad & 2x_1 + x_2 \leq 8 && \text{(machine-hours)} \\ & x_1 + 2x_2 \leq 8 && \text{(labour-hours)} \\ & x_1 \geq 0, \quad x_2 \geq 0. \end{aligned}$$

where:

• $x_1$: number of pallets of product 1 to build
• $x_2$: number of pallets of product 2 to build
• $\max_{x_1,\,x_2}$: maximize the objective over the two decision variables
• $2x_1 + x_2$: machine-hours consumed, with 2 hours per pallet of product 1 and 1 per pallet of product 2; must not exceed 8
• $x_1 + 2x_2$: labour-hours consumed, with 1 hour per pallet of product 1 and 2 per pallet of product 2; must not exceed 8
• $40$: profit per pallet of product 1
• $30$: profit per pallet of product 2

Compressing this into matrix notation is mostly bookkeeping, but the bookkeeping is what lets us talk to software. Let

$$A = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix}, \qquad b = \begin{pmatrix} 8 \\ 8 \end{pmatrix}, \qquad c = \begin{pmatrix} 40 \\ 30 \end{pmatrix}, \qquad x = \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}.$$

where:

• $A$: the resource-consumption matrix, with $A_{ij}$ the amount of resource $i$ that one unit of activity $j$ consumes
• $b$: the vector of available resource capacities
• $c$: the vector of profit coefficients per pallet
• $x$: the decision vector of activity levels

The product $c^\top x$ is a row vector times a column vector, which by definition equals $40x_1 + 30x_2$: the transpose turns the column $c$ on its side so the shapes line up, and the single resulting number is the objective value. Likewise $Ax$ is a $2 \times 1$ vector whose first entry is $2x_1 + x_2$ and whose second entry is $x_1 + 2x_2$, so the pair of inequalities is exactly $Ax \leq b$, where the comparison is applied entry by entry. The compact form of our problem is

$$\max_{x} \; c^\top x \quad \text{subject to} \quad Ax \leq b, \quad x \geq 0 .$$

where:

• $A$: the resource-consumption matrix defined above
• $b$: the capacity vector, so each entry of $Ax$ must not exceed its paired entry in $b$
• $c$: the profit-coefficient vector, so $c^\top x$ is total profit
• $x$: the non-negative decision vector

Each row of $A$ is one resource constraint and each column is one variable. In this model, $A_{ij}$ records the amount of resource $i$ consumed by one unit of activity $j$. A transposed or mislabelled entry changes that meaning. Check a small known decision by multiplying it by $A$ and independently calculating each resource total.

Choosing the variables shapes how we write the objective, domains, and constraints. A good variable is something a decision maker can set, measured in a unit that appears in the objective and the constraints. Two habits make a formulation easier to check:

• Keep units consistent within a column. If $x_1$ is pallets per day, the objective coefficient must be profit per pallet and the constraint coefficient must be hours per pallet, not hours per week.
• Prefer marginal coefficients to average quantities when the model aggregates by addition. If the first 100 pallets cost 5 per unit to make and the next 100 cost 7, a single linear coefficient cannot express that; we need two variables with a capacity link, or a piecewise-linear construction.

A physically divisible quantity, such as litres of solvent, can use a continuous domain. A head count or indivisible pallet count uses an integer domain; an open-or-closed facility decision uses a binary domain $\{0,1\}$. An aggregate quantity such as full-time-equivalent staffing may still be divisible, so choose the domain from the actual decision. Integrality creates combinatorial choices and can substantially change computational difficulty, even when the coefficients stay linear.

Suppose a planning team wants to balance profit, service level, emissions, and overtime. Common ways to specify priorities include a weighted scalar objective, optimizing one measure subject to targets on the others, and lexicographic optimization. The weighted objective is $\sum_k w_k f_k(x)$, where:

• $k$: indexes the objective components being combined
• $w_k$: the weight assigned to objective component $k$, a policy choice that must be stated openly
• $f_k(x)$: the value of the $k$-th objective component for decision $x$

For a lexicographic solve, first obtain the primary optimum, then constrain that objective to its attained optimal value while optimizing the secondary measure. With numerical solvers the allowed primary tolerance must be stated. Weighted sums also require explicit policy weights and compatible scales. Changing weights can change the objective and selected decision, but different weights need not produce different optimal decisions.

A hard constraint excludes violations from the mathematical feasible set. It is appropriate when violating the rule is unacceptable for the modeled decision. That mathematical exclusion does not guarantee a numerically returned or operationally executed plan is valid: the model, data, numerical tolerances, and final decision still need checking.

A soft constraint is a rule we would like to respect but are willing to trade off. The standard encoding is a penalty added to the objective. Using the positive-part function $(u)_+ = \max(0, u)$, which equals $u$ when $u$ is positive and zero otherwise, the penalty formulation is (note $\lambda$ here is the fixed penalty weight, distinct from the Lagrange multipliers $\lambda_i$ discussed in the duality subsection):

$$\min_{\substack{x \in X\\[2pt] h_j(x)=0\;\forall j}}\; f(x) + \lambda \sum_{i=1}^{m} \big(g_i(x)\big)_+^{\,2},$$

where:

• $x$: the decision vector, chosen from the domain $X$
• $X$: the domain of individually admissible decisions
• $f(x)$: the original objective value of decision $x$
• $m$: the number of soft inequalities being penalized; unpenalized equalities remain hard constraints
• $g_i(x)$: the $i$-th constraint function, positive where the rule is violated
• $(g_i(x))_+$: the positive part $\max(0, g_i(x))$, the amount by which constraint $i$ is violated
• $\lambda > 0$: a weight with units of objective per unit of squared violation

If every $g_i(x)\leq0$, the penalty vanishes and the original objective is unchanged. The squared positive part is continuously differentiable as a function of its scalar residual; composition is continuously differentiable when the constraint functions are. This does not generally enforce exact feasibility at a finite weight. In the later one-dimensional example, every finite quadratic weight leaves a violation, although other problems can already have feasible penalized minimizers. A linear positive-part penalty $\rho\sum_i(g_i(x))_+$ can be exact under additional conditions. For example, with the hard equalities retained in the minimization domain, an attained primal optimum, and attained strong-dual multipliers $\lambda_i^\star\geq0$, a weight $\rho>\max_i\lambda_i^\star$ makes every globally optimal penalized decision feasible, provided it is minimized globally over the same domain. This is a conditional result, not a guarantee for arbitrary local solvers. Residuals must have compatible scales or use separate weights per constraint.

To investigate feasibility separately from the original objective, minimize a scaled measure of total constraint violation:

$$v^\star = \inf_{x \in X} \left[\sum_{i=1}^{m}\big(g_i(x)\big)_+ + \sum_{j=1}^{p}|h_j(x)|\right].$$

where:

• $x$: the decision vector, chosen from the domain $X$
• $m$: the number of constraints being checked for violation
• $g_i(x)$: the $i$-th constraint function, positive where the rule is violated
• $(g_i(x))_+$: the positive part $\max(0, g_i(x))$, the amount by which constraint $i$ is violated
• $|h_j(x)|$: the magnitude of equality violation for equality $j$, with $p$ equalities
• $v^\star$: the infimum of the summed violation measures; normalize residual units before adding them

An actual decision with zero total violation is a feasible witness. If the globally optimal violation value is strictly positive, no feasible decision exists in $X$. An infimum of zero alone does not establish feasibility: $x>0$ together with $x\leq0$ is infeasible even though violations can approach zero. A local solver finding a positive violation is also not an infeasibility proof. This phase-one diagnostic shows which requirements the chosen minimum-violation compromise relaxes; it need not identify a unique or irreducible conflict. Residual scales determine which compromises it prefers.

A related construction is the Lagrangian, whose minimization over the retained domain gives a dual bound. Define

$$L(x, \lambda) = f(x) + \sum_{i=1}^{m} \lambda_i\, g_i(x),$$

where:

• $f(x)$: the objective value of decision $x$
• $g_i(x)$: the $i$-th constraint function
• $\lambda_i \geq 0$: the Lagrange multiplier for constraint $i$; with the $g_i(x) \leq 0$ convention non-negative multipliers make the infimum of the Lagrangian over the domain a lower bound on $z^\star$
• $\lambda$: the vector of all multipliers

For each non-negative multiplier $\lambda_i$, the term $\lambda_i g_i(x)$ is non-positive when constraint $i$ is satisfied and non-negative when that individual constraint is violated. For a fixed positive multiplier, larger slack makes the term more negative, while a larger positive violation makes it more positive. If the multiplier is zero, the term remains zero. The sum can contain both signs at an infeasible decision, so one violation does not imply that the entire Lagrangian lies above the objective. Unlike a positive-part penalty, the signed Lagrangian term need not be zero throughout the feasible set. Its purpose here is to construct lower bounds by minimizing over the domain; it does not directly impose feasibility. Equality constraints may remain in that domain, or be dualized separately with unrestricted multipliers. The next subsection derives the bound.

The formulation classes distinguish permitted expressions and variable domains. Their computational properties depend on structure and assumptions. Remember the four names LP, MILP, QP, and NLP: they identify the model classes discussed in solver documentation.

Linear programs (LPs) have affine objectives and affine constraints over continuous variables. Their feasible regions are polyhedra. For a nonempty bounded feasible polyhedron, a linear objective attains an optimum at a vertex, although other optimal points may exist along an edge. Without suitable conditions a polyhedron may have no vertices. LP relaxations provide bounds for mixed-integer linear models and are used in branch-and-bound.

Mixed-integer linear programs (MILPs) retain affine objectives and affine constraints while restricting some variables to integers or binaries. Binary variables can encode logical decisions; a big-M construction needs valid finite bounds and a justified M. General MILP is NP-hard, while special structures may permit efficient methods. Its continuous LP relaxation enlarges the feasible set, which gives the bound derived below.

Quadratic programs (QPs) use an objective $\tfrac12x^\top Qx+c^\top x$ and affine constraints. For symmetric positive-semidefinite $Q$ over a convex continuous domain, the objective is convex. Mean-variance portfolio models use this form. Ridge regression gives another example. Within that regression example, $X$ denotes the design matrix, $y$ the response vector, $\beta$ the coefficient vector, and $I$ the identity matrix of the coefficient dimension; this use of $X$ is separate from the optimization-domain notation above. For penalty weight $\lambda\geq0$, expanding $\lVert y-X\beta\rVert^2+\lambda\lVert\beta\rVert^2$ gives $\beta^\top(X^\top X+\lambda I)\beta-2y^\top X\beta+y^\top y$. Thus $Q=2(X^\top X+\lambda I)$ and $c=-2X^\top y$ reproduce the objective apart from the constant $y^\top y$, which does not change its minimizers. The unconstrained case has no additional constraints.

Nonlinear programs (NLPs) allow nonlinear objectives or constraints. They can model blending or physical relationships, but convexity must be checked. Local methods need not find a global optimum and may stop without reaching a local minimum. Finite-domain constraint programming is another modelling style, combining discrete domains with logical and arithmetic constraints, as in rostering.

Removing integrality from a MILP gives its continuous LP relaxation. Removing integrality from a nonlinear mixed-integer problem gives a continuous relaxation that may still be nonlinear. If a globally solved relaxation returns a decision satisfying the original domains and constraints, that decision also solves the original problem, because it attains the relaxation bound. A fractional relaxation solution remains a bound, rather than a valid integer plan.

Suppose we cannot solve a problem exactly, or we want to know how much we would gain from trying harder. We need a number that no feasible decision can beat. Any such number is a valid bound, and a relaxation supplies one.

Take a mixed-integer problem and delete the integrality restrictions, obtaining a relaxation with feasible set $\mathcal{F}_{\text{rel}} \supseteq \mathcal{F}$. Because we minimized over a larger set, the relaxed optimum cannot be larger:

$$z_{\text{rel}} \leq z^\star .$$

where:

• $z_{\text{rel}}$: the optimal value of the continuous relaxation (integrality removed); for a MILP, this is an LP
• $z^\star$: the optimal value of the original mixed-integer problem
• $\mathcal{F}$: the feasible set of the original problem
• $\mathcal{F}_{\text{rel}}$: the feasible set of the relaxation, with $\mathcal{F}_{\text{rel}} \supseteq \mathcal{F}$

For a maximization this reverses to $z_{\text{rel}} \geq z^\star$, so the relaxation is optimistically better than reality: it says "if fractions were allowed, you could earn 186.67", whereas the true integer profit is only 180. Note that the LP value 186.67 is the maximization value; in the minimization form used earlier for the gap the corresponding numbers are $-186.67$ and $-180$. Every real plan is bounded by that promise, which is exactly what makes the number useful. The bound does not depend on the quality of our incumbent; it depends only on the model, so it can certify even a plan we have not found yet.

The Lagrangian also gives a lower bound. Let $\lambda_i \geq 0$ for every inequality constraint and let $y$ be any feasible decision. Then each $g_i(y)\leq 0$, so

$$L(y,\lambda)=f(y)+\sum_{i=1}^{m}\lambda_i g_i(y)\leq f(y).$$

Here $L$ is the Lagrangian, $f$ is the minimization objective, and the multipliers $\lambda_i$ weight the inequality residuals $g_i$. Each added term is non-positive at a feasible point. Now minimize over the entire domain $X$, which includes $y$:

$$d(\lambda):=\inf_{x\in X}L(x,\lambda)\leq L(y,\lambda)\leq f(y).$$

The function $d$ is the dual function: its value is the infimum of the Lagrangian over all domain-allowed decisions, without requiring the relaxed inequalities. Because this chain holds for every feasible $y$, it also gives

$$d(\lambda)\leq\inf_{y\in\mathcal{F}}f(y)=z^\star.$$

The infimum is the greatest lower bound, which need not be attained by a decision. This is weak duality. Maximizing $d(\lambda)$ over non-negative multipliers seeks the strongest bound in this family; it does not guarantee equality with the primal optimum. A feasible incumbent supplies an upper bound for minimization, while this dual value supplies a lower bound. Together they bracket the unknown optimum.

With a candidate value $z_{\text{inc}}$ from some plan or incumbent and a lower bound $z_{\text{LB}}$, the relative optimality gap is

$$\text{gap} = \frac{z_{\text{inc}} - z_{\text{LB}}}{\lvert z_{\text{inc}} \rvert},$$

where:

• $z_{\text{inc}}$: the objective value of the best incumbent plan found so far
• $z_{\text{LB}}$: a valid lower bound on the optimal value
• $z_{\text{inc}} - z_{\text{LB}}$: the absolute optimality gap, the amount the incumbent might still be improvable
• $\lvert z_{\text{inc}} \rvert$: the absolute value of the incumbent, normalizing the gap to a relative fraction

The numerator bounds the possible improvement of a feasible incumbent over the unknown minimum. Dividing by $\lvert z_{\text{inc}}\rvert$ expresses that bound relative to the magnitude of the incumbent, not relative to the unknown optimum. This formula is undefined when $z_{\text{inc}}=0$; report the absolute bound gap or state the solver's explicit convention for that case.

Bounds and gaps quantify search quality, but a small gap does not replace checking candidate feasibility, objective accounting, or model inputs. Use three independent cross-checks:

• Recompute the objective from the reported decision and compare it with the solver's reported value, checking for sign errors and truncated output.
• Check variable domains, including bounds and integrality, and recompute every constraint residual with stated tolerances. For a general inequality $g_i(x) \leq 0$, the violation is $\max(0,g_i(x))$. For an affine inequality $a_i^\top x \leq b_i$, the signed slack is $b_i-a_i^\top x$, where $b_i$ is the $i$-th capacity and $a_i$ is the $i$-th coefficient row. A negative slack means the inequality is violated; a non-negative slack is unused capacity. Report the largest violation in each relevant residual scale. For an equality $h_j(x)=0$, check the magnitude $\lvert h_j(x)\rvert$ against its tolerance.
• On small problems, compare with a second method such as exhaustive enumeration. When enumeration is impossible, compare with a different solver or a differently formulated model. Different implementations can still share input or formulation errors.

These checks connect a solver status to a plan whose objective and feasibility have been independently examined.

• A convex domain, convex inequality functions, and affine equality functions give a convex feasible set. With a convex objective, any local minimum over that set is global.
• A linear objective over a nonempty bounded polyhedron has at least one optimal vertex. A constant objective on the entire real line has a finite optimum but no vertex, illustrating why the geometric conditions matter.
• Adding constraints to a fixed model can only shrink its feasible set, so its optimal minimization value cannot decrease. If every old feasible decision embeds in an expanded model with the same objective value, the expanded minimization value cannot increase. Without that embedding, adding variables alone gives no such monotonicity guarantee.
• Weak duality does not require convexity. Convexity with a suitable constraint qualification, such as Slater's condition, is a sufficient route to strong duality, not a necessary one. Dual attainment is an additional issue; equality of optimal values alone does not guarantee an optimal multiplier exists.
• Integrality is not preserved by relaxation, and the difference between the integer optimum and the relaxed optimum is the integrality gap. It can be zero, small, or arbitrarily large, so LP bounds are informative in some models and nearly useless in others.
• Floating-point feasibility is checked with stated tolerances. Choose checks appropriate to each constraint's units and scales, inspect signed residuals, and report violations rather than assuming one numerical threshold suits every model.

With two decision variables we can draw the entire problem, and the picture is a useful antidote to abstract notation. Each inequality $a_i^\top x \leq b_i$ defines a half-plane, its boundary line is where the constraint is tight, and the feasible set is the intersection of these half-planes with the non-negative quadrant. The objective $c^\top x$ is constant along lines perpendicular to $c$, so we can draw several iso-profit lines and watch which one is the last to touch the region.

A non-negotiable rule belongs in the feasible set. A preference that permits violations can instead use an explicit penalty with stated units and weight. In either case, check the returned decision. The one-dimensional example shows why a large finite quadratic penalty cannot simply be assumed to satisfy a hard rule.

We now solve the packaging problem completely by hand, then repeat the exercise with whole pallets, and finally measure the gap between the two. Hand-solving is not busywork: it gives us a reference value against which every solver call in the next section can be audited.

The first step is to find the feasible set, because without it we have no candidates to score. Each resource inequality becomes an equality on its boundary line. The machine constraint $2x_1 + x_2 \leq 8$ has boundary $x_2 = 8 - 2x_1$, which meets the $x_1$-axis at $x_1 = 4$ and the $x_2$-axis at $x_2 = 8$. The labour constraint $x_1 + 2x_2 \leq 8$ has boundary $x_2 = 4 - x_1/2$, meeting the axes at $x_1 = 8$ and $x_2 = 4$. The non-negativity domains cut everything to the first quadrant, so the feasible region is the quadrilateral with corners

$$(0,0), \qquad (4,0), \qquad (8/3,\, 8/3), \qquad (0,4).$$

The corner $(4,0)$ comes from the first line at $x_2 = 0$; the corner $(0,4)$ comes from the second line at $x_1 = 0$; the corner $(8,0)$ implied by the second line is cut off by the first line and is therefore not feasible. To find the intersection we solve the two equalities. Doubling the first gives $4x_1 + 2x_2 = 16$. Subtracting the second, $x_1 + 2x_2 = 8$, yields $3x_1 = 8$, so $x_1 = 8/3$, and substituting back gives $x_2 = 8 - 2(8/3) = 8/3$. Both are positive, so this point is in the feasible set.

Evaluating the objective at each corner:

The largest value is $560/3 \approx 186.67$ at corner C, where both resources are exactly exhausted. Checking the algebra: $40 \cdot \tfrac{8}{3} = \tfrac{320}{3}$ and $30 \cdot \tfrac{8}{3} = \tfrac{240}{3}$, and the sum is $\tfrac{320}{3} + \tfrac{240}{3} = \tfrac{560}{3}$. Because the objective is linear and the feasible set is a polygon, the maximum must occur at a corner, so we have solved the continuous problem exactly without any software. The slack columns are worth reading alongside the profit: at C both are zero, which is the geometric signature of a vertex formed by two binding constraints.

Now suppose pallets cannot be split. We enumerate every lattice point with $0 \leq x_1 \leq 4$ and $0 \leq x_2 \leq 4$ and keep those satisfying both inequalities $2x_1 + x_2 \leq 8$ and $x_1 + 2x_2 \leq 8$. The feasible lattice points are exactly those whose coordinates satisfy both resource limits, because nonnegativity and the resource limits rule out any coordinate above 4, independently of the objective. The top candidates, ranked by profit $40x_1 + 30x_2$, are:

The best integer plan is $x_1 = 3$, $x_2 = 2$ with profit $40 \cdot 3 + 30 \cdot 2 = 180$, leaving one labour-hour idle ($8 - (3 + 2\cdot 2) = 1$) and no machine-hours idle ($8 - (2\cdot 3 + 2) = 0$). Note how close the top candidates are: $(2,3)$ earns 170 and $(3,2)$ earns 180, a ten-unit difference produced by swapping which resource is left slack. Rounding the continuous optimum $2.667, 2.667$ to $(3,3)$ would have been a mistake, since $2 \cdot 3 + 3 = 9 > 8$ violates the machine constraint; rounding down to $(2,2)$ loses 40 units of profit. Rounding is a heuristic with no general feasibility or optimality guarantee; this example shows infeasibility when rounding up and lost profit when rounding down.

Finally we quantify how much the integer restriction costs. In minimization form the integer optimum is $z_{\text{inc}} = -180$ and the LP relaxation bound is $z_{\text{LB}} = -560/3$; using profit values directly gives the same relative gap,

$$\begin{aligned} \text{gap} &= \frac{z_{\text{inc}} - z_{\text{LB}}}{\lvert z_{\text{inc}} \rvert} && \text{(relative gap definition)} \\ &= \frac{(-180) - (-560/3)}{\lvert -180 \rvert} && \text{(substitute incumbent and bound)} \\ &= \frac{20/3}{180} = \frac{1}{27} && \text{(simplify numerator and denominator)} \\ &\approx 0.0370. && \text{(evaluate)} \end{aligned}$$

The gap relative to the integer profit is $1/27\approx3.70\%$. This quantifies the initial LP bound's looseness. Enumeration has already established that 180 is the exact integer optimum for this tiny model. A MILP solver that certifies that optimum can tighten its search bound to 180 and report a zero final gap.

We use SciPy because it exposes all three layers we need in one place: linprog for the relaxation, milp for the integer problem, and minimize for the penalty experiment. The organizing principle is to build the audit trail first, because a solver's own report should never be the only evidence we keep. Each code block below corresponds to a step in the hand solution, so the numeric outputs can be checked against the algebra rather than accepted on faith.