I've implemented an algorithm -- in C++ -- with the help of a few EE gurus. The code for this "0-1 knapsack" problem is posted below.

Now, the current program/solution follows the "Greedy" method (comments inside the code provide more details). In this program, the method simply looks at the largest "ratio" (computed via "Value / (Volume + Weight)" and adds items into the "knapsack" until it reaches either one of the two constraints ("maximum volume" or "maximum weight" of the knapsack).

Now, I'm using two different data sets (both of them are included in the declaration section). Using the first data set, it just mere coincidence that the greedy method results in an optimal solution with no slack (unused volume/weight capacity). Therefore, I'm indeed outputting the optimal solution -- a value that I verified using MS-Excel's "Solver".

However, the second data set leaves unused capacity. In contrast to MS-Excel's solver, my current C++ program does NOT attempt to optimize the solution by "swapping" (potentially items).

Well, as you know, a "picture is worth a thousand words", so I decided to provide more details in the attached spreadsheet. The XLS contains four (4) worksheets:
1. "Excel Solver -- Data Set 1"
2. "Excel Solver -- Data Set 2"
3. "C++ Snapshots of 2 Data Sets"
4. "C++ Logic"

The first three worksheets could be considered more or less FYI. Nevertheless, they set the stage and provide a quick contrast between the two data sets as well as the C++ output (snapshots).

The fourth worksheet, however, provides IMHO the meat of what I'm trying to accomplish.

Essentially, I need to come up with a "Local Search" algorithm that will accept a worse solution/option in order to get out of a "local optimum" in order to reach a "global optimum". There's plenty of detail on the web... search keywords such as "local search algorithm" return valuable info, incl. a 2010 reference document such as shown at: http://www.cs.umd.edu/~nau/cmsc421/chapter04b.pdf

Based on the URL, slide #7 ("Hill climbing" ) outlines -- in much better words/pictures -- what I described in the previous paragraph.

So, what do I need some help with? In addition to my greedy algorithm (see the C++ code), I'd like to implement the "Local Search" algorithm which would allow the swapping of, e.g., item #7 with item #10. [What?!?! ... where's this coming from... well, please read the info in the yellow call-out box on worksheet "C++ Logic" of the attached XLS].

Again, any help is appreciated for achieving this goal. Thousand thanks in advance!!!

EEH

// Required C++ libraries and header files#include <iostream>#include <iomanip>#include <fstream>#include <cstdlib>#include <math.h> #include <limits.h>using namespace std;// Declaration of variables#define MAXVOLUME 800 // Knapsack's maximum volume (constant) int knapSack_Max_Volume = 800; // Knapsack's maximum volume #define MAXWEIGHT 900 // Knapsack's maximum weight (constant)int knapSack_Max_Weight = 900; // Knapsack's maximum weight int linecount = 10; // The number of items available for selectionint itemValue[10] = {150, 250, 450, 150, 50, 350, 175, 275, 275, 575}; // Knapsack items' array specifing their valueint itemVolume[10] = {100, 200, 200, 200, 200, 200, 200, 200, 300, 300}; // Knapsack items' array specifing their volumeint itemWeight[10] = {100, 200, 200, 200, 200, 200, 200, 200, 400, 400}; // Knapsack items' array specifing their weight// ****** Begin of TESTING DATA (other than the data provided) ******/*#define MAXVOLUME 1100int knapSack_Max_Volume = 1100;#define MAXWEIGHT 1400int knapSack_Max_Weight = 1400; int linecount = 13; int itemValue[13] = {150, 580, 200, 350, 360, 400, 75, 200, 535, 250, 450, 150, 50}; int itemVolume[13] = {100, 150, 150, 300, 400, 400, 50, 175, 500, 200, 200, 200, 200}; int itemWeight[13] = {100, 200, 55, 100, 100, 100, 25, 300, 200, 200, 200, 200, 200}; */ // ****** End of TESTING DATA (other than the data provided) ******// Declarations of independent functionsvoid knapsack_Greedy_Algorithm();// Structure used in the knapsack problemtypedef struct PossibleMatch { int nItem; int nValue; int nVolume; int nWeight;} ;// Main() is the programs' "entry point"int main(){ // Function call to execute the "greedy" algorithm for the "0-1 Knapsack Problem: // More information can be obtained via: // 1. http://en.wikipedia.org/wiki/Greedy_algorithm // 2. http://en.wikipedia.org/wiki/Knapsack_problem knapsack_Greedy_Algorithm(); // Pause the window console screen system("PAUSE"); return 0;}void knapsack_Greedy_Algorithm() { // ********************** General Summary of the implemented Greedy Algorithm ********************* // This function will add items into a knapsack using a "greedy" algorithm. // This algorithm first computes/fills a table/array holding ratios of "Value / (Volume + Weight)". // Then, the ratio is sorted in descending order (holding the largest ratios first). // Once the ratio table has been computed, the algorithm loops through the table/arry // and adds items until there reaching the constraints (volume and weight constraints). // In other words, it adds items until there is no more space for the next item. // Depending on the data sets, there is a probability that the knapsack is left with // additional available space (both volume or weight). // Therefore, this method is NOT optimal and could benefit from the "Local Search" function. // ************************************************************************************************ // This algorithm computes very fast, so it can be used with a significant large number of items int *SortedRatios; // Index of ratios float *Ratios; // Ratios themselves float tmp1; int weightLeft = MAXWEIGHT; int volumeLeft = MAXVOLUME; int totalValue = 0; int i, j; SortedRatios = new int[linecount]; Ratios = new float[linecount]; // Calculate the ratios for each items for (i=0; i < linecount; i++) { Ratios[i] = (float)itemValue[i] / (itemVolume[i] + itemWeight[i]); SortedRatios[i] = i; } // Sort the ratios using a "Bubble Sort" for (i=0; i < linecount; i++) for (j=i; j < linecount; j++) { if (Ratios[i] < Ratios[j]) { // Swap ratios tmp1 = Ratios[i]; Ratios[i] = Ratios[j]; Ratios[j] = tmp1; tmp1 = SortedRatios[i]; SortedRatios[i] = SortedRatios[j]; SortedRatios[j] = tmp1; } } // Console output of the Bubble Sort result in order to see if it is properly sorted (by ratio) std::cout << endl; std::cout << "Step 1: Ratio Computation:" << std::endl; std::cout << "==========================" << std::endl << endl; for (i=0; i<linecount; i++) { std::cout << "Ratio: " << setw (2) << fixed << setprecision(2) << Ratios[i] << setw (10) << "Index: " << setw (2) << SortedRatios[i] << setw (10) << "Value: " << setw (3) << itemValue[SortedRatios[i]] << setw (11) << "Volume: " << setw (3) << itemVolume[SortedRatios[i]] << setw (11) << "Weight: " << setw (3) << itemWeight[SortedRatios[i]] << std::endl; } std::cout << endl << endl; // Items are added to the knapsack until the volume/weight constraints are met. Items are added in DESC order of the computed ratio. std::cout << endl; std::cout << "Step 2: The selected knapsack items are as follows:" << std::endl; std::cout << "===================================================" << std::endl << endl; i = 0; while ((weightLeft > 0) && (volumeLeft > 0) && (i < linecount)) { // This If-statement ensures that the next item combination (volume & weight) will NOT violate either constraint. if ((weightLeft - itemWeight[SortedRatios[i]] >= 0) && (volumeLeft - itemVolume[SortedRatios[i]] >= 0)) { // Passing the If-statement ensure that space is left in the knapsack. Therefore, the item is added to the knapsack. weightLeft -= itemWeight[SortedRatios[i]]; volumeLeft -= itemVolume[SortedRatios[i]]; std::cout << "Item# " << setw (2) << SortedRatios[i] + 1 << " -- Value: " << setw (3) << itemValue[SortedRatios[i]] << " Volume: " << setw (3) << itemVolume[SortedRatios[i]] << " Weight: " << setw (3) << itemWeight[SortedRatios[i]] << std::endl; totalValue += itemValue[ SortedRatios[i]]; } i++; } // Console output providing the knapsack's inventory (including "Total Value" of the items; total volume/weight of the items). std::cout << endl << endl << endl; std::cout << "Step 3: Knapsack 'Inventory':" << std::endl; std::cout << "=============================" << std::endl << endl; std::cout << "Total Knapsack Value: " << setw (3) << totalValue << std::endl; std::cout << endl; std::cout << "Total Volume (available): " << setw (4) << knapSack_Max_Volume << std::endl; std::cout << "Total Volume (used): " << setw (4) << knapSack_Max_Volume - volumeLeft << std::endl; std::cout << "Volume Capacity (left): " << setw (4) << volumeLeft << std::endl; std::cout << endl; std::cout << "Total Weight (available): " << setw (4) << knapSack_Max_Weight << std::endl; std::cout << "Total Weight (used): " << setw (4) << knapSack_Max_Weight - weightLeft << std::endl; std::cout << "Weight Capacity (left): " << setw (4) << weightLeft << std::endl; std::cout << endl << endl << endl;}

is the 'Local Search' algorithm you described your own idea or is it a well-known algorithm?

the problem is see is that it wouldn't exchange pairs with singles nor any multiples with other multiples. so in the best it only adds a little improvement on the greedy.

Thanks for chiming in... I already feel I'm in goods hands. 8)

>>Is the 'Local Search' algorithm you described your own idea or is it a well-known algorithm?<<
No, the "Local Search" algorithm is NOT my own idea. There lots of research covering this topic. I believe that Excel's Solver actually has this concept built-in. That how it "knew" that swapping those two items (replace #7 with #10) would provide a greater optimal total value.

>> So in the best it only adds a little improvement on the greedy. <<
You're are absolutely correct. Allow me to elaborate though.

By using MS-Excel, I'm somewhat "cheating". Meaning, I know what the optimal value should be. Depending on the situation, a process owner may not know what the optimal value is. In such case, incremental improvements (no matter how small) should be considered success.

Now again, having used Excel up-front, I know what the best "item swapping" scenario is: "Replace 7 with 10". Given the existing data set (13 records), I'm not sure if there's even another possible option (w/o decreasing the total value AND not violating the volume/weight constraints).

However, another data set (having hundreds of records) and smaller values for volume/weight might provide several swapping scenarios. That is dealing w/ the unknown though.

Going back to the example that I found online (http://www.cs.umd.edu/~nau/cmsc421/chapter04b.pdf), I've included an algorithm that may perform the swapping. See attacched image. (Source slide #6).

Does that make sense? Please let me know if the information provided is confusing.

Your code says it is "very fast" and then proceeds to use Bubble Sort which is O(n^2). Why on earth would you use Bubble Sort with something that is supposed to be "very fast"? The Greedy algorithm you have is O(n) and the Hill-Climbing is also O(n). So the slowest thing in your code will be the Bubble Sort.

That said, I believe the Hill Climbing is a rather poor solution. It works only when there are obvious "neighbors", and does get stuck on local maxima. The Hill Climbing is hardly better than the Greedy method.

Your problem is the traditional Knapsack problem, but in two dimensions. A modified Branch and Bound would be much better.

Suppose you have gotten to where you are nearly full on volume, but have lots of weight left. You'd want to pick the item with the highest value to volume ratio, almost without regard for weight.

0

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Thanks for the feedback. I appreciate it. Given the amount of items (maybe up to 30 or 40), the existing code will absolutely suffice. I'm not interested in saving milliseconds.

So, for right now, I'd like to stay focused on the Local Search algorithm (vs. modifying/improving the Greedy algorithm). Fair enough?

As far as your recommendation on the "Hill Climbing" is concerned, I'm open for recommendations. That provided reference was simply one that came up when searching for "local search algorithm" on the web.

For the local search, I'm simply trying to "check out" other options. So, here's what I'm trying to achieve:
1. Take an item out and replace it with another one. The selection of the replacement item could be some random occurrence.
2. Check out if that item change improved the total value. If it did, keep it. Otherwise, return the previous item.
3. Continue with steps 1 and 2.

How would I go about implementing such code in the existing program?

As part of the research task, I will need to stick with "Local Search". I know it may not make sense why I wouldn't choose the best method, but there's an underlying reason (not important to go into the details right now).

At this time, I'm simply trying to prove that Local Search can/will improve the solution... even if it's only by a few "total value units".

I'd note that the concept of "local maximum" is *not* defined given the problem domain. Hill climbing is done in a space where all you do is look for the maiximum value based on N-dimensions. You are doing a "two-dimenstional Knapsack packing problem". Local maximum simply has NO sensible definition in this case since you are not looking for a point in a N-dimensional space -- you are looking to combine a number of points into an optimum set.

So what you need is an algorithm that does more than just "switch" items. For example, it may be best to throw out a high-volume high-value item to allow two lesser value, lesser volume items which happen to sum to a greater value and a lesser or equal volume and no more than the same weight.

A better approach might be to select items at random and use the greedy method (but don't stop when an item doesn't fit, as a later item might fit). Do that a lot :-).

sdeller:
>> For example, it may be best to throw out a high-volume high-value item to allow two lesser value, lesser volume items which happen to sum to a greater value and a lesser or equal volume and no more than the same weight.<<

Exactly! Essentially, I provided that concept in the XLS (worksheet "C++ Logic; yellow callout). It says:
>> The remaining question which must be asked is the following: Having swapped 7 with 10, did the "total value" increase or even decrease. #7's value = 75 value units. #10's value = 250. That means a net gain of 175 value units gain be gained via this swapping!!! The swapping is done based on the increase. (If it had been actually a decrease, the swapping would have been undone)."

So, you and I are in synch as to what needs to be done (conceptually). As I consider myself somewhat of a novice in C++ programming, I welcome any pointers/recommendations (incl. hints for coding).

Pls see previous reply first. I noticed there was another comment that I didn't address.
>>A better approach might be to select items at random and use the greedy method (but don't stop when an item doesn't fit, as a later item might fit). Do that a lot :-). <<

As far as I'm concerned, that's how the Greedy currently works. Once an item doesn't fit, it does not stop there... instead, it keeps going until another items fits (given there's no violation for either volume and weight constraint).

eeh, i thank you for the points and i am sorry i couldn't help you with your idea with the local search. but local search is suitable for NP complete problems where an optimum can't be found. i agree that when using both volume and weight as a criteria the 0-1-knapsack cannot be solved completely as easily as when only the weight (in integer) is given. but the uncertainity of the target function whether volume or weight is now the more crucial point is bad for local search as well.

Sara

0

Featured Post

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++.
The reason I built this class is to ease the pain of using XML files with C++, since there isâ€¦

IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger. It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article locâ€¦

The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.

The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.