I am programming a vendor bid system for school lunch.  The purchasing
manager prepares a list of items to send to bid, multiple vendors
submit their pricing.  The analysis is turning out to be tricky for a
variety of reasons:

- There may be as many as 50 vendors that respond
- There may be over 1,000 items on the "shopping list"
- The district includes forecasted quantities for each item
- Vendors rarely bid on all items on the "shopping list"
- Typically, no single vendor is picked, but instead a combination of
several vendors
- Certain staples (i.e. Milk) dominate a bid

Complete coverage of the "shopping list" (every item has a price) is
desired, though dogged pursuit of coverage can lead to combinations of
vendors that are suboptimal in a larger sense, for example, if a
certain combination of vendors manages to completely cover every item
on the shopping list, that may require the use of 10 separate vendors,
meaning the school district will spend a ton of money on delivery
fees.

Assuming there are N vendors submitting responses and the district
will allow up to M vendors to "win" the bid, what method is best to
determine the winning vendors?

Is there a better way to describe this process?  (Better vocabulary,
etc.?)

I've looked here: http://www-unix.mcs.anl.gov/otc/Guide/faq/

...and it seems like a good primer, but I'm truly a programmer, not a
mathematician.

---

Request for Question Clarification by maniac-ga on 10 Feb 2003 19:04 PST

Hello Kevoco,

Q: What method is "best" to determine the winning vendors?

A: This class of problem is generally a "discrete optimization" or
part of "operations research" where you may have limits on the
granularity (e.g., a product can be purchased by the case, not the
can). Let me suggest a brief look at
  http://www.cs.sunysb.edu/~algorith/implement/syslo/implement.shtml
which has links to descriptions and software for the
 - "Knapsack Problem"  (maximize value of selected items in a limited
space)
 - "Set Cover" (cover a set of items w/ a minimal (or lowest cost)
set)
 - "Set Packing" (cover a set of items w/o overlap)
 - "Bin Packing" (store a set of items in minimal space)
Your problem seems to have characteristics of one or more of these.

If you have some preferences in source language (or other
constraints), or want one or more of these explained more fully - to
see how they solve your problem, please don't hesitate to ask.

  --Maniac

---

Request for Question Clarification by maniac-ga on 19 Feb 2003 16:32 PST

Hello Kevoco,

Are you interested in further suggestions or do you have a solution to
your problem?

  --Maniac

Sounds like an interesting project.  Just from having read your
description, I would consider the following plan of attack:

- Determine if any single vendor can meet all the requirements and
estimate the annual cost (using forecasts of volume) for that vendor. 
[I realize you've said it unlikely that any single vendor will bid all
items, but bear with me.]

- Determine if any two vendors can meet all the requirements and
estimate the lowest annual cost for any pair of vendors who cover all
bid items.  If this cost is lower than one determined above, rank it
above that solution.  Otherwise forget it.

- Continue to consider in sequence lowest forecast solutions for 3, 4,
5, etc. vendors until a solution is found and no significant
improvements (to forecast costs) are obtained.

If you have a practical method for estimating delivery costs, you
might use them as a yardstick for assessing the significance of
"savings" by using additional vendors.

It may well be that your school district has some criteria that MUST
be met by the evaluation process, and your brief account does not
enable me to guess what these might be.  Sometimes governmental
regulations of this kind are quite counterintuitive and lead to
suboptimal bid acceptance, but bid contests and rebids can be costly
as well.

From a mathematical perspective I would label your problem as either
combinatorial optimization (picking a combination of vendors) or
integer programming.  It would be helpful to know more about the
platform you intend to implement the software on, if you'd like
implementation specific suggestions.

best wishes, mathtalk-ga

I don't know what the answer is, but I can offer a suggestion for
improving the question:  I suggest you specify somehow the relative
values of cost and coverage.

If you only considered cost, you could just buy each item from the
vendor who will sell it for the lowest cost for the forecasted
quantity.  If this approach gives you M or fewer vendors, the problem
is solved right there, but if it gives you more than M vendors, you
have to knock some off the list, which will decrease coverage,
increase cost, or both.  If coverage is more important, you will tend
to keep vendors who are sole suppliers of some items, even if they are
expensive, whereas if cost is important, you will tend to keep vendors
with low prices, even if there are some items you have to give up.  So
the algorithm needs some specific direction as to which is more
important.

For example, you might state the problem in one of these ways:

--Select the product and vendor mix with the lowest cost for 90% or
greater coverage.  (It may or may not be possible to get 90% or more
coverage with no more than M vendors.)

--Select the product and vendor mix that covers the most products for
a cost no greater than 110% of the minimum (the minimum being the
lowest cost you can get without the limitation of M vendors), assuming
all products are equally important.

--First, find the highest coverage possible with M vendors.  Then find
the lowest cost for that many products, assuming all products are
equally important.

And of course, if you are going to have incomplete coverage and some
products are more important than others, that's another possible
complication to work in.

--efn

Take a look at Data Envelopment Analysis.  I believe that it is a
framework by which
a number of heterogeneous producers can be evaluated.

You can find a starting link at:
http://www.deazone.com/

Good luck!