[SOLVED] CS B tree algorithm Subject TP IOC, algorithms for solving the backpack problem, C ++ implementation

Subject TP IOC, algorithms for solving the backpack problem, C ++ implementation
Paris-Saclay University, L3 INFO academic
year 2020-2021
General instructions (to be read carefully)
This practical work is to be delivered individually or in pairs, and will be part of the continuous control note (CCTP). Several tutorials / practical work during the course are devoted to this project, a part of independent work is expected .
This lab implements and illustrates the Backpack Problem Solving course. You can proceed at your own pace, and watch the videos of these courses only when it becomes necessary for the advancement of the lab, this will be mentioned in the topic. The idea of this operation is to be able to allow yourself to organize yourself to move forward at your own pace and to make the question sessions as profitable as possible. I also advise you to take advantage of the practical sessions for questions on the most critical points that can block you, including implementation.
The project topic is written so that you are autonomous enough to move forward, with several parts independent enough so that you can move forward on several fronts / issues if you get stuck on one point. Questions / answers are done on the eCampus forums. No individual question by email, questions / answers are beneficial to all. You can ask questions regularly, I will specify the time slots where we are connected to answer live. With this operation, it is up to you to organize your time and your work so that these question and answer points are profitable.
The rendering of this TP project will be done in two phases. The first phase includes questions from 1 to 14 to code the various approaches presented in class, and to check that the results are consistent. For this part, the rendering is expected by eCampus for February 15, in a single fi le plnePart1-NOM1 (NOM2) .pdf, where the completed code is inserted in the answers to the questions. . At the end of this phase, the solution code will be provided on February 16. It will allow you to perform the requested numerical analyzes and answer the questions in part 2, even if your code was not functional on February 15. This second part is also to be returned by eCampus, in a single pdf plnePart2-NOM1 (-NOM2) .pdf.
The coding of the required functions should allow you to better understand the PLNE course by applying it, which will be a good basis for the exam. For the end of the project, you are expected to analyze and take a step back from the various algorithms and results observed experimentally. The experimental questions lead you to compare / analyze algorithms and to be able to explain the practical behavior of algorithms and better understand them.
The implementation part of the Branch & Bound algorithm will probably take the most time, and is most important for the IOC course. The previous parts allow us to increase in power, in particular in C ++ on simpler algorithms. C ++ reminder videos are also provided, to remind you of some refexes necessary for coding this lab (and the following lab which will also be in C ++)
Code and data sets provided
The code is provided separately on eCampus. The architecture of the code, the data sets provided and the compilation options, are in the course boards and presented in video, in the course videos, or in the videos archiCodeBB.ogv and codeArchiMake fi le.ogv specifications.
Note, you can reorganize the code however you want, whether this is reorganizing the code and rewriting a corresponding make fi le, or writing your own functions without using functions already coded. The architecture provided has been designed to be the easiest to understand pedagogically for the greatest number of people.
Data sets of different sizes are provided as text fi les in the instance folder, the format of these data is explained in the course video part1 algoGlouton.mkv. The import of such data in a KpSolver instance is already provided, with the method:
void KpSolver :: importInstance (const string & fileName)
To be able to generate data of fi xed size, (depending on the characteristics of your machine), the following function in the KpSolver class extracts the sub-instance from the instance in memory by taking the objects of clues between idMin and idMax, keeping the initial ratio of the total mass of the objects in the bag divided by the capacity of the backpack: void extractSubInstance (int idMin, int idMax)
The code can be compiled directly into the src directory, with a g ++ * .cpp. The main is in the KnapsackSolvers.cpp fi le. If you want to have several entry point fi les to run various calculations without changing KnapsackSolvers.cpp, you can for example create a test subfolder with all possible entry points including KnapsackSolvers.cpp , and compile with commands of type g ++ * .cpp test / KnapsackSolvers.cpp. Such a compilation leaving a hand in the root of the src folder would be wrong, with two hands found of course. If such a mode reassures you for the first part of the lab, you can do it, the make-up should make your life easier.
To compile the code, an architecture with a simple make fi le is provided, and explained in the codeArchiMake fi le.ogv video. The use of make fi le is particularly interesting in the second part of the lab to be able to generate several types of executables, for different types of experiments, without having to change to each time the KnapsackSolvers.cpp fi le where the main is located. For example, it is useful to generate the automatically requested result tables by writing the results to a .csv fi le, by various main functions in various entry points. It is possible to code using all the same classes de fi ning the backpack resolution.
The make-up has been designed not to scratch the less accustomed, and to be easily modi fi able by reproducing identically. The most used ones can rewrite / regenerate the make fi le according to their habits.
1 Implementation part, for February 15
Question 1 Mention the specifications of your hardware and software con fi guration, for example: Intel (R) Core (TM) i5-3320M CPU, 2.60GHz, 8Gb RAM, Linux Ubuntu operating system
20.04 and g ++ version 7.5.0. In case of working in pairs or on several machines, mention the various characteristics (eg Machine A: , Machine B: ). In this case, we will specify for each of the results depending on the machine (calculation time, maximum resolution size), on which machine the results were obtained.
Greedy algorithms
This part only requires for the understanding of algorithms the first part of the course, recorded on part1 algoGlouton.mkv. The code architecture is shown in the codeArchiMakefile.mkv video.
Question 2 Code the void function KpSolverGreedy :: solveUpperBound () of the KpSolverGreedy class, which resolves the continuous backpack by the greedy algorithm and writes the obtained upper bound in the upperBoundOPT field. Note that the objects have already been sorted in descending order of
Question 3 Code the void function KpSolverGreedy :: solveLowerBound () of the KpSolverGreedy class, which implements the greedy heuristic for the discrete backpack and writes the lower bound obtained in the costSolution field and writes the composition of the backpack, in the vector solution.

Question 4 Run several calculations, show that the results obtained are quite consistent.
Exact dynamic programming algorithms
This part only requires the second part of the CM7 for understanding the algorithms, recorded on part2 ProgDynamique.mkv. The architecture of the code is shown in the video codeArchiMake fi le.mkv.
Question 5 Code the void KpSolverDP :: solveIter () and void KpSolverDP :: backtrack () functions of the KpSolverDP class.

Question 6 The exact mode resolution should resolve instances with 100 and 1000 objects. Run several calculations, show that the results obtained are consistent.
1.3 Separation and evaluation algorithm
This part is necessary for the understanding of the Branch & Bound algorithm (B&B) presented as the end of the backpack problem solving course.

Question 6 Encode the void function NodeBB :: solveUpperBound which eliminates the continuous relaxation by greedy approach to give the local upper bound to the considered node of the B&B tree, similarly to void KpSolverGreedy :: solveUpperBound (), with signature:
void solveUpperBound(int kpB, int nbIt, vector & weights, vector & values);
The kpB, nbIt, weights, values fields define the characteristics of the backpack, not known to a NodeBB by the choice of code architecture, and which must therefore be passed as an argument.
A major difference compared to question 6, the fixing of variables in the node induces objects already considered, when isFixed [i] = true, and objects that cannot be selected, with isRemoved [i] = true. The function must verify that the total mass of the imposed objects does not exceed the authorized capacity for the backpack. In this case, we will update the overCapacitated field to true to remove the node later. Otherwise, we continue the greedy computation and we will update the local bound of the localUpperBound node, we store the critical index of the first non-selected object entirely following the greedy order, in the criticalIndex field and its value fractional (potentially 0) in the fractionalVariable field.
Question 7 Code the void function NodeBB :: primalHeuristic similarly to question 3, except that the resolution gives a good lower locale, to be entered in localLowerBound, with a composition of the backpack to be entered in primalSolution. Warning: this function must not modify the localUpperBound, criticalIndex and fractionalVariable fields.

Question 8 The functions of the KpSolverBB class allowing to insert new nodes or to select a node and remove it from the list of current nodes are given:

NodeBB* selectNode();
void insertNode(NodeBB* nod);
void insertNodes(NodeBB* nod1, NodeBB* nod2);
Justify that these functions allow the route to be made in width, depth and according to the best upper bound of the B&B tree.

Question 9 Code the void function KpSolverBB :: solve () allowing to solve the problem by the algorithm
by Branch & Bound. At this stage, we will only code a first version where the bool parameter withPrimalHeuristics; active void NodeBB :: primalHeuristic at each node with withPrimalHeuristics = true and otherwise, primalHeuristic can be called only when an entire solution is found, to retrieve the composition of the backpack using the copyPrimalSolution method of the NodeBB class.
Question 10 Run several calculations, show that the results obtained are consistent.

1.4 Kernel Search Heuristics
This part only needs for the understanding of algorithms the part of the course recorded on part3 HeuristiqueDP.mkv.
Question 11 Code the void function KpSolverHeurDP :: solveUpperBound () which solves the upper bound by greedy approach, as in void KpSolverGreedy :: solveUpperBound (), by adding the storage of the critical index of the first unselected object following the greedy order, in the int lastIndex field of the KpSolverHeurDP class.

Question 12 Code the void function KpSolverHeurDP :: solve () which applies the Kernel Search heuristic. The first phase calculates the upper bound and the critical index by calling the previous function. Then, this defines with [lastIndex nbSelectedReopt, lastIndex + nbUnselectedReopt] the set of indices to be re-optimized, forming a backpack problem of defined size. Index objects less than lastIndex
nbSelectedReopt are selected in the final backpack, objects with index greater than lastIndex + nbUns- electedReopt are not selected in the final backpack, and are not considered in the local optimization. On this induced backpack problem, with only the objects to be re-optimized and by considering the mass induced by the selection of the first objects, we solve the problem exactly like a KpSolverDP.

Question 13 The resolution by Kernel Search should make it possible to find solutions for all instances, with an optimization of the order of 100-1000 objects. Run several calculations, show that the results obtained are consistent.

Question 14 In the KpSolverBB :: init () function, you still have to code an initial solution initialization with KernelSearch dynamic programming history, activated withDPinitPrimalHeuristic = true, with an integer prameter sizeDPheur to indicate the radius of the Kernel Search. Run several calculations, show that the results obtained are consistent.