Search integer decisions with valid pruning

Try

Maximize 3x+2y subject to 2x+y≤4, x+2y≤4 and nonnegative integer x,y. The LP relaxation has intersection x=y=4/3 and value 20/3. Integer point (2,0) gives value six. There might still be a better integer point between six and 20/3, so branch on the fractional x coordinate. Every integer x satisfies x≤1 or x≥2. These two child regions cover all integer possibilities while excluding the current fractional point.

Predict

Predict the bounds after branching. In the x≥2 child, the first resource constraint forces x=2,y=0, giving six. In the x≤1 child, the relaxed optimum is x=1,y=3/2 with value six. Since a feasible incumbent already achieves six, neither child can improve it. The proof does not require every child LP optimum to be integer; a valid bound that matches the incumbent is enough to prune a branch when seeking one optimum.

Experiment

Trace the search using a small ledger. Distinguish a feasible integer value from a relaxation bound.

Node	Relaxation bound	Integer evidence	Action
Root	20/3	Incumbent 6 at (2,0)	Branch on x
x≤1	6	Fractional relaxation allowed	Prune by bound
x≥2	6	(2,0) feasible	Close node

Verify the left bound algebraically: its best y is limited by (4−x)/2 in the relevant region, giving objective at most 4+2x≤6. Once all active nodes are closed, the incumbent six is certified globally optimal. The root relaxation gap has been closed by logical coverage and bounds, not by rounding its fractional solution.

Understand

Branch and bound maintains a tree of subproblems whose integer feasible sets cover the original possibilities. A fractional coordinate r creates branches xⱼ≤floor(r) and xⱼ≥ceil(r), disjoint for integer values. A maximization node can be pruned if infeasible, if its relaxed optimizer is integer and no further improvement remains, or if its valid upper bound is no greater than the best known feasible integer value. Every pruning reason must be mathematically justified.

The largest upper bound among unresolved nodes, together with the incumbent value, bounds the global optimum. If all feasible objective values are integers, a fractional upper bound can be rounded down, but only after proving that objective integrality applies. A rational objective with arbitrary denominators cannot use that shortcut without scaling or another lattice argument. Finite termination is guaranteed for a bounded integer search space with progressing exhaustive branches and exact valid node solves. A time-limited computation instead has an unfinished status, even if its incumbent appears excellent.

Apply

Suppose a maximization run stops with incumbent twelve and unresolved node bounds thirteen, eleven and 12.5. The global upper bound is thirteen and the absolute gap is one. The node bounded by eleven can be discarded; the others still prevent an unconditional optimality claim. If objective values are even integers, the upper bound can be tightened to twelve and the incumbent certified. Explain the extra arithmetic fact that changes the conclusion.

If the goal is to enumerate every optimal solution, pruning nodes whose bound equals the incumbent can remove alternative optima. The usual equality pruning is valid for finding one best value and one corresponding solution, not automatically for complete enumeration. State the requested output before choosing a stopping or pruning policy.

Continue

Report the incumbent, bound, gap, open-node status and stopping reason. An exact certificate can be short even when discovering it took a long search. Continue to Multiobjective and Pareto decisions, where there may be several incomparable good decisions rather than one scalar objective. Bounds still matter, but the definition of improvement must first be clarified.