This is a resource allocation problem I am attempting to formulate myself, so bear with me this isn't from the 12th edition of some math book.

A miner is selecting 'rocks' from amongst his mine to haul back to the top. There are three components, or attributes, that define a rock; mineral_1, mineral_2, and mineral_3, location.

Example Rock A) 50 units mineral_1, 20 units mineral_2, 0 units mineral_3

Example Rock B) 10 units mineral_1,10 units mineral_2,10 units mineral_3

Example Rock C) 0 units mineral_1,0 units mineral_2, 95 units mineral_3

His cart can hold about** 300 units of rock, and at the top he wants to have about** 100 units of each rock component.

Example Cart 1)

Contains Rock A and C.
Holding 165 units total.
50 units mineral_1, 20 units mineral_2, 95 units mineral_3

His rocks are generally scattered about the caverns of the mine. Their removal comes at a cost of manpower. The manpower required to move a particular rock can be easily calculated as a (,say, linear) function of distance from the location of the cart.

One rock 100 yards away requires 100 rupees of man power, 99 yards, 99 rupees ... 98, 98...[nevermind other things like how much the rock weighs for example.]

**Now about the "about." Think of the cart like a grocery cart. There really is no hard limit on how much it can be stacked. For each case, choose an arbitrary limit "L" and an arbitrary minimum "M" > 0.
*For the individual components, there is a limit "l" for too many of a type of mineral, and a minimum "m" < 0 for too few of a type of mineral. * The goal being always to get as close to the ideal 100,100,100 composition.

I want to know, given full knowledge of the composition of every rock in the cave, and its location, what is the best choice of rocks to haul back to the surface on this trip which minimizes cost.

Help translate to math? I want to avoid a subjective element, meaning I don't want to have to consider any more variables or elements, particularly as it pertains to a propensity to choose 'closeness' over cost. If this is unavoidable, I need help capturing its essence concisely.

The algorithm I've roughed out it Like this:

Divide each element of each rock by the cost associated with obtaining the whole rock. Now I have the rocks in terms of their elements per unit cost, calling them "Rc"

Assume no one rock alone can overflow any element. Meaning, no rock contains more than 100 of any mineral.

  1. Cart = [mineral_1,mineral_2,mineral_3] = [0,0,0]

  2. Choose the Rc with the greatest sum, and add it to the cart.

  3. Cart = [0+Rc1,0+Rc2,0+Rc3]

  4. Here is a difficulty in choosing. Simply adding the previous rock again will most likely (though not certainly) lead to an unbalance.


  1. So I decided to create a scaler. scaler = [(100-Cart1)/100,(100-Cart2)/100,(100-Cart3)/100]
  2. To decide on the next rock to choose, I examine each Rc and do the dot product with scaler. I choose the Rc/rock that has the greatest dot product in this case.

  3. And so on until I get reasonably close to the goal.

One thing I am issues with in this case is respecting both the cart boundary and the element boundaries.


1 Answer 1


What you need to define is a utility function that incorporates the returned quantities and the cost to obtain them. How many rupees better is $100,100,100$ than $120,80,60$? Once you have that function and your constraints, this is a knapsack style problem-find the set of rocks that maximize utility. More commonly, there would be no maximum on any mineral, there would just be a price for each one, but that is a constraint like putting a maximum weight on the cart. The utility function sounds like it will be harder and more important than the optimization problem.

  • $\begingroup$ If I had a utility function, do I then have a way to determine the marginal value of each rock that I would toss in the cart? Thus, would I have my solution algorithm? $\endgroup$
    – Mr. AM
    Oct 5, 2013 at 3:35
  • $\begingroup$ It does seem hard. Have you ever had to formulate rather than just evaluate or analyze? Much more difficult I think, though a bit more fun I suppose. $\endgroup$
    – Mr. AM
    Oct 5, 2013 at 3:36
  • $\begingroup$ It can be hard. Often you are selling the minerals on the market, so don't care about balance. Then you can just assess the value of the minerals you extract minus the cost to extract them. You don't say why it is good to be close to balance. If you are producing something that takes one of each, maybe there is a market price that you can buy the shortfall. That makes it much easier. Otherwise, why isn't the objective the minimum of the minerals minus (some factor times) the cost? That is how much product you can build. $\endgroup$ Oct 5, 2013 at 3:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .