How does a continuous LP optimum differ from an integer-constrained optimum?

A continuous optimum is chosen from all real-valued feasible points, while an integer-constrained optimum is chosen only from feasible lattice points. The integer set is smaller, so in maximization it cannot outperform the continuous benchmark. This distinction explains why decimal optimal coordinates may need adjustment.

What is the difference between the nearest integer point and the best feasible integer point?

The nearest integer point is based on geometric distance to the continuous optimum, not on constraints or objective value. The best feasible integer point must satisfy all inequalities and optimize the objective among valid candidates. So closeness is only a heuristic, not the rule.

When should you use local nearby-point checking versus full integer-programming algorithms?

Nearby-point checking is appropriate in two-variable graphical settings where an exam expects quick, transparent reasoning. Full algorithms are needed in higher dimensions or when global optimality guarantees are required. The method choice depends on model size and rigor requirements.

What goes wrong if you round each coordinate of the continuous optimum and accept it immediately?

Independent rounding can produce a point that violates one or more constraints because feasibility is joint in both variables. Even if it is feasible, it may not give the best integer objective value. You must test multiple integer candidates and compare objective values only after feasibility checks.

Why is it a mistake to compute objective values before checking constraints?

An infeasible point is not part of the admissible solution set, so its objective value is irrelevant to the optimization problem. Calculating objective values first wastes time and can mislead comparisons. Correct workflow is feasibility filtering first, objective ranking second.

Why can a sign mistake in an inequality invalidate the final integer answer?

Inequality direction determines whether a candidate belongs to the feasible region. Reversing or mishandling one sign can incorrectly accept a forbidden point or reject a valid one. Since the final choice depends on feasible candidates only, one sign error can change the entire answer.

What are the four standard integer candidates around a continuous optimum $(x^*, y^*)$?

They are formed by floor/ceiling combinations: $(\lfloor x^* \rfloor, \lfloor y^* \rfloor)$, $(\lfloor x^* \rfloor, \lceil y^* \rceil)$, $(\lceil x^* \rceil, \lfloor y^* \rfloor)$, and $(\lceil x^* \rceil, \lceil y^* \rceil)$. These points bracket the continuous optimum on the integer grid. They provide a practical first set to test in graphical LP questions.

What is a feasible integer point?

A feasible integer point is a coordinate pair where each variable is an integer and all model constraints are satisfied. This includes non-negativity and every inequality in the system. Only such points are eligible for final optimization.

What objective formula is evaluated when comparing feasible integer candidates?

You still use the same linear objective, typically $P=ax+by$, because integer constraints do not alter the formula. The difference is only which points are allowed for substitution. This keeps computation simple while changing the search domain.

Why does the continuous optimum still help when the final answer must be integer?

The continuous optimum identifies the most favorable direction of improvement for the objective over the feasible region. Integer candidates near that location often preserve much of the objective value. So it acts as a benchmark and search anchor, even though it may not be admissible.

Finding the Optimal Integer Solution | Pearson Edexcel International A-Level Maths

1. Definition & Core Concepts

Integer solution requirement means decision variables must be whole numbers, such as counts of products, staff, or vehicles. A continuous LP optimum can produce decimals because geometry and objective lines are continuous. Integer optimization is the step that converts that idealized result into a practically executable plan.
Continuous optimum vs integer optimum are different targets. The continuous optimum is the best point in the feasible region over all real values, while the integer optimum is the best point among feasible lattice points only. Because the search set is smaller, the integer optimum can never be better than the continuous optimum in a maximization problem.
Feasible integer point is any integer coordinate that satisfies all constraints, including non-negativity. Feasibility always comes before objective comparison, because an infeasible point is invalid regardless of its objective value. This separation prevents common mistakes where students compare objective values too early.

Feasible region with a continuous optimum and four surrounding integer candidate points used to choose an integer solution.

2. Underlying Principles

Why corner logic still matters: In LP, the best continuous value occurs at a boundary extreme point because the objective is linear and constraints form a convex polygon. Integer restriction removes many points, but the continuous optimum still gives a strong directional guide for where good integer points are likely to be found. This is why nearby integer points are tested first.
Rounding is not a theorem: Simply rounding $x^*$ and $y^*$ independently can violate constraints or miss a better feasible integer point. Feasibility depends on the joint pair $(x,y)$ , not each coordinate in isolation. The correct method is candidate testing with full constraint checks.
Upper-bound idea in maximization: If $P^*$ is the continuous optimum, any feasible integer value $P_I$ satisfies $P_I \le P^*$ . This gives an immediate reasonableness check for your final answer and helps detect arithmetic errors. In minimization, the inequality reverses and the continuous optimum is a lower bound.

3. Methods & Techniques

Core workflow

Step 1: Solve the LP continuously first using objective-line or vertex evaluation methods. This gives an anchor point $(x^*, y^*)$ and the benchmark objective value. Starting here is efficient because it reduces the integer search to a local check in typical exam settings.

Candidate generation and testing

Step 2: Build nearby integer candidates with floor/ceiling combinations:

(\lfloor x^* \rfloor, \lfloor y^* \rfloor),\ (\lfloor x^* \rfloor, \lceil y^* \rceil),\ (\lceil x^* \rceil, \lfloor y^* \rfloor),\ (\lceil x^* \rceil, \lceil y^* \rceil)

These are the four lattice points around the continuous optimum and are often the first high-value checks. They are only candidates, so each must be validated against every constraint.

Step 3: Filter by feasibility, then optimize by computing $P=ax+by$ only for feasible candidates. Keep a small table of candidate, feasibility status, and objective value to avoid omission errors. For maximization choose largest $P$ ; for minimization choose smallest $P$ .

Key check: Always verify all constraints before comparing objective values.

4. Key Distinctions

Comparison table

Method distinction is about search set, not formula change. The objective formula stays linear, but the admissible points change from all real feasible points to feasible integer points. This is why procedure changes even though $P=ax+by$ remains the same.

Feature	Continuous LP optimum	Integer-constrained solution
Allowed decision values	Any real values in feasible region	Whole-number values only
Typical location	Vertex of feasible polygon	Feasible lattice point, often near optimum
Selection process	Objective line or vertex method	Candidate generation + feasibility testing
Guarantee level	Global optimum over continuous set	Best among tested feasible integers
Relationship in maximization	Highest possible benchmark	Cannot exceed continuous optimum

Nearest integer vs best feasible integer are not identical concepts. The geometrically closest lattice point may fail constraints, and a slightly farther one can produce a better valid objective value. Therefore distance to $(x^*,y^*)$ is a heuristic, not the decision rule.
Exam-level local search vs full integer programming should be distinguished. In introductory graphical settings, testing nearby points is usually expected and sufficient for marks. In advanced optimization, full branch-and-bound or cutting-plane methods are needed for guaranteed global integer optimality.

5. Exam Strategy & Tips

State integer necessity explicitly when context implies counting discrete items. Examiners reward this interpretation because it shows modeling awareness, not just algebra. If the problem context is physical units of items, decimals should trigger an integer check.
Use a compact decision table with columns for point, each constraint check, and objective value. This structure prevents skipping a constraint and makes reasoning auditable. It also helps recover partial marks even if final arithmetic slips.
Apply sanity checks before finalizing: for maximization, confirm your integer objective does not exceed continuous optimum; for minimization, confirm it does not go below continuous optimum. Also verify non-negativity and whether both coordinates are integers. These checks catch most end-stage mistakes quickly.
Show rejected candidates briefly instead of erasing them. A rejected point still demonstrates complete method and may earn process marks. Clear elimination logic is often as important as the final chosen point.

6. Common Pitfalls & Misconceptions

Misconception: round each variable independently and stop. Independent rounding can produce infeasible points because constraints couple variables. Always check each rounded pair against the full system.
Pitfall: evaluating objective before feasibility screening leads to wasted work and false comparisons. Infeasible points have no admissible objective value in the model, so they should be discarded first. This ordering simplifies and de-risks the calculation.
Pitfall: assuming nearest feasible integer is globally best. The objective direction may favor a point that is not the closest in Euclidean distance. Objective value, not geometric closeness, is the final criterion.
Pitfall: forgetting inequality direction signs when substituting candidates. A single sign error can incorrectly accept or reject a point and flip the final answer. Write each check as a full inequality statement to avoid silent mistakes.

7. Connections & Extensions

Connection to modeling: Integer constraints turn a continuous resource-allocation model into a discrete decision model. This better reflects real systems such as scheduling shifts, selecting machines, or shipping whole packages. The modeling choice determines whether solutions are implementable.
Connection to computational optimization: Graphical methods work only in two variables, but the same integer idea extends to high-dimensional mixed-integer linear programming. Algorithms like branch-and-bound formalize the candidate-pruning logic used intuitively in 2D. This links classroom LP to industrial optimization software.
Connection to sensitivity thinking: If nearby integer candidates produce similar objective values, the decision may be robust to small data changes. If values differ sharply, the model is sensitive and requires careful parameter validation. This helps interpret whether the chosen integer plan is stable in practice.

Finding the Optimal Integer Solution

Summary

1. Definition & Core Concepts

2. Underlying Principles

3. Methods & Techniques

4. Key Distinctions

5. Exam Strategy & Tips

6. Common Pitfalls & Misconceptions

7. Connections & Extensions

Finding the Optimal Integer Solution

Summary

1. Definition & Core Concepts

2. Underlying Principles

3. Methods & Techniques

Core workflow

Candidate generation and testing

4. Key Distinctions

Comparison table

5. Exam Strategy & Tips

6. Common Pitfalls & Misconceptions

7. Connections & Extensions

Core workflow

Candidate generation and testing

Comparison table