An alloy from scrap
A foundry melts an alloy from scrap. The store holds n kinds of raw material: for each, the price per kilogram in tenge, how much there is, and what share of each of k elements it contains are known. Exactly M kilograms of alloy must be produced, in which the share of each element lies within given limits. Raw material can be taken in any amount up to the stock, including fractional amounts. What is the lowest price of the batch?
An element’s share in the alloy is its mass in all the raw material divided by M. The rest of the raw material is impurities, with no limits on them.
Input
The first line holds n, k, M (1 ≤ n ≤ 60, 1 ≤ k ≤ 10, 1 ≤ M ≤ 105). Then n lines: the price p (1 ≤ p ≤ 105), the stock s in kilograms (0 ≤ s ≤ 105) and k element shares in tenths of a per cent (integers from 0 to 1000 with a sum of at most 1000). Then k lines: the lower and upper limit of an element’s share in the alloy, also in tenths of a per cent, 0 ≤ lo ≤ hi ≤ 1000.
Output
The lowest price of the batch, or IMPOSSIBLE if such an alloy cannot be made from this raw material. The answer is accepted with an error of up to 10−6 of the answer (and up to 10−6 absolute for numbers below one).
Examples
Example 1
3 2 100 4200 100 999 0 1500 100 0 995 2600 100 650 340 600 630 360 400
251538.4615
Example 2
3 2 100 4200 100 999 0 1500 10 0 995 2600 100 650 340 400 500 500 600
IMPOSSIBLE
Limits
- Time · Python
- 5000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 9 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
The unknowns are how many kilograms of each raw material to take, x1, …, xn. The mass, the element shares, the stocks and the price are all linear expressions in x. So it is a linear problem.
2Hint 2
The inequalities must be turned into equations. For “at most” add a non-negative slack variable with a plus sign, for “at least” with a minus. Then the problem takes the form A·x = b, x ≥ 0, price → min, and the two-phase simplex method solves it.
3The idea
The rows: Σxj = M; for each raw material xj + sj = stock; for each element Σ sharej·xj − u = lo·M and Σ sharej·xj + v = hi·M. 1 + n + 2k rows in all. Phase 1 with artificial variables finds a feasible blend or proves there is none: if the sum of the artificials did not reach zero, the answer is IMPOSSIBLE. Phase 2 decreases the price.
4Walkthrough
The tableau is dense: at most 81 rows and 221 columns including the artificials. The entering column is the one with the most negative reduced cost; after many consecutive steps that do not move the point, the first suitable one by number (Bland’s rule), so as not to cycle. The leaving row is by the minimum ratio, and on a tie the one with the smaller basic variable number. All comparisons use a tolerance of 10−9; the answer is Σ pricej·xj at the vertex found.
4+Solution
5Complexity
A step is O(m·n) ≈ 2·104 operations. How many steps cannot be said in advance (the simplex method has no guarantee of a polynomial number of steps), but on the largest test the Python solution fits in a quarter of a second.
6Common mistakes
- Forgetting the stocks. This is
wrong.py: without the “at most the stock” constraint the whole alloy is made from the most profitable raw material, and in the second example a price comes out instead ofIMPOSSIBLE. - Greed. Taking the cheapest raw material first and then fixing the shares does not work: cheap scrap can spoil the composition so that it has to be fixed with expensive pure metal.
- Negative right-hand sides. Before phase 1, rows with a negative right-hand side are multiplied by −1, otherwise the artificial variables start from negative values.
- Whole kilograms. The problem allows fractional amounts; requiring integers would make it an integer programming problem, solved by branch and bound on top of the same simplex method.