Why a Continuous Optimum Is Not the Final Answer
A continuous optimization problem allows the decision variable to take every real value in a specified interval. A discrete decision may instead be restricted to integers: a number of workers, machines, batches, or items cannot be fractional. In that setting, a point that optimizes the continuous model might not be an allowed decision.
Calculus can still help. If the objective has a single peak or trough, its continuous optimum can identify nearby integer candidates. But those candidates must be feasible, and their objective values must be compared. If the continuous optimum is outside the feasible interval, or the objective has a different shape, a boundary value or other feasible integer may matter instead.
Integer Feasibility and Finite Comparisons
Suppose a decision \(x\) must be an integer in the closed interval \([a,b]\), where \(a\le b\). The feasible integer set is \([a,b]\cap\mathbb{Z}\). It is finite, but it may be empty. If it is nonempty, an objective \(f\) has a maximum and a minimum on that set: there are only finitely many feasible values to compare.
This finite-set fact is useful, but it does not say which integers to compare. If there are only a few feasible choices, checking every one is direct. When the set is large, the shape of the continuous objective may narrow the comparison to a small number of candidates.
A Peak Between Two Integers
Consider a function with a strict continuous maximum at \(c\): it increases as \(x\) approaches \(c\) from the left and decreases as \(x\) moves right from \(c\). If \(c\) is not an integer, the natural candidates are the integers immediately on either side, \(\lfloor c\rfloor\) and \(\lceil c\rceil\), provided they are feasible. The floor is the greatest integer no greater than \(c\), and the ceiling is the least integer no less than \(c\).
Worked Example: Comparing Integers Near a Continuous Maximum
Maximize \(f(x)=-x^2+\frac{32}{5}x\) over integer decisions \(x\in[0,8]\). First locate the continuous maximum by differentiating:
Setting the derivative equal to zero gives \(-2x+\frac{32}{5}=0\), so \(x=\frac{16}{5}=3.2\). The derivative is positive for \(x<\frac{16}{5}\) and negative for \(x>\frac{16}{5}\), so this is a strict continuous maximum. The neighboring integers \(3\) and \(4\) are both feasible. Evaluate the objective at each:
Since \(\frac{51}{5}>\frac{48}{5}\), the best of these candidates is \(x=3\). The derivative signs show that every feasible integer below \(3\) has a lower value than \(f(3)\), and every feasible integer above \(4\) has a lower value than \(f(4)\). Thus \(x=3\) is the discrete maximum. As a check, substituting \(x=3\) into the original objective gives \(-3^2+\frac{32}{5}(3)=-9+\frac{96}{5}=\frac{51}{5}\), as calculated.
The continuous optimum narrowed the search to two integers, but the comparison determined which one won. The two values need not be equal, and knowing which integer is closer to \(c\) is not, by itself, a substitute for comparing objective values.
Why the Neighboring-Integer Rule Works
Here is a precise version of the rule for maximization. The nonempty-feasible-set condition matters: an interval can contain a continuous maximum but contain no feasible integer at all.
The derivative signs imply that \(f\) increases to \(c\) and decreases after \(c\). To justify this, take any \(u<v\) in \([a,c]\). The Mean Value Theorem applies on \([u,v]\), since \(f\) is continuous there and differentiable between \(u\) and \(v\). It gives a point \(d\in(u,v)\) such that \(f(v)-f(u)=f'(d)(v-u)>0\). Thus \(f(v)>f(u)\). The same theorem applied to \(c\le u<v\le b\) gives \(f(v)-f(u)=f'(d)(v-u)<0\), so \(f(v)<f(u)\). In particular, \(f\) increases up to \(c\) and decreases after \(c\).
If \(c\) is not an integer and there is a feasible integer less than \(c\), the greatest such integer is \(\lfloor c\rfloor\); if \(c\) is an integer, step 3 handles it. It lies in \([a,b]\): it is at least as large as any feasible integer on the left, and it is less than \(c<b\). Since \(f\) increases to \(c\), no feasible integer further left has a greater value.
If \(c\) is not an integer and there is a feasible integer greater than \(c\), the least such integer is \(\lceil c\rceil\); if \(c\) is an integer, step 3 handles it. It lies in \([a,b]\), and since \(f\) decreases after \(c\), no feasible integer further right has a greater value.
If \(c\) is an integer, it is feasible because \(c\in(a,b)\), and \(f\) increases before it and decreases after it. It is therefore a maximizing integer. In all cases, the feasible integers among the floor and ceiling contain a maximum.
The proof also explains why nonempty feasibility is needed: there must be at least one integer decision for a discrete maximum to be attained. For a minimum, the corresponding rule applies when the derivative is negative before \(c\) and positive after it. The function then decreases to \(c\) and increases after it, so the neighboring feasible integers contain a minimum.
Worked Example: A Continuous Minimum Between Integers
Worked Example: Choosing the Better Integer for a Minimum
Minimize \(g(x)=(x-\frac{13}{5})^2+2\) over integers \(x\in[0,6]\). Differentiating gives:
The derivative is negative when \(x<\frac{13}{5}\) and positive when \(x>\frac{13}{5}\), so \(c=\frac{13}{5}=2.6\) is a continuous minimum. The neighboring feasible integers are \(2\) and \(3\). Substituting each into the objective gives:
Since \(\frac{54}{25}<\frac{59}{25}\), choose \(x=3\). The derivative signs establish that integers further from the minimum on either side cannot improve on their nearer candidate. Substituting \(x=3\) into the original expression gives \((\frac{2}{5})^2+2=\frac{4}{25}+\frac{50}{25}=\frac{54}{25}\), confirming the selected value.
When a Feasible Boundary Determines the Answer
The neighboring-integer rule above assumes the continuous peak \(c\) lies in the interior of the interval. In applications, the unconstrained peak can lie outside the feasible interval. Then the objective might be increasing or decreasing throughout the feasible range, and the feasible integer nearest the appropriate boundary can be optimal. The boundary itself may not be an integer, so compare feasible integer choices rather than treating that real boundary as an allowed decision.
Worked Example: The Best Integer Lies at a Feasible Boundary
Maximize \(h(x)=-(x-5)^2+12\) over integer \(x\in[1.2,4.6]\). The feasible integers are \(2,3,4\). The derivative is \(h'(x)=-2(x-5)\), which is positive throughout the interval because \(x<5\). Thus the objective increases across the feasible interval, and its greatest feasible integer is \(4\). To verify the choice, compare the objective values:
The largest value is \(11\), attained at \(x=4\). The continuous peak \(x=5\) is outside the feasible interval, and the right endpoint \(4.6\) is not an integer decision. Substitution of \(x=4\) into the original objective gives \(-(4-5)^2+12=-1+12=11\), confirming the maximum.
Why Rounding Alone Can Fail
It is tempting to round a continuous optimum to the nearest integer and stop. That shortcut is not generally justified: a function can have a strict continuous peak and still lose value more rapidly on one side than on the other. The nearest integer need not give the greater objective value. The following calculation shows why the two neighbors must be compared.
Worked Example: The Nearest Integer Is Not Always Best
On the integer decisions \(x\in\{0,1\}\), consider \(p(x)=-\frac{t^2}{2}+\frac{t^3}{2}\), where \(t=x-\frac{49}{100}\). As a function of \(x\), its derivative is:
For \(0\le x\le1\), \(t\) ranges from \(-\frac{49}{100}\) to \(\frac{51}{100}\). The factor \(1-\frac{3t}{2}\) is positive throughout this range; even at the largest \(t\), it is \(1-\frac{153}{200}=\frac{47}{200}>0\). Therefore \(p'(x)>0\) before \(c=\frac{49}{100}\) and \(p'(x)<0\) after it. The continuous maximum is at \(c=0.49\), whose nearest integer is \(0\). But the two feasible integer values are:
Since \(-\frac{127449}{2000000}>-\frac{357749}{2000000}\), the better integer is \(1\), not the nearest integer \(0\). These values come from substituting \(t=-\frac{49}{100}\) and \(t=\frac{51}{100}\), respectively, into the definition of \(p\). This example confirms that even when the continuous peak is known, comparing the neighboring feasible integers is essential.
A Practical Comparison Procedure
For an integer decision constrained to a closed interval, first identify the feasible integers. If the set is nonempty and small, evaluate the objective at every feasible choice. If calculus reveals a strict interior maximum or minimum with the derivative signs described above, evaluate the feasible integers immediately to either side of the continuous optimum. If that optimum is outside the interval, check the feasible endpoint choices and use the derivative behavior to determine whether the objective is increasing or decreasing across the range.
These shortcuts depend on the objective's shape and on the feasible set. If the integer constraints leave gaps, or the objective is not increasing up to one peak and decreasing after it, the floor-and-ceiling result may not apply. In that case, compare the feasible candidates justified by the actual constraints and objective; do not assume that the nearest integers to a continuous critical point settle the problem.
Check Your Understanding
Use the derivative behavior and feasible integer set to decide which values must be compared.
- A function increases before \(c=4.3\) and decreases after \(c\). If the integer feasible set is \(\{1,2,\ldots,8\}\), which candidates suffice to find its maximum?
- Why does a theorem about a maximum over feasible integers need to assume that at least one feasible integer exists?
- A continuous minimum occurs at \(c=6.7\), with the function decreasing before \(c\) and increasing after it. Which neighboring integers should be checked if both are feasible?
- If the continuous maximum lies to the right of every feasible integer and the objective is increasing throughout the feasible interval, which feasible integer is best?
- Why can rounding a continuous optimum to the nearest integer fail, even when the function has a strict maximum there?
