An integer-programming algorithm cannot repair a model that expresses the wrong decision. Here we translate several common logical statements into linear inequalities, then prove that the translation preserves the intended choices.
A switch for an activity
Definition 3.4.1
(On/off switch, minimum level and fixed charge)
Suppose a machine can make an amount between zero and a known capacity . A binary with meaning enabled and meaning off is an on/off switch for when
A minimum level with adds . A fixed charge for enabling the machine is represented by in the objective, in addition to the variable cost .
Theorem 3.4.2
(The feasible production set of a switched activity)
The on/off constraints have projection onto , with forced when . With the minimum level added, the projection is exactly .
Proof
(Two binary cases)
If , the constraints read (and ), so . If , they read , respectively . Conversely, is feasible with and every in the stated interval is feasible with . The projection is the union of the two cases.
This is an on/off condition, not the assertion that whenever : the pair is still feasible. For a continuous variable, the statement “ exactly when ” with arbitrarily small positive values is not captured by choosing an arbitrary positive : doing so would discard legitimate small production amounts.
The fixed charge is paid whenever , including when the enabled machine is idle. If , and changing only from one to zero at preserves all other constraints, no optimum of the minimization problem has : that change reduces cost. If also satisfies other constraints, however, that argument may fail. A zero fixed charge likewise gives no reason for an idle switch to be zero.
Worked example 3.4.3
(Choosing capacity with a fixed charge)
Meet a demand of units. Machine A can produce up to , at cost per unit plus a fixed charge of if enabled. Machine B can produce up to , at cost per unit with no fixed charge. Oversupply is not allowed. With and , minimize
If , the only choice is , costing . If , substitution gives cost , so within the best choice is at cost . Thus enabling A is optimal. Its physical bound is , but the balance and nonnegativity also imply ; using is a valid tighter formulation for this specific model. The calculation compares both binary cases and therefore proves global optimality.
Conditional constraints and valid bounds
Let contain all the constraints that apply regardless of a switch. To enforce
use with binary.
Definition 3.4.4
(A valid big- constant)
A finite is valid for this implication if
If the inactive branch is empty, every is valid.
Theorem 3.4.5
(Exactness of a big- implication)
If is valid, the constraint imposes when and excludes no allowed point when . If every has finite bounds in , then
is valid.
Proof
(Case check and a componentwise bound)
At the inequality reduces to . At it reads , which every allowed inactive point satisfies by the definition of a valid . For the box bound, each term is at most when and at most when ; summing bounds over all of , hence over the inactive branch.
The reverse implication is not imposed: an inactive point may happen to satisfy . If no finite upper bound on the possible violation exists, this construction has no valid finite ; infinity is not a linear-program coefficient. One must find further valid bounds or use a different formulation.
A small invalid silently removes intended choices; an excessively large valid one weakens the LP relaxation and may worsen numerical behavior. Neither should be chosen merely because it looks large.
Worked example 3.4.6
(Testing two values of )
Let and require , with every in the interval allowed when . The largest inactive violation is , so is the smallest valid value, and the box formula gives the same number. Taking gives , which at reads and wrongly excludes that point; taking gives and preserves it.
Either-or decisions
Worked example 3.4.7
(Encoding two disjoint intervals)
Suppose and the permitted values satisfy or . Let select the first branch and the second:
For these become and ; for they become and . The constants and are the valid big-M values from the global bounds: the maximum violation of the first and second branch. Conversely, every point in either interval can be assigned its corresponding . The projected feasible set is exactly .
In general “or” is inclusive: if two branches overlap, points in the overlap may admit either switch value. Enforcing both branch inequalities without switches would instead describe their intersection.
A binary–continuous product
Theorem 3.4.8
(Exact linearization of a binary–continuous product)
Suppose are known finite bounds and is binary. Then with satisfies
if and only if .
Proof
(Check the two binary cases)
If , the first pair forces ; the second pair reduces to , which follows from . If , the second pair forces ; the first pair is then just the original bound on . Hence every feasible triple has , and every bounded with binary and satisfies all four inequalities.
Proof X-ray
Each pair is tight in one case and redundant in the other
The four inequalities are two big-M pairs. The pair is the switch: it pins to when and is harmless when only because already holds. The pair is the link: it pins to when , and when it reads , which is again exactly the bound on . So the bounds and play the role of valid big-M constants in both pairs.
No sign assumption is used anywhere; the proof works for . What is used is that and are true bounds. If were smaller than the largest possible , the case would impose and remove feasible points.
The counterexample below shows how each part of the formulation fails when it is altered.
Counterexample mode
Why the bounds matter
If , and , then is correct. Adding the common special-case constraint would wrongly exclude it. Conversely, omitting the inequalities that link to when allows, for example, , which is not the product. The full formulation and its stated domain matter.
Common mistakes
Common mistake
(Reading an on/off switch as forcing positive production)
The constraint forces when but does not force when ; is feasible. If enabled production must be at least , the constraint must be added explicitly.
Common mistake
(Using a bound that is not valid for the model)
For , writing the product formulation with makes the case impose , which excludes the allowed point . Bounds used as big-M constants must hold for every allowed point, not just for the points one expects at an optimum.
Exercises
Quick check
(An activity is either off or produces between and units, paying fixed charge and variable cost per unit. Formulate the feasible set and cost. Is feasible?)
Solution · Answer
Use , , and cost . At one gets ; at one gets . Thus is infeasible.
Quick check
(For , encode with the smallest nonnegative valid when all domain points are allowed at . Show a point excluded by .)
Solution · Answer
The maximum violation is , so is valid and is the smallest valid nonnegative value. With , the intended inactive point violates .
Quick check
(For , write the four inequalities for . Determine at and .)
Solution · Answer
The inequalities are and . At the second pair gives , so ; at the first pair gives .
Quick check
(Minimize subject to and or , using the either-or formulation above and solving both branches. Is the point feasible?)
Solution · Answer
At , , whose minimum is ; at , , whose minimum is . The overall minimum is . The value lies in neither interval and is infeasible for either switch value.