View Question
 Question
 Subject: Algorithm for lowest bid path Category: Computers > Algorithms Asked by: njovin-ga List Price: \$200.00 Posted: 04 Aug 2006 15:38 PDT Expires: 03 Sep 2006 15:38 PDT Question ID: 752652
 ```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.```
 Subject: Re: Algorithm for lowest bid path Answered By: maniac-ga on 08 Aug 2006 22:07 PDT
 ```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```
 ```here i give simple suggestion that will really help you one .... use the following function as per your requirement 1. IF condition. 2. SUMIF condition. 3. count 4. finding max and min number using MAX & MIN function.. these is enough for u... Regards, Pugalzhenthi .V```
 ```This type of problem is called Exact Cover. See: http://en.wikipedia.org/wiki/Exact_cover Generate all exact covers and find that with the lowest cost. Note that determining if there is an exact cover is NP-complete, meaning that it cannot be solved efficiently (in polynomial time), provided the famous \$1,000,000 conjecture P not equal NP is true.```
 `You sure this was not a homework assignement for a logic class?`