Tensions in Practice: A quick lower bound in tension with an executable discrete plan¶
Supplying at least three units of capacity
A whole lot of type A supplies 2 capacity units and costs 10; a whole lot of B supplies 3 and costs 17. At least 3 capacity units are required. Allowing fractional lots gives 1.5 of A at cost 15, a lower bound. Whole lots instead favor one B at 17. Simply rounding 1.5 A up to two A produces cost 20, which is feasible but worse than B.
Bound the best possible cost
Temporarily drop indivisibility to obtain a lower bound.
Produce an executable purchase
Retain whole-lot choices and find the cheapest admissible plan.
Why these aims pull against each other
The relaxed problem is useful precisely as a relaxation. Its fractional optimum cannot be ordered, and rounding its chosen type does not by itself solve the discrete choice.
Choose an arrangement to see what changes and what remains difficult.
A lot supplies 2 units for 10; B supplies 3 for 17. Allowed refers to the active model, not physical permission to buy fractional lots. Highlighting selects that model’s minimum; a relaxed minimum is only a lower bound for the whole-lot problem.
What this choice protects
What it costs
When it fits
Compare the arrangements
Compute a fractional bound
Allow nonnegative real quantities of both lot types. A costs 5 per capacity unit and B costs 17/3, so exactly 1.5 A attains the relaxed minimum 15.
| Capacity | Allowed? | Cost | |
|---|---|---|---|
| 1.5 lots A | 3 | Yes | 15 |
| 1 lot B | 3 | Yes | 17 |
| 2 lots A | 4 | Yes | 20 |
- What it protects
- Cost 15 is a valid lower bound on every whole-lot plan under this model.
- What it costs
- The selected fractional quantity is not executable and leaves the integer choice unresolved.
- When it fits
- Fits early bounding or an intermediate optimization step that explicitly defers discrete feasibility.
Illustration note: The toy calculation is easy under both models. The general appeal of relaxation is not a measured runtime improvement in this example.
Require whole lots
Restrict both quantities to nonnegative integers. One B costs 17; two A cost 20. No cheaper whole-lot plan supplies the required capacity.
| Capacity | Allowed? | Cost | |
|---|---|---|---|
| 1.5 lots A | 3 | No | 15 |
| 1 lot B | 3 | Yes | 17 |
| 2 lots A | 4 | Yes | 20 |
- What it protects
- The 17-cost plan is executable within the declared whole-lot model and is optimal here.
- What it costs
- Discrete feasibility must be checked rather than inferred from a rounded relaxed answer; the optimum is 2 above the lower bound.
- When it fits
- Fits the stage where an actual whole-lot choice is required.
Illustration note: The bound and plan are complementary outputs and may be used sequentially. The gap is not an error in either correctly stated problem.
What this illustration does—and does not—establish
The source supplies the structural tension. This bounded example makes a particular relation inspectable; the aims, conditions and residual costs are part of the comparison.
- Capacities, prices and unlimited lot availability are invented; no purchasing action or empirical solver-performance claim is involved.
- The three displayed plans explain the comparison; the optimization domains include all nonnegative quantities of the respective type.
- All costs are positive. A-only feasible integer plans need at least two lots; any plan containing B costs at least 17, establishing the displayed optimum.
Source entries
Integer Linear Programming (ILP)
The canonical tension motivates this comparison. The setting and arrangements are declared editorial illustrations, not observed findings.
Discrete-Choice Fidelity vs Continuous-Relaxation Quality
The integrality constraints capture the discrete reality of the problem (you cannot open half a warehouse, run 0.4 of a vehicle, or assign 0.7 of a worker), but the LP relaxation (dropping integrality) provides the essential bound used by branch-and-bound.
The source operation
Integer linear programming is the variant of linear programming in which some or all decision variables are required to take integer values