Be aware might it would take a moment to digist the information. Instead, allow me to recap the problem/solution and then explain what might require some tweaking:

o The program solves the "knapsack" (spatial optimization) problem.
o The code executes fine. Right now, it contains five (5) data sets. The first (original) data set provides a solution that fully meets the requirements.
o That is, the "Greedy Algorithm" first determines the total value ... being outputted to the console in "Step 3".
o Depending on the data set, the "Greedy" algorithm may not necessarily provide the most optimal ouput. This is where the "Local Search" algorithm comes in.
o Essentially, it "looks" at items that were not picked in the Greedy and compares them with items in the knapsack.
o As part of the optimization process, it checks if removing a selected item (thereby freeing up volume/weight capacity) would allow an non-selected, higher value-item to be placed into the knapsack.
o Again, per the original data set, the "Local Search" actually improved the total value by 175 total value units (see step 5 of the code... or better see JPG "OriginalDataSet.jpg").

Now, here's what I need some help with:
o Apparently, the Local Search algorithm does >> NOT << always find an improved/equal solution (when compared to the Greedy).
o As a matter of fact, out of the four new data sets, three (3) produce a worse solution.
o That is, data set [1, 2, 4] result in solution that provides a smaller total value.

My question:

How should the Local Search function be modified in order to ensure either the same (or hopefully) better output in step #5?

Thanks,
EEH

P.S. The 2nd JPG (Data Set 1) shows a "weird" value in the last line of the console output. That's because the total value in the Greedy is larger than the total value in the Local Search. I've actually modified the code by simple adding an IF-ELSE statement in the Step 5 console output. Unfortunately, I don't have access to the modified code. Simply put, if the total value oof LocalSearch is greater then I print: LocalSearchTotal - GreedyTotal... else, I print GreedyTotal - LocalSearchTotal. [Pseudocode]

// Required C++ libraries and header files#include <iostream>#include <iomanip>#include <fstream>#include <cstdlib>#include <deque>#include <math.h>#include <limits.h>using namespace std;// Declaration of variables// ****** Begin of ORIGINAL DATA ******#define MAXWEIGHT 1400 // Testing Data (for Local Search)int knapSack_Max_Weight = 1400; // Testing Data (for Local Search)#define MAXVOLUME 1100 // Testing Data (for Local Search)int knapSack_Max_Volume = 1100; // Testing Data (for Local Search)int linecount = 13; // Testing Data (for Local Search)int itemValue[13] = {150, 580, 200, 350, 360, 400, 75, 200, 535, 250, 450, 150, 50}; // Testing Data (for Local Search)int itemWeight[13] = {100, 200, 55, 100, 100, 100, 25, 300, 200, 200, 200, 200, 200}; // Testing Data (for Local Search)int itemVolume[13] = {100, 150, 150, 300, 400, 400, 50, 175, 500, 200, 200, 200, 200}; // Testing Data (for Local Search)// ****** End of ORIGINAL DATA ******// ****** Begin of 1st Data Set (10 items) ******//#define MAXWEIGHT 1200 // Knapsack's maximum weight (constant)//int knapSack_Max_Weight = 1200; // Knapsack's maximum weight ////#define MAXVOLUME 1000 // Knapsack's maximum volume (constant) //int knapSack_Max_Volume = 1000; // Knapsack's maximum volume // //int linecount = 10; // The number of items available for selection//int itemValue[10] = {150, 250, 450, 150, 50, 350, 175, 275, 275, 575}; // Knapsack items' array specifing their value//int itemWeight[10] = {100, 200, 450, 200, 65, 200, 200, 350, 300, 478}; // Knapsack items' array specifing their weight//int itemVolume[10] = {120, 200, 200, 130, 175, 200, 200, 285, 400, 422}; // Knapsack items' array specifing their volume// ****** End of of 1st Data Set (10 items) ******// ****** Begin of 2nd Data Set (12 items) ******/*#define MAXWEIGHT 1350 int knapSack_Max_Weight = 1350; #define MAXVOLUME 1150 int knapSack_Max_Volume = 1150; int linecount = 12; int itemValue[12] = {35, 200, 400, 300, 555, 250, 75, 122, 680, 500, 125, 275};int itemWeight[12] = {75, 215, 333, 350, 375, 100, 75, 80, 410, 175, 100, 175}; int itemVolume[12] = {90, 222, 240, 300, 400, 177, 75, 110, 150, 350, 74, 100}; */ // ****** End of of 2nd Data Set (12 items) ******// ****** Begin of 3rd Data Set (15 items) ******/*#define MAXWEIGHT 1850 int knapSack_Max_Weight = 1850;#define MAXVOLUME 2100 int knapSack_Max_Volume = 2100; int linecount = 15; int itemValue[15] = {200, 180, 200, 200, 200, 300, 333, 300, 515, 300, 500, 600, 900, 700, 600};int itemWeight[15] = {150, 121, 155, 350, 50, 100, 177, 250, 420, 175, 175, 175, 575, 565, 600};int itemVolume[15] = {120, 170, 130, 228, 55, 130, 250, 150, 288, 100, 100, 100, 700, 725, 440};*/ // ****** End of of 3rd Data Set (15 items) ******// ****** Begin of 4th Data Set (20 items) ******/*#define MAXWEIGHT 3000 int knapSack_Max_Weight = 3000;#define MAXVOLUME 2875 int knapSack_Max_Volume = 2875; int linecount = 20; int itemValue[20] = {200, 200, 200, 200, 200, 300, 300, 300, 300, 300, 500, 600, 900, 700, 600, 250, 500, 430, 95, 250}; int itemWeight[20] = {100, 200, 150, 350, 50, 100, 200, 250, 50, 175, 175, 175, 575, 565, 600, 175, 250, 220, 25, 120}; int itemVolume[20] = {120, 200, 130, 300, 50, 120, 250, 150, 150, 100, 100, 100, 700, 725, 440, 175, 350, 320, 35, 140}; */ // ****** End of of 4th Data Set (20 items) ******// Declaration of slack variables for volume and weightint volumeLeft = MAXVOLUME;int weightLeft = MAXWEIGHT;// Structure used in the knapsack problem (for Greedy Algorithm)typedef struct PossibleMatch { int nItem; int nValue; int nVolume; int nWeight;} ;// Structure used in the knapsack problem (for Local Search Algorithm)struct knapsack_Item{ unsigned int Index; unsigned int Value; unsigned int Volume; unsigned int Weight;};// Declarations of "double-ended queues" (sequence containers)deque<knapsack_Item> SortedItems;deque<knapsack_Item> Left_Behind;// Declarations of independent functionsvoid knapsack_Greedy_Algorithm();void knapsack_LocalSearch_Algorithm(int *SortedRatios, float *Ratios, float tmp1, int totalValue, int volumeLeft, int weightLeft);unsigned int GetNewTotalValue_LocalSearch();// 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 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) << "Weight: " << setw (3) << itemWeight[SortedRatios[i]] << setw (11) << "Volume: " << setw (3) << itemVolume[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 (Greedy Algorithm):" << std::endl; std::cout << "======================================================================" << std::endl << endl; i = 0; knapsack_Item kI; while ((weightLeft > 0) && (volumeLeft > 0) && (i < linecount)) { // This If-statement ensures that the next item combination (volume & weight) will NOT violate either constraint. if ((volumeLeft - itemVolume[SortedRatios[i]] >= 0) && (weightLeft - itemWeight[SortedRatios[i]] >= 0)) { kI.Volume = itemVolume[SortedRatios[i]]; kI.Value = itemValue[SortedRatios[i]]; kI.Index = SortedRatios[i] + 1; kI.Weight = itemWeight[SortedRatios[i]]; SortedItems.push_back(kI); // Having "passed" the If-statement ensures that capacity (for both volume & weight) is left in the knapsack. Therefore, an item is added to the knapsack. volumeLeft -= itemVolume[SortedRatios[i]]; weightLeft -= itemWeight[SortedRatios[i]]; std::cout << "Item# " << setw (2) << SortedRatios[i] + 1 << " -- Value: " << setw (3) << itemValue[SortedRatios[i]] << " Weight: " << setw (3) << itemWeight[SortedRatios[i]] << " Volume: " << setw (3) << itemVolume[SortedRatios[i]] << std::endl; totalValue += itemValue[ SortedRatios[i]]; } else{ kI.Volume = itemVolume[SortedRatios[i]]; kI.Value = itemValue[SortedRatios[i]]; kI.Index = SortedRatios[i] + 1; kI.Weight = itemWeight[SortedRatios[i]]; Left_Behind.push_back(kI); } 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' (Greedy Algorithm):" << std::endl; std::cout << "================================================" << std::endl << endl; std::cout << "Total Knapsack Value: " << setw (3) << totalValue << 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; 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 << endl << endl; // Call the LocalSearch function knapsack_LocalSearch_Algorithm(SortedRatios, Ratios, tmp1, totalValue, volumeLeft, weightLeft);}void knapsack_LocalSearch_Algorithm(int *SortedRatios, float *Ratios, float tmp1, int totalValue, int volumeLeft, int weightLeft) { // ********************** General Summary of the implemented Local Search Algorithm ********************* // This function will add items into a knapsack using a "local search" algorithm. // This algorithm determines what items are "left behind". // Based on the calculated "slack" (both for volume and weight), the algorithm determines if swapping items will have a // beneficial impact on the knapsack's total value. // In other words, by removing an initially selected item and removing it, additional space (both volume and weight) // is freed up. Now, potentially, another larger item with (potentially) a greter total value can fit in the knapsack. // In the end, this swapping of item may yield an additional net gain for the total value. // This local search algorithm has been tested on the 2nd data set and did provide a net gain of 175 total value units. // This gain of 175 value points matches MS-Solver's solution; therefore, providing the optimal value to the user. // However, depending on the data set, it is not guaranteed that this algorithm will always find the optimal solution. // ************************************************************************************************ std::cout << endl; std::cout << "Step 4: The selected knapsack items are as follows (Local Search Algorithm):" << std::endl; std::cout << "============================================================================" << std::endl << endl; deque<knapsack_Item>::iterator it = SortedItems.begin(); while(it != SortedItems.end()){ // cout << "Item: " << (*it).Index << endl; // Output testing (console output is done via the ForLoop below) // cout << "Value: " << (*it).Value << endl; // Output testing (console output is done via the ForLoop below) // cout << "Volume: " << (*it).Volume << endl; // Output testing (console output is done via the ForLoop below) // cout << "Weight: " << (*it).Weight << endl; // Output testing (console output is done via the ForLoop below) // cout << endl << endl; it++; } it = Left_Behind.begin(); while(it != Left_Behind.end()){ // cout << "Item: " << (*it).Index << endl; // Output testing (console output is done via the ForLoop below) // cout << "Value: " << (*it).Value << endl; // Output testing (console output is done via the ForLoop below) // cout << "Volume: " << (*it).Volume << endl; // Output testing (console output is done via the ForLoop below) // cout << "Weight: " << (*it).Weight << endl; // Output testing (console output is done via the ForLoop below) // cout << endl << endl; it++; } // Declaration of the unused (slack) for volume unsigned int UsedVolume = knapSack_Max_Volume - volumeLeft; unsigned int NewVolume = 0x0; // Declaration of the unused (slack) for weight unsigned int UsedWeight = knapSack_Max_Weight - weightLeft; unsigned int NewWeight = 0x0; // Determines if swapping of items will provide a net gain for the knapsack's total value for(int i = 0; i < SortedItems.size();i++){ for(int c = 0; c<Left_Behind.size();c++){ NewVolume = UsedVolume - SortedItems[i].Volume + Left_Behind[c].Volume; if((UsedVolume < NewVolume) && (NewVolume <= knapSack_Max_Volume)){ NewWeight = UsedWeight - SortedItems[i].Weight + Left_Behind[c].Weight; if(NewWeight > knapSack_Max_Weight) break; UsedWeight = NewWeight; Left_Behind.push_back(SortedItems[i]); SortedItems.erase(SortedItems.begin()+i); SortedItems.push_back(Left_Behind[c]); Left_Behind.erase(Left_Behind.begin()+c); UsedVolume = NewVolume; if(NewVolume == knapSack_Max_Volume) goto LOOPEND; else break; } } } LOOPEND: // Sort the knapsack items it = SortedItems.begin(); while(it != SortedItems.end()){ std::cout << "Item# " << setw (2) << (*it).Index << " -- Value: " << setw (3) << (*it).Value << " Weight: " << setw (3) << (*it).Weight << " Volume: " << setw (3) << (*it).Volume << std::endl; it++; } // Console output providing the new knapsack's inventory (including "Total Value" of the items; total volume/weight of the items). std::cout << endl << endl << endl; std::cout << "Step 5: Knapsack 'Inventory' (Local Search Algorithm):" << std::endl; std::cout << "======================================================" << std::endl << endl; std::cout << "Total Knapsack Value: " << setw (3) << GetNewTotalValue_LocalSearch() << std::endl; std::cout << endl; std::cout << "Total Weight (available): " << setw (4) << knapSack_Max_Weight << std::endl; std::cout << "Total Weight (used): " << setw (4) << UsedWeight << std::endl; std::cout << "Weight Capacity (left): " << setw (4) << knapSack_Max_Weight - UsedWeight << std::endl; std::cout << endl; std::cout << "Total Volume (available): " << setw (4) << knapSack_Max_Volume << std::endl; std::cout << "Total Volume (used): " << setw (4) << UsedVolume << std::endl; std::cout << "Volume Capacity (left): " << setw (4) << knapSack_Max_Volume - UsedVolume << std::endl; std::cout << endl << endl; std::cout << "Implementing the Local Search algorithm improved the optimal solution by:" << std::endl; std::cout << GetNewTotalValue_LocalSearch() - totalValue << " total value units!" << std::endl; std::cout << endl << endl;}unsigned int GetNewTotalValue_LocalSearch(){ // ********************** General Summary of the Get Total Value function ********************* // Given the implementation of the "local search" algorithm, this function was created to keep // track of the total new value that is created based on swapping items in/out the knapsack. // ******************************************************************************************** unsigned int ret = 0; // Determine the new total value based on the Local Search algorithm deque<knapsack_Item>::iterator it = SortedItems.begin(); while (it != SortedItems.end()){ ret += (*it).Value; it++; } return ret;}

From a brief look this loop in the local search algorithm:

for(int i = 0; i < SortedItems.size();i++){
for(int c = 0; c<Left_Behind.size();c++){
...
if(NewWeight > knapSack_Max_Weight)
break;
UsedWeight = NewWeight;
...
}

is the heart of it. I note that when considering swaps the only criteria for succes appears to be these lines:

if(NewWeight > knapSack_Max_Weight)
break;

That is, if the new weight exceeds the knapsack max, then the swap is discarded; otherwise it is made.

Therefore, since the only criteria is that the swap use more of the knapsacks "weight" capacity, this loop is optomizing for weight usage; it is ignoring value. If you want to guarantee that the value does not decrease you will need to specify something about value in the criteria. The simple spec would be to ensure that value of the item being swapped in is not less than the value of the item being replaced.

0

ExpExchHelpAuthor Commented:

imladris:

Thanks for chiming in... do you have a recommendation for tackling this change?

Well, I imagine you would add something about value in those lines.

This additional line about NewValue calculates the new value based on the swap, and nixes it if the total value decreases. You would have to prepare the TotalValue variable (probably in the same loop where UsedWeight etc. are calculated) and maintain it as swaps are done. And an additional condition is added to the break line, that breaks if the value decreases.

Hi,
A couple of points;
Firstly crank up your warnings on the compiler and sort out your signed/unsigned issues. for simplicity set everything to signed; that will sort out your numeric overflow which is why you are getting a "wierd" value.
Secondly change your swaps to std::swap() which will allow you to completely eliminate the tmp1 variable that is used for both floats and int.
Compiler warnings are for a reason!
You might also consider removing a selection of large items and replacing with a selection of small items. i.e. where one(or more) large item blocks the filling with multiple small items.

0

ExpExchHelpAuthor Commented:

jefftope:

Thanks... I'll look into it... but that won't fix the "NewValue" declaration problem, right?

EEH

0

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

The subnet calculator helps you design networks by taking an IP address and network mask and returning information such as network, broadcast address, and host range.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

for(int i = 0; i < SortedItems.size();i++){

for(int c = 0; c<Left_Behind.size();c++){

...

if(NewWeight > knapSack_Max_Weight)

break;

UsedWeight = NewWeight;

...

}

is the heart of it. I note that when considering swaps the only criteria for succes appears to be these lines:

if(NewWeight > knapSack_Max_Weight)

break;

That is, if the new weight exceeds the knapsack max, then the swap is discarded; otherwise it is made.

Therefore, since the only criteria is that the swap use more of the knapsacks "weight" capacity, this loop is optomizing for weight usage; it is ignoring value. If you want to guarantee that the value does not decrease you will need to specify something about value in the criteria. The simple spec would be to ensure that value of the item being swapped in is not less than the value of the item being replaced.