A frequent problem encountered in lowest-bidder goverment contracting is the existence of sub goals.  Typically, a lowest-bidder contract is as simple as giving the job to whoever offers to do it cheapest.  But in some cases, one must bid the lowest price possible with still giving, say 30% of the project to minority businesses, or small businesses, or some other set-aside category.  This is called a goal or subgoal, depending on who you ask.  Suppose I'm building widgets, which each require an angle (A), a bar (B), and a cog (C).  Consider the following parts suppliers:

 

Part	#1 Widget Parts Co (1)	Two-Timers, Inc. (2)	Three Ugly Brothers Supply (3)
Angle (A)	$20	$30	$15
Bar (B)	$11	$7	$12
Cog (C)	$19	$8	$23

Now, as you can see, in a normal bid I'd be best off buying A from 3, B from 2, and C from 2 for a total cost to me of $30.  When I put my markup of 10% on it, I'd bid $33.  Seems easy enough, right?  But what if I have to ensure that 30% of my total bid goes to companies (say) with headquarters in Connecticut, as per the rural Connecticut Improvement Act of 2008 and only Company 1 is located in CT?  I can't use that bid, because I've got no supplier from Connecticut!  My bid will just be thrown out.  No, now I have to give #1 a cut of the action.  So, I could buy A from them, upping my cost to $35 and my bid to $38.5, which gives them $20/$38.5 = about 51.9% of the total bid.  Or I could buy B from them, upping my cost to $34 and bid to $37.4, with them getting 29.41%, which, while cheaper, won't allow me to win the bid!  I could get C from them for a cost of $41, a bid of $45.1, and a 42.12% cut. 

There is nothing which says that the money has to go to one supplier.  There is nothing which says that there can only be one supplier who meets the subgoal.  Obviously, giving A to 1 is the way to go in this example, but how do you solve that?  This is a real problem we had around here a few months ago, and nobody had a good dynamic programming solution, because the consensus is that it's NP-complete (for reals this time).  If you can provide a good algorithm, I might even give you a shiny American dollar.

1) Find the guy who made the regulation requiring money to be pumped into CT

2) Shoot him in the face

3) Stab him in the stomach

4) Run him through with a spear

5) Take the lowest bid for each sub-assembly

6) ???

7) Profit

You're trying to find a solution to the set of inequations over an inner-product space:

[20,11,19]x/(1.1*([20,11,19]x + [30,7,8]y + [15,12,23]z)) >= .3

x+y+z = [1,1,1]

where [20,11,19]x + [30,7,8]y + [15,12,23]z is a minimum and x,y,z are three-vectors over (0,1)

The problem is it's not a linear-optimization problem since you can't just say that a linear combination of x, y and z are strictly bounded. It's Conneticut ruining everything. But the fact that you have nine highly-constrained unknowns should help with the thing. I'm not going to say that it is or is not NP-hard or -complete, but it doesn't look too bad. How much does it have to scale? Like, in the real world how many suppliers, subcomponents and constraints are there? Are all constraints second-order like the Connicut constraint or are there any that are higher-order?

Welbog:

How much does it have to scale? Like, in the real world how many suppliers, subcomponents and constraints are there?

As an example, here are the numbers from two tests (based upon real client data) we used: The first test had 105 suppliers, 43 subcomponents, and 1 constraint.  The second had 122 suppliers, 51 subcomponents, and 2 constraints which overlapped (For example, Connecticut companies and companies that only purchase American trucks.  A single company can meet and apply to both goals).

Welbog:

Are all constraints second-order like the Connicut constraint or are there any that are higher-order?

Except for a couple special cases we have resolved elsewhere, they are always like Connecticut.

 Also, perhaps I should give you a bit more of our thinking, so you can avoid wasting your time with the same things we did.  First of all, we figured we could cull the options down to 2 for any part: the lowest goal and non-goal prices (Or, with multiple goals, the lowest (g + 1) prices, where g is the number of goals).  This would leave 2^p (where p is the number of distinct parts) combinations (or (g + 1)^p for multi-goals). While it's true that you can discard all but the lowest of the non-goal prices (there's no advantages to raising the total and not the goal amounts), you can't necessarily discard all of the goal prices.  For example:

 

Part	#1 Widget Parts Co (1)	Two-Timers, Inc. (2)	Three Ugly Brothers Supply (3)
Angle (A)	$90	$30	$20
Bar (B)	$13	$10	$4
Cog (C)	$50	$10	$5

Where 1 and 2 meet the goal requirement.  1 is higher in all instances, but if we didn't consider it, we wouldn't discover the solution of A3, B1, C3 for a cost of $38, a bid of $41.8, and a percentage of 31.1%.  Instead, we would have resorted to A2, B3, C3 for a cost of $39, bid of $42.9, and percentage of 69.9%.  It's a small difference in this case, but not always.  We could design a million heuristics, but the boss wants to know that if we provide a price, it's the best price possible.

I refuse to look further into this problem until you come up with a better name for Connecticut because I can't spell Connecticut. Can we say it's Nevada's fault or some other easier-to-spell state?

Welbog:

I refuse to look further into this problem until you come up with a better name for Connecticut because I can't spell Connecticut. Can we say it's Nevada's fault or some other easier-to-spell state?

It's easy: Connect + I + Cut.  But if you insist, how about Ohio?

bstorer:

Welbog:

I refuse to look further into this problem until you come up with a better name for Connecticut because I can't spell Connecticut. Can we say it's Nevada's fault or some other easier-to-spell state?

It's easy: Connect + I + Cut.  But if you insist, how about Ohio?

Let me try it out. Ohio. Ohio. Ohio. Cleveland. Alex Papadimoulis. Ohio.

I think I can live with that.

I'm just throwing this out there, in case it sparks an idea in someone else (or if you've already thought about this, bstorer)

You have a set of companies, and a subset of those companies are Ohio companies. If the Ohio constraint didn't exist, you'd obviously go after the cheapest subcomponents from each company. So start with that as a base solution. From that total, you can figure out a lower bound on how much you need to move toward Ohio companies.

For example, in bstorer's first example, disregarding the Ohio constraint the optimal solution is C, B, B. The total bid of that is 33, and 30% of 33 is 9.9. Therefore you need to move at least 9.9 in subcomponents to Ohio. But then moving that to Ohio will contribute a bit to the total bid, so you'll need a formula that will come up with an estimation of this amount.

I've been thinking about the average of the differences between Ohio prices and optimal prices. e.g. moving any product to Ohio would cost an extra 6.43, which would raise the bid to 37.53, and 30% of 37.35 is 11.259. Now take the smallest Ohio price above 11.259 (which in this case is 19 from supplier A) and you have it. I leave it as an exercise to bstorer to see if this makes any sense in real-er data.

Welbog:

You have a set of companies, and a subset of those companies are Ohio companies. If the Ohio constraint didn't exist, you'd obviously go after the cheapest subcomponents from each company. So start with that as a base solution. From that total, you can figure out a lower bound on how much you need to move toward Ohio companies.

That's exactly what I was thinking, and would be fairly easy to implement in excel.  have your parts down the left, companies across the top, and a row below each company name describing the constraint.  Have a VBA script go through and calculate and highlight the prices where the least costly solution occurs.

Currently, even though I haven't implemented it, I'm thinking just a percent under the company name so that the algorithm can calculate whether that company's percent is matching the rule.  If multiple companies can satisfy a rule, that makes the calculation (and the rules syntax) more complex, so I'm not thinking about that yet.

Welbog:

I've been thinking about the average of the differences between Ohio prices and optimal prices. e.g. moving any product to Ohio would cost an extra 6.43, which would raise the bid to 37.53, and 30% of 37.35 is 11.259. Now take the smallest Ohio price above 11.259 (which in this case is 19 from supplier A) and you have it. I leave it as an exercise to bstorer to see if this makes any sense in real-er data.

Something is horribly wrong with my numbers. Using real numbers this time instead of the ones I seem to have just pulled from belgariontheking's ass:

The Ohio prices are 5, 4 and 11 more than the optimal prices. The average difference is 6.67, which means the new cost would be 36.67, with a bid of 40.33. 30% of this new bid has to be from Ohio, so Ohio's minimum cost is 12.10. The lowest Ohio price above 12.10 is 19 for product C from supplier 1.

Welbog:

Welbog:

I've been thinking about the average of the differences between Ohio prices and optimal prices. e.g. moving any product to Ohio would cost an extra 6.43, which would raise the bid to 37.53, and 30% of 37.35 is 11.259. Now take the smallest Ohio price above 11.259 (which in this case is 19 from supplier A) and you have it. I leave it as an exercise to bstorer to see if this makes any sense in real-er data.

Something is horribly wrong with my numbers. Using real numbers this time instead of the ones I seem to have just pulled from belgariontheking's ass:

The Ohio prices are 5, 4 and 11 more than the optimal prices. The average difference is 6.67, which means the new cost would be 36.67, with a bid of 40.33. 30% of this new bid has to be from Ohio, so Ohio's minimum cost is 12.10. The lowest Ohio price above 12.10 is 19 for product C from supplier 1.

But how does that translate to the second set I posted above where there are two suppliers from Ohio?

bstorer:

But how does that translate to the second set I posted above where there are two suppliers from Ohio?

You're not supposed to ask that, because it doesn't work right for that one.

With multiple Ohio suppliers, you'd sum up their differences and include them in the average, figure out the new bottom line and then pick the smallest price or set of prices above that line. It doesn't work with that example because supplier A's prices are so much higher than everything else. You'd have to use some kind of weighted average or possibly just omit "really big" prices entirely, but this is just a heuristic at this point and doesn't guarantee anything.

Like I said originally, it's not a solution. It's just an idea. 30% of the lowest bid really is an absolute lower bound on Ohio subcomponents. It's just that it's too low a bound to be a useful constraint. Did you explore anything like this originally?

While I can still edit this, the second example doesn't work if you include all of the Ohio supplier's prices in your calculation, but it works fine if you omit the $90 and $50 subcomponents.

Welbog:

Welbog:

I've been thinking about the average of the differences between Ohio prices and optimal prices. e.g. moving any product to Ohio would cost an extra 6.43, which would raise the bid to 37.53, and 30% of 37.35 is 11.259. Now take the smallest Ohio price above 11.259 (which in this case is 19 from supplier A) and you have it. I leave it as an exercise to bstorer to see if this makes any sense in real-er data.

Something is horribly wrong with my numbers. Using real numbers this time instead of the ones I seem to have just pulled from belgariontheking's ass:

The Ohio prices are 5, 4 and 11 more than the optimal prices. The average difference is 6.67, which means the new cost would be 36.67, with a bid of 40.33. 30% of this new bid has to be from Ohio, so Ohio's minimum cost is 12.10. The lowest Ohio price above 12.10 is 19 for product C from supplier 1.

What say we look at this table:

Part	#1 Widget Parts Co (1)	Two-Timers, Inc. (2)	Three Ugly Brothers Supply (3)
Angle (A)	$90	$623	$20
Bar (B)	$14	$7	$4
Cog (C)	$45	$11	$5

 1 and 2 are from Ohio. 1's avg difference is 40.  2's avg diff is 204. Overall average diff is 122.  Lowest cost is $29.  The correct answer is 3,2,2 = $38 cost, $41.8 bid, 43.06% subgoal.  How do you derive that using your algorithm?

Welbog:

bstorer:

But how does that translate to the second set I posted above where there are two suppliers from Ohio?

You're not supposed to ask that, because it doesn't work right for that one.

Or for the one I just posted, which shows a case of multiple subcomponents to meet the goal.  I feel like there might be some benefit to be had with techniques from regression analysis.  I'll have to think on that.

bstorer:

Part	#1 Widget Parts Co (1)	Two-Timers, Inc. (2)	Three Ugly Brothers Supply (3)
Angle (A)	$90	$623	$20
Bar (B)	$14	$7	$4
Cog (C)	$45	$11	$5

Start with 20, 4, 5 from supplier 3 as the lowest possible case disregarding Ohio which sucks.

The algorithm totally breaks because the costs are just so ridiculously big from the stupid Ohio companies. Eyeballing this you know there's no way in hell you'd go with part A from 1 or 2, nor part C from 1. Or maybe you can algorithmically say that products that are more than, say, 4 times the lowest cost are just right out. In any case, if you get rid of the really-expensive Ohio prices, you figure out that the average diffence in cost is 6.33, meaning your expected bid will be (29 + 6.33) * 1.1 = 38.86, giving an Ohio baseline of 11.66, which leads us to part B from 1 since $14 is cheaper than $18 (the sum of parts B and C from 2).

It doesn't work because it's minimizing Ohio's involvement rather than the bid. Personally I think getting rid of Ohio is the best option.

Seriously, though, my algorithm is minimizing Ohio's percentage in the final bid. It's doing that because we're picking the lowest Ohio cost higher than a critical value. How could it be changed to pick the smallest total cost satisfying the condition instead of the smallest Ohio percentage?

We know that we need more than $11.66 of Ohio involvement. Picking the smallest Ohio value greedily isn't optimal as your example shows. Picking the highest is obviously stupid. Maybe at this point it becomes a linear problem with the constraint that the final cost be a minimum, and Ohio's involvement is greater than the baseline as calculated using the heuristic above. I leave this as an exercise to you.

Welbog:

The algorithm totally breaks because the costs are just so ridiculously big from the stupid Ohio companies. Eyeballing this you know there's no way in hell you'd go with part A from 1 or 2, nor part C from 1. Or maybe you can algorithmically say that products that are more than, say, 4 times the lowest cost are just right out. In any case, if you get rid of the really-expensive Ohio prices, you figure out that the average diffence in cost is 6.33, meaning your expected bid will be (29 + 6.33) * 1.1 = 38.86, giving an Ohio baseline of 11.66, which leads us to part B from 1 since $14 is cheaper than $18 (the sum of parts B and C from 2).

It doesn't work because it's minimizing Ohio's involvement rather than the bid. Personally I think getting rid of Ohio is the best option.

Seriously, though, my algorithm is minimizing Ohio's percentage in the final bid. It's doing that because we're picking the lowest Ohio cost higher than a critical value. How could it be changed to pick the smallest total cost satisfying the condition instead of the smallest Ohio percentage?

Well, the simplest solution (in terms of amount of time required to think about it) is to generate all the possible combinations of Ohio parts which are greater than or equal to the Ohio baseline of 11.66, and sorting by the lowest difference over the low price.  In this case you'd get (in (Ohio amount, difference from low, [Ohio subcomponents]) format): (18, 9, [B2,C2]), (14, 10, [B1]), (25, 16, [B1,C2]), which means the $18 of Ohio money is best. 

The problem is that "generate all the possible combinations" part, which is often a flag that we're saying goodbye to polynomial time. Of course, it also remains to better define the decision of which subcomponent prices are too high to consider.

This is why I'm saying it reduces to a linear-optimization problem, which can be solved with the simplex method pretty fucking quickly without enumerating all possible combinations like some kind of monkey.

Welbog:

This is why I'm saying it reduces to a linear-optimization problem, which can be solved with the simplex method pretty fucking quickly without enumerating all possible combinations like some kind of monkey.

But can the simplex be applied to multiple min/maxes at the same time?

lolwut

There's only one thing to minimize, which is the bid. What do you think you're trying to minimize?

Is this a trick question where the real solution is closer to the one involving violence - that is, to actually change the laws so that the best attributes win rather than arbitrary discriminitation?

Programmatically, though, it is just an N-dimensional optimization problem with constraints.  I'm not sure I understand Welbog's variable assignments though - looks like his x,y,z vectors contain the decision to use a particular company for a particular component. (I also don't know his notation since the first inequality is a vector expression being compared to a scalar.)

The problem is you can't solve that set of equations without iteration because the result is not guaranteed to be a single value; the constraint is really |x| >= 1, not x+y+z = [1,1,1] (that is, you must use company 1 for at least one part, but you don't have to use the other companies at all).

The first issue is that you don't know if there is a single solution or multiple solutions to the problem - are there different combinations of components and suppliers which meet the constraints and have the same lowest price?  Similar to "what are the roots of x^2+b x + c = 0?" you have to have special logic to determine if there are zero, one, or many solutions to the equation. It's worse, though, as you don't even know the maximum number of solutions (which could in fact be the total number of combinations if all vendors have the same price for each component).

The only method really might be the brute-force method:  Compute all combinations that match the constraints, then compare the prices of all those combinations.

too_many_usernames:

are there different combinations of components and suppliers which meet the constraints and have the same lowest price?

In the universe of this problem, you don't care.  You just need one combination, but it has to be as low as any other bid price meeting the subgoal.

In regard to there being no solution, it's possible, but it's easy enough to check: Do you have at least one vendor meeting the subgoal requirement?  If so, you can meet the subgoal percentage.  It's stickier with multiple subgoals, but it doesn't come up very often.

too_many_usernames:

Programmatically, though, it is just an N-dimensional optimization problem with constraints.  I'm not sure I understand Welbog's variable assignments though - looks like his x,y,z vectors contain the decision to use a particular company for a particular component. (I also don't know his notation since the first inequality is a vector expression being compared to a scalar.)

The problem is you can't solve that set of equations without iteration because the result is not guaranteed to be a single value; the constraint is really |x| >= 1, not x+y+z = [1,1,1] (that is, you must use company 1 for at least one part, but you don't have to use the other companies at all).

I admit I was terse, but come on, man, put some thought into it. I said it was an inner-product space. The inner product of two vectors is a scalar, which is what was being compared and minimized. I specifically said it had to be an inner-product space so that this would be understood without me needing to write out a fancy inner-product symbol. Also, the constraint x+y+z=[1,1,1] exists because you need one of each subcomponent. Yes, you're right that there is a further constraint that ||x|| >= 1, but x+y+z=[1,1,1] is still a necessary and valid constraint.

Welbog:

I admit I was terse, but come on, man, put some thought into it. I said it was an inner-product space. The inner product of two vectors is a scalar, which is what was being compared and minimized. I specifically said it had to be an inner-product space so that this would be understood without me needing to write out a fancy inner-product symbol. Also, the constraint x+y+z=[1,1,1] exists because you need one of each subcomponent. Yes, you're right that there is a further constraint that ||x|| >= 1, but x+y+z=[1,1,1] is still a necessary and valid constraint.

 

Ah, I did misread the first inequality - it is all scalar. I also realized you covered the inequality by the equation >= 0.3 (the 30% from 'Ohio' requirement) (so ||x||>=1 is not required - it's actually the wrong constraint in this instance).

 

I'm still a bit confused though ... you wrote [20,11,19]x so I thought x was the vector representing the components sourced by company A.  Thus to ensure one of each component wouldn't you need three constraints:

[1,0,0](x+y+z) = 1

[0,1,0](x+y+z) = 1

[0,0,1](x+y+z) = 1

instead of x+y+z = [1,1,1]?

So I guess at the end of the day, I only disagree with the x+y+z = [1,1,1] bit =)

too_many_usernames:

I'm still a bit confused though ... you wrote [20,11,19]x so I thought x was the vector representing the components sourced by company A.  Thus to ensure one of each component wouldn't you need three constraints:

[20,11,19]x is the portion of the bid's cost that comes from supplier 1. Each x, y and z represents the products coming from a given supplier. Since we need one and only one of each product, x+y+z = [1,1,1], indicating one and only of product A, B and C in total from all suppliers. Your three equations

too_many_usernames:

[1,0,0](x+y+z) = 1

[0,1,0](x+y+z) = 1

[0,0,1](x+y+z) = 1

mean the same thing as x+y+z = [1,1,1]. They're just a much less elegant and meaningful way of saying the same thing.

Welbog:

too_many_usernames:

[1,0,0](x+y+z) = 1

[0,1,0](x+y+z) = 1

[0,0,1](x+y+z) = 1

mean the same thing as x+y+z = [1,1,1]. They're just a much less elegant and meaningful way of saying the same thing.

 

Crap, they are equivalent. Stupidly obvious now that I'm looking at it again...

You know, I think my current work (trying to reivew a requirements document that is full of things that are not requirements) is obviously damaging my vector math ability, so I'm just going to stop thinking about it today.

The more I screw with this, the more I'm certain it's just the napsack problem.

 

I think the real lesson here is that Alan Turing does not think it is possible to improve the plight of the downtrodden Connecticutian without pissing away more money than is necessary or building a quantum computer out of qubits and lasers.

Welbog:

The problem is it's not a linear-optimization problem since you can't just say that a linear combination of x, y and z are strictly bounded. It's Conneticut ruining everything.

I think it is a linear-optimisation problem, if you need a large enough number of parts that you can pretend the unknowns vary continuously and you can split orders for any part. Calling A_i, B_i, C_i the proportion of parts A, B, C you buy from provider i, you want to minimise A_1*20+A_2*30+...+C_3*23 under the constraints

A_i >= 0
B_i >= 0
C_i >= 0
A_1+A_2+A_3 = 1
B_1+B_2+B_3 = 1
C_1+C_2+C_3 = 1
 A_1*20+B_1*11+C_1*19 >= 0.33*(A_1*20+...+C_3*23)

If memory doesn't fail me (and it's decades since I learned the stuff, so it may), that's a linear-optimisation problem.

Ilya Ehrenburg:

If memory doesn't fail me (and it's decades since I learned the stuff, so it may), that's a linear-optimisation problem.

Just because you can express all of the unknowns in a linear relationship doesn't make the whole thing a linear problem. Take a look at http://en.wikipedia.org/wiki/Linear_programming, which clearly states that in order to qualify as a linear problem, the right-hand side of a constraint inequality has to be known. In your example it isn't. If you were to express it as a known (the only know we have there is .33), you have to express the left-hand side as a reciprocal (and therefore non-linear) function. That's my motivation for estimating the right-hand side of your equation using heuristics, which, if selected carefully, will end up with a linear problem.

bstorer:

This is a real problem we had around here a few months ago, and nobody had a good dynamic programming solution, because the consensus is that it's NP-complete (for reals this time).  If you can provide a good algorithm, I might even give you a shiny American dollar.

Take a look at this: http://en.wikipedia.org/wiki/Integer_linear_programming#Integer_unknowns

If the unknown variables are all required to be integers, then the problem is called an integer programming (IP) or integer linear programming (ILP) problem. In contrast to linear programming, which can be solved efficiently in the worst case, integer programming problems are in many practical situations (those with bounded variables) NP-hard. 0-1 integer programming or binary integer programming (BIP) is the special case of integer programming where variables are required to be 0 or 1 (rather than arbitrary integers). This problem is also classified as NP-hard, and in fact the decision version was one of Karp's 21 NP-complete problems.

(Emphasis mine)

If integral solutions to similar linear systems are NP-complete, the non-linear case is most likely NP-hard and quite possibly -complete as well.

My idea of reducing the problem to a linear programming problem would also be NP-complete. No point in continuing that line of reasoning (or any, for that matter).

Welbog:

 

My idea of reducing the problem to a linear programming problem would also be NP-complete. No point in continuing that line of reasoning (or any, for that matter).

Unless you can come up with a worthwhile dynamic programming solution, because even that would be better than nothing.

Welbog:

Ilya Ehrenburg:

If memory doesn't fail me (and it's decades since I learned the stuff, so it may), that's a linear-optimisation problem.

Just because you can express all of the unknowns in a linear relationship doesn't make the whole thing a linear problem. Take a look at http://en.wikipedia.org/wiki/Linear_programming, which clearly states that in order to qualify as a linear problem, the right-hand side of a constraint inequality has to be known. In your example it isn't. If you were to express it as a known (the only know we have there is .33), you have to express the left-hand side as a reciprocal (and therefore non-linear) function. That's my motivation for estimating the right-hand side of your equation using heuristics, which, if selected carefully, will end up with a linear problem.

 

Rewrite the last equation as 

0.67*A_1 + 0.67*B_1 + 0.67*C_1 - 0.33*A_2 - ... - 0.33*C_3 ≥ 0, 

then you have a linear system with known right hand side. The inequalities define a compact convex polyhedron. That isn't empty, so the (linear) cost-function takes its minimum in an extremal point, which is findable by the simplex algorithm.

Ilya Ehrenburg:

Rewrite the last equation as  ...

Fair enough.

I'm not sure why I didn't think of that. It's kind of a moot point, though, since it's still an NP-complete problem.

Bstorer might find that the simplex algorithm is faster than his current brute-force method, though, so it might be worth a shot.

Welbog:

some other easier-to-spell state?

I always remember it as "CONNECT Interface Code to Unit Test".

We're all geeks, it should work.