Objectives, Decision Variables, Constraints, and Feasibility › Formula

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.