My company is using some very old DOS software (for which there is no
upgrade/replacement), and we want to duplicate its functionality in a
newer program. I need a special algorithm to do so.
We have subcontractors who bid on different divisions of work (let's
say the divisions are 1,2,3, and 4). Subcontractor A may bid $40,000
to perform on divisions 1 and 2, while subcontractor B bids $20,000 to
perform divisions 1 and 4, and Subcontractor 3 bids $3,000 for
division 1 alone.
I need an algorithm that will calculate the lowest bid path, given
these overlapping bids. We can't do it by trial and error because in
reality there may be 50+ divions of work and hundreds of subs, and the
results need to compute almost instantly. It's much easier to
visualize, so I've posted an example bid sheet in Excel format at
http://www.soltekpacific.com/bidSample.xls.
A $100 tip will be given to the first answerer who provides a usable
solution upon our own testing of said solution (within 24 hours of
question being answered, we won't drag our feet on it). |
Request for Question Clarification by
tox-ga
on
05 Aug 2006 13:04 PDT
njovin-ga,
I have an algorithm in mind for producing the results you want but, I
need to clarify some things first.
In the example you gave, there are two problems. First, nobody has bid
on division #3. Should I just ignore divisions that aren't bid on?
Second, if these are all the bidders, then so far, it would be the
cheapest to go with subcontractor B since it maximizes coverage while
minimizing costs.
To be more concise, there is no guarantee that every subdivision will
be bid on, or even if they are, the grouped nature of the bids do not
guarantee a solution that minimizes the average cost (for example,
obviously it's cheaper/division if you hire sub #3, but to maximize
coverage, you need to hire A or B). The question is then, what do you
want to minimize when you mean "lowest bid path". Do you want as
complete coverage of all the divisions as possible while accepting it
may mean higher average costs? Or simply have the lowest average cost
while ignoring coverage?
Cheers,
tox-ga
|
Clarification of Question by
njovin-ga
on
05 Aug 2006 13:39 PDT
The example I gave was a bad one, I just threw that spreadsheet
together. When we actually DO run a bid, we have bids on ALL
divisions of work. If a division does NOT have a bid, the program we
are writing will notify the user and usually a rough estimate will be
punched in for that division.
To answer your question more specifically, we want the lowest possible
cost, ignoring any coverage problems, as the coverage problems will be
addressed by the estimator using the software. The algorithm only
need find the lowest cost for the divisions that DO have bids.
|
Request for Question Clarification by
maniac-ga
on
05 Aug 2006 18:07 PDT
Hello Njovin,
After downloading your spreadsheet, I made a slight change and posted it at
http://homepage.mac.com/mhjohnson/maniac-ga/njovin/bidSample.xls
The first sheet has your original data. The second has a 'solution"
for the first sheet based on:
- selecting all contractors that are the sole bidders on a division
(e.g., Johnson, Acme, Kevin).
- for those divisions that remain, select the "minimum cost" that
covers the (may have overlap) that set of divisions. For example,
choose John over ABC due to cost to cover #2 and choose John over
Smith due to cost to cover #7 and #8.
Yes - there is overlap on #10 and #11, but I assume you have some way
of taking care of that.
Is this the kind of solution you are looking for? If so, it should be
relatively simple to automate that process and meet your timing
constraints.
--Maniac
|
Request for Question Clarification by
tox-ga
on
05 Aug 2006 23:24 PDT
njovin-ga,
Two questions before I post the pseudo-code:
Let's say there are 4 divisions 1, 2, 3 and 4 and 3 subs A, B and C.
A bids 100000 for 1 and 2
B bids 200000 for 3 and 4
C bids 2000 for 2 and 3
Would you pick A and B or just C?
Same setup, now:
A bids 1000 for 1, 2 and 3
B bids 2000 for 2, 3 and 4
C bids 10000 for 1, 2, 3 and 4
Would you pick only C? or would you pick A and B, with some way to
deal with the overlapping?
Cheers,
tox-ga
|
Clarification of Question by
njovin-ga
on
06 Aug 2006 12:20 PDT
Maniac - this IS the kind of solution we're looking for, with one
exception. There can be no overlap. Therefore, if two subcontractors
bid on the same division (in your example, Johnson and David overlap
on division 11), they cannot both be selected, we must choose one or
the other.
As I said before, when we run the actual bid, there's a much larger
sampling of subs and much less overlap. I've added a third sheet to
the excel file and reposted it at
http://www.soltekpacific.com/bidSample.xls
This sheet shows the same bid, but with a more realistic sampling of
subs, and the solution for the bid that the algorithm should come up
with.
Tox - In your first example,the ALGORITHM would come up with A and B
because there can be no overlap. The software we are writing will
have a series of warnings in place that will SUGGEST to the user
(estimator) that they fill in an amount for my company to self perform
divisions 1 and 4 in the first example, and let C perform 2 and 3,
because the dollar amount difference in the bids is so huge. Thus, the
estimator would enter company D (my company), and fill in a bid for D
to complete 1 and 4 (say, for $3000), and then the algorithm would
recalculate and solve for company C to perform 2 and 3 and D to
perform 1 and 4 for a total cost of $5000.
In your second example, the algorithm would come up with using C,
because there is no overlap and all divisions are covered. The
estimator using the software would see the massive difference in the
bids, and again, fill in an estimate for my company to self-perform
the work, in essence adding a D again, and entering new bid amounts
for the algorithm to recalculate.
You guys are both on the right track. I'm excited to see what you come up with.
|
Hello Njovin,
OK. I have put an updated version of your worksheet at
http://homepage.mac.com/mhjohnson/maniac-ga/njovin/bidSample.xls
which includes a single macro named "bidSample" that performs the
calculations - and reproduces your result for the sample data (in
about a second). Note that the "red" regions all have a non-blank
value entered in them (I used 1, but any non-empty cell should work).
That is how the macro determines if a subcontractor has bid on a
division of work. I MAY be able to cue off of the cell formatting -
please let me know if you need that changed (and I'll see if it is
feasible).
The following describes how the spreadsheet / macro works and a few
ideas on making changes (if necessary). Please follow up with a
request for clarification if you have ANY problems with the macro or
need it adjusted for your specific worksheets.
First - a note on Excel security. If you cannot run the macro, please
check your security settings. I did not "sign" the macro so you need
to be at "medium" security level (or lower - but I don't recommend
low...). For reference, see another answer I've provided at
http://answers.google.com/answers/threadview?id=736450
which describes some of the alternatives in the first clarification.
To run the macro, use the menu
Tools -> Macro -> Macros...
select bidSample and then Run.
If you want to view the macro code (to follow along the explanation
that follows or make changes - use the menu
Tools -> Macro -> Visual Basic Editor
and Visual Basic should start up and display the macro code in a window.
(use Close & Return to Microsoft Excel to get back to the spreadsheet)
The macro is set up in several sections, separated by comments.
At the top, it sets a couple variables (bidRange and costRange) to
regions defined in the worksheet by the names show (BidRange and
CostRange). To change the definitions of these ranges in the
worksheet, do the following steps:
[1] select the region (A4 through N25 in the example) that includes
the list of contractors, the "picked" and "cost" columns, and the
remaining columns that map the bidders to the divisions of work. The
use the menu
Insert -> Name -> Define
and enter BidRange
[2] select the region (D2 through N2 in the example) that includes the
estimated costs for the divisions). Use the menu
Insert -> Name -> Define
and enter CostRange
The helper variables that follow define some limits to the number of
bidders (1000) and divisions (100). You can increase the size of these
if necessary - just change the two assignment values and the rest of
the macro will work with the increased array sizes. [I tried to
calculate these from the size of the ranges, but VB would not let me
do that]
The Bits array is used to help generate the permutations of bidders
within each "group" (described below). Hmm. In retrospect, I suggest
changing the size of this to at least 20 - as is, this limits the
number of bidders in a group to 10. Let me know if you run into
problems with this - I an idea to mitigate this limit (by limiting the
combinations in the permutation loop). I may post a fix to this
tomorrow because that will make the macro a LOT faster when you have
lots of bidders in a group.
The variables starting with row & col refer to rows & columns within
the bidRange definition. For example,
rowBidS refers to the starting row of the bidders and rowBidE refers
to the ending row
Next, the macro clears three regions (the picked column, count row,
and a "picked" row). The picked row isn't used (I was going to put the
bidder for each division here - let me know if you need that - it
would be easy to add).
Next, the "quick" check for divisions that have a single bidder. Your
example doesn't have any but if you clear E6 or E7 in the sample file,
you can see the effect of this code in the example.
The next part of the code creates a set of "groups" and assigns
bidders and divisions to each group. You may notice that the groups
are exclusive - no bidders are in more than one group, no divisions
are in more than one group. The group works like this in the example:
- bidders in rows 5, 6, and 7 bid on divisions in columns D and E (group 1)
- bidders in rows 8, 9, and 10 bid on divisions in columns F and G (group 2)
- bidders in rows 11 through 16 bid on divisions in columns H, I, and J (group 3)
- bidders in rows 17 through 25 bid on divisions in columns K through N (group 4)
The number of groups and grouping of bidders / division is done
"automatically" with this code.
Finally, there is a loop going through the groups that
- collects the bidders / costs in the group
- collects the divisions in the group
- works through the permutations (8 for groups 1 and 2, 32 for group
3, 512 for group 4) to determine the choice that cover the division
(no repeats allowed) at the least cost
- marks the "picked" bidders for the least cost choice
That's it.
Again, if you have any problems with how the macro works or any error
messages when you process it with your "real" bidding information -
please make a clarification request. I am glad to help.
Good luck with your testing and your work.
--Maniac |
Clarification of Answer by
maniac-ga
on
10 Aug 2006 21:22 PDT
Hello Njovin,
As mentioned previously, I made a few updates to the macro (still at)
http://homepage.mac.com/mhjohnson/maniac-ga/njovin/bidSample.xls
as follows:
[1] If two bids cover the same divisions, the "higher cost" one is
marked as "Ignored" and will no longer be used in calculations. With
the sample data you provided, two bidders meet this criteria. Note
that if overlap is possible, the sample data you provided could have a
slightly lower cost (Company D is $500 less than Company B for more
work, but D won't be selected due to the exact cover requirement).
[2] There are now two algorithms used for generating the bidder
combinations to cover the divisions of work:
- the original algorithm is used in the (unlikely) case that there
are fewer bidders than divisions in a group. [not in your example data
- but is already proven code]
- when the number bidders (B) exceed the number of divisions (D) in a
group, the code walks through all possible selections of D bidders
from the list of B bidders. For the sample data, this was used to
solve all the groups and results in far fewer combinations to check.
For your sample worksheet, the code seems to run "just as fast" with
these changes as before, but with a large number of bidders and
divisions, the improvement should be quite significant. This also
removes the limitation on the number of bidders in a group (20 with
the old algorithm).
[3] Filled out the "bidder picked" row at the bottom to indicate which
bidder is covering which division.
Again - I am greatly interested in feedback on how the macro works
with your real word bid samples. If you have any problems with the
macro - please make a clarification request and I would be glad to
help you further.
Good luck with your work.
--Maniac
|
Request for Answer Clarification by
njovin-ga
on
11 Aug 2006 10:43 PDT
Maniac,
There seems to be a problem with the script. I added some more data,
updated the size of the Bits array to 20, changed the BidArea region
to include the new data, and it bugs out when running the macro.
There seems to be a problem with the way it calculates the number of
bids in any division, the number is higher than it should be (when
viewing the locals window at the time of the error).
Also, (please correct me if I'm wrong), but this is trying all
possible combinations, basically brute-forcing the answer, corrrect?
I'll know more when I test out the script with more data, but it seems
like with a full sample (several dozen divisions and several dozen
subs) it will take this a very long time to run. I'll know for sure
once you work this bug out.
I've posted your macro-ed version with my data at
http://www.soltekpacific.com/bidsample.xls
|
Clarification of Answer by
maniac-ga
on
12 Aug 2006 11:55 PDT
Hello Njovin,
OK. I have put an updated version of your worksheet at
http://homepage.mac.com/mhjohnson/maniac-ga/njovin/bidSample.xls
this version solves the new sample data in a minute or two.
If you run the macro, it has some debug code (to display the number of
combinations) and gives you the option to cancel at that point. Enter
"True" to the dialog box to proceed. The new macro also colors the
groups (before the debug code) and the resulting picks (at the end) to
illustrate the solutions it is coming up with. If you have some data
that this version works poorly with - please let me know.
I have a few more ideas to reduce the runtime more fully and wanted to
give you a brief update on the optimizations I am working on.
First, let me comment briefly about "brute force".
I assume you DO want an absolute minimum - if that is not the case,
please make a clarification request and I will look more at
statistical methods instead of trying all "reasonable" combinations.
The method implemented in the macro (then and now) works as follows:
[1] Looks for divisions w/ a single bid / and "picks" those right away
[2] Marks some (now quite many) bids to be "ignored". The new
version is more agressive at marking bids to be ignored (using your
"could cost" values) and I've thought of another method that may add
more to the "ignored" list and will add it to the next version.
[3] Forms groups of independent bids. This is key in the previous and
current macro in reducing the combinations to be tested. The bidder in
row 33 in particular was a problem with the old macro since it
prevented subgroup formation. Due to its bid price, its now ignored
but a more general solution to [4] will need to address this problem.
[4] Work through the "valid" combinations to determine the low cost
that covers the divisions in each group. The new macro reduces the
combinations greatly but I have some additional ideas to continue to
search the combinations more efficiently.
There are some other optimizations that I can apply to reduce run time
(using arrays or recoding as an application), but I think its most
important to work out the specific algorithms first and then if the
runtime is still too slow, then do the further optimizations. Making
this an application could improve the runtime by 100x or more but if
the algorithm is still 10000x too slow - I need to fix that first.
--Maniac
|
Clarification of Answer by
maniac-ga
on
14 Aug 2006 20:18 PDT
Hello Njovin,
I made another update to the worksheet at
http://homepage.mac.com/mhjohnson/maniac-ga/njovin/bidSample.xls
This solves your latest sample data in a few seconds by "ignoring"
many more bidders than the previous versions. This should scale up
relatively well if the data has "much less overlap" as you indicated
previously. The combination of ignored bids, single bidders in a
group, and grouping should reduce the complexity of the overall
solution.
Let me point out some other changes that may be helpful to your application.
[1] The current code checks to see if the "could cost" is less than
the bid. This is done near the first comment with the phrase DEBUG
(the macro runs slower if you take uncomment the next line). If you
add the rows at the bottom of the worksheet to the BidRange named
region, the code runs about 3x faster with the sample data.
[2] I changed the input boxes to message boxes - use OK to proceed or
Cancel to stop. Those also have a DEBUG comment near by if you want
search for them / comment the prompts. I am seeing performance of
about 1k combinations per second - use that to judge the runtime
before pressing OK. (the bidders & divisions are colored at that point
as an aid in debugging) If all (or most) of the divisions end up being
a single color (e.g., "Green"), that indicates there is quite a bit of
overlap in the bids.
[3] I moved the count / chosen rows to the top & used "Freeze Panes"
to keep the top few / left few rows on the screen all the time. Use
Menu -> Unfreeze Panes or Remove Split to remove it.
[4] I also turned on Data -> AutoFilter to view subsets of the bids.
If you click on the drop down next to "Picked", select 1 to show just
the picked bids. As an alternative, you can click on the drop down
next to "Ignored", select Custom Filter and select "not equal to" and
1 to show the "not ignored" bids.
Let me know how this version works with your real data. There may be
some ways to further reduce the combinations, but this sample data
doesn't show much room for improvement. The solution has 3 single
bidders and 6 bids to cover the other 8 divisions since most of the
"not ignored" bids have only one or two divisions covered and each
division is covered by at most three "not ignored" bids.
--Maniac
|
Request for Answer Clarification by
njovin-ga
on
22 Aug 2006 10:03 PDT
We've added some more sample data that is causing the program to run
VERY slowly (taking more than a minute to compute). We're going to
load in some real data (from an actual bid), I'll let you know how
that goes.
|
Clarification of Answer by
maniac-ga
on
22 Aug 2006 17:04 PDT
Hello Njovin,
I hope your testing goes well. If not, I posted another version at
http://homepage.mac.com/mhjohnson/maniac-ga/njovin/bidSample.xls
which has a slightly different algorithm for computing the
permutations (after ignoring several bids & doing the single bid
selections). The reduction in the number of permutations was
relatively minor with the sample data provided so far but it appears
to work more efficiently. [partly due to recoding to more efficient
methods - if the algorithm is correct, I can do more of that or recode
as an application to get further speed boosts]
If you can post something similar to your "real data" (I assume
sanitized), I can look at where the algorithm is getting "stuck" and
see if there is a good solution.
--Maniac
|
Request for Answer Clarification by
njovin-ga
on
06 Sep 2006 08:04 PDT
I've posted a sampling of actual bid data at www.soltekpacific.com/bidDataTest.xls.
I tried pasting this data into the provided bidSample.xls file and
updating the range, but the macro is still erroring out.
|
Clarification of Answer by
maniac-ga
on
07 Sep 2006 06:15 PDT
Hello Njovin,
Just a brief status update.
I downloaded a copy of the sample data. After updating the maximum
number of bidders, I found a couple other bugs that appear to prevent
a complete solution to this set of data. I've fixed one and the
updated code solves all but four of the divisions - somehow those
divisions were "skipped" by the code. I should have a full solution
later today or tomorrow.
--Maniac
|
Clarification of Answer by
maniac-ga
on
07 Sep 2006 18:20 PDT
Hello Njovin,
Take a look at the worksheet
http://homepage.mac.com/mhjohnson/maniac-ga/njovin/bidDataTest.xls
which has the data you provided (Sheet1), a solution generated by the
macro (Solution) copied from the first sheet, plus the version of the
macro that processed that data.
The macro takes about a minute to simplify the problem (marking
bidders to "ignore" that cannot be part of a lowest cost solution) and
then mark the divisions / matching bidders that have a single
remaining bidder.
The remainder of the bidders / divisions are divided into 9 groups.
Most are quite small, but the largest still covers 16 divisions and 19
bidders. The small ones are solved in a few seconds. The large one
takes some time to solve (about 60 million combinations - several
hours on my system).
Please confirm this works in a similar manner on your system. If not,
or if you have data that still doesn't work properly, please let me
know.
After viewing the data more thoroughly, I noticed a few things that
may greatly simplify the calculations:
- columns CY through DB are covered by only three rows (195, 196, and
204). Row 204 can't be part of the solution since it overlaps the
other two and cannot form a cover with other rows. There may be a way
detect that condition and ignore that bid. (and bids with similar
conditions)
- after that, there are several columns with only two possible bid
combinations. CY through DB and DK through DN. By selecting the bids
that cover these columns, the remainding columns DC through DJ would
result in a much simpler solution.
I will think about this some more and see if I can come up with a
method to do this reduction automatically and cut down on the
permutation to speed up the macro. It may be a couple days before I
can produce a suitable solution for that however. Please be patient.
--Maniac
|
Clarification of Answer by
maniac-ga
on
17 Sep 2006 10:15 PDT
Hello Njovin,
I have updated
http://homepage.mac.com/mhjohnson/maniac-ga/njovin/bidDataTest.xls
with an updated solution (w/ two slightly different versions).
The worksheet "Solution" has the solution generated by the last
version (bidSample).
The worksheet "aBidSoln" has the solution generated by the macro
aBidSample. In my testing, this takes about two minutes total to
produce a solution. The top half is the same as bidSample (to ignore
higher cost bidders, select single bidders). The bottom half is a new
algorithm that starts at the first division and moves across,
selecting bidders to fill in the zeros / ignoring bidders that
overlap. When the complete covers are generated, the lowest cost one
is selected.
The worksheet "bBidSoln" has the solution generated by the macro
bBidSample. In my testing, this runs slightly faster (about 1 - 1/2
minutes) total to produce a solution. I noticed the bottom half runs
quite quickly now, so the top half was simplified to take less time by
being less thorough in removing higher cost bidders. The trade off
appears work in the sample data you provided (saving 35 seconds in the
top half at a cost of 2 seconds added to the bottom half).
Let me know if you have any further problems with this solution.
--Maniac
|
