One capacity with chosen items, and every requirement covered by at least one chosen set: these are the two models most practical binary programmes are assembled from. Their relaxations are fractional in characteristic ways — one splits a single item, the other spreads halves across overlapping sets — and that is exactly why a relaxation's value is a bound rather than an answer.
Core ideas
Two models and one idea about both of them: the way a relaxation goes fractional is a property of the model's shape, not an accident of the data.
Maximise Σ v_j y_j subject to one row Σ w_j y_j ≤ W. Every selection problem with a single budget is this model: which features to ship in a release, which repairs to fund this year, which crates to load. The binaries make it hard; the single row makes it the smallest hard model there is.
Minimise Σ c_j y_j subject to one row per requirement saying that at least one set containing it is chosen. Depots covering districts, shifts covering hours, tests covering code paths. The rows outnumber the variables and each one is an “at least one of these” from the previous lesson.
The relaxed knapsack fills in value-per-weight order and splits exactly one item, because one row can only be tight in one place. The relaxed covering problem does something else entirely: on a ring of overlapping sets it puts 1/2 on every one of them, satisfying each row with two halves and paying half the price.
The material
Both models from data, both relaxations solved, and the three numbers each one produces.
Items 1, …, n with values v_j and weights w_j, and a capacity W. Choose y_j ∈ {0, 1} to maximise Σ v_j y_j subject to Σ w_j y_j ≤ W. The name is the picture: one bag, a weight limit, and each item either in or out.
Requirements 1, …, m and sets 1, …, n with costs c_j, where set j covers some of the requirements. Choose y_j ∈ {0, 1} to minimise Σ c_j y_j subject to, for each requirement i, the row Σ y_j ≥ 1 taken over the sets that cover i. Replacing that ≥ by = gives set partitioning, which is a different problem.
Take three items worth 60, 100 and 120 weighing 10, 20 and 30, with a capacity of 50. Their values per unit weight are 6, 5 and 4, so the relaxation loads the first two whole — thirty units of weight, 160 of value — and then takes 2/3 of the third to fill the bag, for 240. That is the bound.
The relaxation is worth 240 and gets there by splitting the third item. Greed by value per weight takes the first two, cannot fit the third in the remaining twenty units, and stops at 160. The best whole choice, found by trying all eight subsets, is the second and third items together: weight exactly 50, value 220. So 240 ≥ 220 ≥ 160, and the middle number is the only one that is an answer.
Discrete Mathematics’ “Greedy Algorithms” closes by showing the value-per-weight rule optimal for the fractional problem and defeated by the 0/1 version, which is precisely the gap between 240 and 160 here. The rule is not a heuristic for this model; it is the exact solution to the relaxation, and the two facts are easy to confuse because the arithmetic is the same.
Five districts in a ring, each reachable from two of five depots, every depot costing 2. Each row says “at least one of these two depots”. The relaxation satisfies all five rows by opening every depot to the extent of 1/2, and pays 5. No whole choice does: three depots are needed, costing 6. The 1 between them is the price of not being able to open half a depot.
On that same ring, require each district to be covered exactly once instead of at least once. Nothing in the data changed and only the relation did, and now there is no feasible choice of depots at all: an odd ring cannot be partitioned by adjacent pairs. The relaxation of the partitioning version is still solvable and still worth 5, which is the cruellest part — a relaxation being feasible says nothing about whether the integer problem is.
Both atoms above were solved exactly by enumerating every subset, and that is where this lesson's method ends: 2¹² is 4096, which is instant, and 2⁵⁰ is not a number of subsets anybody enumerates. What is this lesson's own is the pair of models and the shape of their relaxations. Four results about them are used here and proved elsewhere, each by its owner.
None of those four is derived here, and none of them is needed to write the models down. What is needed is the reflex of solving the relaxation first and looking at what it made fractional, because the split item and the spread halves each point at the row doing the work — which is the variable to branch on when the search lesson arrives.
Interactive
Two atoms of binary modelling, and the characteristic shape of each relaxation
Method
The same five steps for both models. The fourth is where a relaxation earns its keep.
An item taken, or a set opened. If the answer is “how many of them”, this is not one of these two models and a binary is the wrong variable.
A knapsack has exactly one row, and a second row means a second model. A covering problem has one row per requirement, and each row lists the sets that cover it — which is read straight off the incidence table.
One split item, or a scatter of halves. This is the diagnostic step: it tells you which row is binding and, later, which variable to branch on.
Greed by value per weight, or greed by cost per newly covered requirement, gives one. Enumeration at this size gives the best one. Two whole numbers are worth more than one, because their difference is what greed cost.
z_LP ≥ z_IP ≥ z_greedy for a maximisation, reversed for a minimisation. Write all three and label them; a covering result reported as one number cannot be told apart from a guess.
Both atoms on one page, each solved three ways. Every figure is the lab's, on its opening presets.
The knapsack's two gaps say different things. The 20 above is what integrality costs on this instance; the 60 below is what greed costs. Only the first is a property of the model — the second would change if greed were replaced by anything better, and the bound would not.
The covering relaxation's halves are worth a second look. Every one of the five rows is satisfied with nothing to spare, and the total is 5 against an answer of 6. That is the characteristic shape: a covering relaxation pays for the rows and not for the indivisibility, and on an odd ring the indivisibility is the whole cost.
For a faded rehearsal, drop the knapsack capacity to 40 and redo all three numbers. The supplied first move is that the density order does not change, because the items did not — so the relaxation is still items 1 and 2 whole and then a fraction of item 3, and only the fraction moves. Work out the fraction, then the exact optimum, and say what happened to each of the two gaps.
You should be able to formulate a knapsack and a covering instance from data, solve both relaxations, name the single split item in one and the spread halves in the other, produce a greedy answer and an exact one by enumeration at this size, state both gaps, and say what changes when a covering row becomes an equality.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.