10. Projects¶

Projects will usually consist of two parts: theoretical questions or exercises to be solved by hand and a programming assignment to put everything you have learned in practice. To that end, the course will use two different platforms: Gradescope and Inginious. Below are some instructions on how to set up and use these two tools, followed by the project descriptions.

10.1. Gradescope¶

Go to Gradescope and connect with your UCLouvain account.
Add the LINFO2266-2023-2024 (Course ID: 625917) course by clicking on Enroll in Course and entering the code JK7D4D.
You will find the theoretical part of the projects there, which consist of a PDF document with a few questions.
Answer these questions either by printing the document or filling it on your computer. If you follow the instructions for the Inginious part, you will find the .tex files in the tex/ folder of the repository so you can fill them directly.
Do not forget to submit your answers on Gradescope when you are done.

10.2. Inginious¶

Go to Inginious and connect with your UCLouvain account.
Find LINFO2266 in the course list ([LINGI 2266] Advanced Algorithms for Optimization) and add it by clicking on Enroll in the course.
Go to the task called Create your repository and enter your Github username. This will create a Github repository with the projects of the course that you can clone on your computer.
This repository contains a Maven project that you can easily open with IntelliJ (or Visual Studio Code with the recommended Java extensions).
For each project, a package is already created in the src/main/java/ folder with some Java classes.
Follow the instructions of each project on how to fill some of those classes.
Once you think you have something working, you can run the tests provided in the corresponding src/test/java/ folder.
Finally, submit your code on Inginious on the task dedicated to each project.

10.3. Project 1: Dynamic Programming¶

If not done yet, follow the instructions given above to enroll to the Gradescope and Inginious courses, as well as retrieving the source code of the projects.

The first project is about Dynamic Programming (DP) and the Traveling Salesman Problem (TSP). It consists of 2 parts:

On Gradescope, find the assignment on DP where you will learn about the TSP and model it on paper with this technique. Submit your answers when you are ready.
Then, go to your personal LINFO2266 Github repository, where you will specify your model and solve real TSP instances.
1. In the dynamicprogramming package, you will find a file called DynamicProgramming.java. This file contains three parameterized classes Model, State and Transition which allow to specify the components of any DP model. Moreover, you will find a class called DynamicProgramming that will compute the optimal solution of a given DP problem. The first exercise is to implement the functions getSolution, getValueForState and rebuildSolution in this class.
2. You can verify your implementation by running the tests for the Knapsack problem, which is already implemented in Knapsack.java.
3. Now it is your turn to implement a DP problem. The second exercise concerns the files TSP.java and TSPState.java where you need to fill the class representing a state of the TSP model and then implement functions specifying the recurrence you imagined in the first part of the project. Take a look at Knapsack.java and KnapsackState.java if you need an example.
4. Run the tests for the TSP to see if your implementation is correct and fast enough.
5. When you are done, do not forget to commit and push your changes before submitting your work on Inginious.

10.4. Project 2: Branch and Bound, Lagrangian Relaxation¶

The second project is about Branch and Bound (BnB), Lagrangian Relaxation and the Traveling Salesman Problem (TSP).

Your implementation work will be in the in the branchandbound package. As a preliminary, step, read first the class called BranchAndBoundKnapsack as this class is a good example of what you will do for the TSP, that is:

Implement the state/node representation for the BnB search.
Implement a lower-bounding procedure to prune the BnB search.

10.4.1. Gradescope¶

On Gradescope, find the written assignment on BnB where you will learn about the TSP and model it on paper with this technique. You can already answer to the Exercises 1 and 2, while Exercise 3 will need to wait until you complete your implementation.

10.4.2. Implementation¶

Then, go to your personal LINFO2266 Github repository, where you will specify the classes to model and solve real TSP instances with branch and bound in the package branchandbound (don’t forget to pull to get the latest update).

The implementation work is composed of four steps:

Implement the simple one-tree based bound procedure in the SimpleOneTree class. You can test your result by executing SimpleOneTreeTestFast.
Implement the branch and bound for the TSP in the BranchAndBoundTSP class which will use the SimpleOneTree bound procedure you just implemented earlier. You can check your result by executing the test testOneTree from BranchAndBoundTSPTestFast.
Implement an enhanced bound calculation for the one-tree based on Lagrangian relaxation in the HeldKarpOneTree class. You can test your result by executing HeldKarpOneTreeFast and the remaining tests from BranchAndBoundTSPTestFast.
Replace in your branch and bound for the TSP BranchAndBoundTSP, the bound calculation by your new reinforced bound. You can test your result by executing BranchAndBoundTSPTest.

Once your implementation is ready, don’t forget to finish your written assignment, by writing your answer for Exercise 3!

10.5. Project 3: Linear Programming and Maximum-Flows¶

In this project, you will model and solve a maximum flow problem and a maximum matching problem with a linear programming solver. It means that for these two problems must be encoded into the form of

\[\begin{split}\max \quad & cx \\ \text{subject to} \quad & Ax \leq b \\ & x \ge 0\end{split}\]

that can be used by the simplex algorithm.

10.5.1. Implementation¶

All the files related to this project are in the package linearprogramming. You have to modify three classes:

FlowMatrices.java : given a FlowNetwork instance, you must compute the coefficient A, b, c for solving the maximum flow problem with the simplex implementation. To retrieve your solution depending on your matrices, you must also fill in the function assignFlow in addition to the constructor.
MatchingMatrices.java : given a bipartite graph, you must compute the coefficient A, b, c for solving the maximum matching problem with the simplex implementation. To retrieve your solution depending on your matrices, you must also fill in the function isEdgeSelected in addition to the constructor.
BigMSimplex.java initializes the simplex method, even when negative values for b are given. You need to fill in the simplex tableau to ensure that it finds a correct solution. Here are some inspirations for implementing it:

In the class LinearProgramming.java lies an implementation of the simplex algorithm, without the initialization.

In TwoPhaseSimplex.java, the initialization is done by adding new variables x_a, called artificial variables, and transforming the objective function. The new objective consists in minimizing the sum of artificial variables: instead of encoding in the simplex tableau

\[\begin{split}\max \quad & cx \\ \text{subject to} \quad & Ax + s = b \\ & s \ge 0 \\ & x \ge 0\end{split}\]

where $s$ are the slack variables, the problem is now

\[\begin{split}\max \quad & - sum(x_a) \\ \text{subject to} \quad & Ax + s + x_a = b \\ & s \ge 0 \\ & x \ge 0 \\ & x_a \ge 0\end{split}\]

In the first formulation, if a $b_i$ was negative, the corresponding $x_i$ could not be used within the base (because it means that $x_i$ should be negative, which is prohibited by the last constraints of the problem). The second formulation thus introduces the artificial variables and use them in the base. In the case where a row includes a negative $b_i$, the row is multiplied by $-1$ (except for the term $x_a$). Thus, we can assume $b \ge 0$ in all cases and solve the problem using $x_a$ as the base.

Once the objective of the second formulation is solved, and that all artificial variables are set to 0, the program switches back to the original objective: $\max cx$.

We ask you to implement a variation of TwoPhaseSimplex.java, that does not work using two phases. Artificial variables are still introduced, but instead of switching between 2 objectives, only one objective is used. The algorithm takes as input a large constant $M >> 0$, and tackles the problem (in tableau form):

\[\begin{split}\max \quad & cx - M \,sum(x_a)\\ \text{subject to} \quad & Ax + s + x_a = b \\ & s \ge 0 \\ & x \ge 0 \\ & x_a \ge 0\end{split}\]

Given that the second term is much larger than the first, this forces the simplex to do a lexicographic search: it will first minimize the use of artificial variables ($\max - M \, sum(x_a)$) and then maximize the original objective ($\max cx$). Your implementation needs to be done within BigMSimplex.java.

You can test your code by running the example in DietProblem.java, that solves the Diet problem .

Once your code is ready, you can submit it onto inginious and work on the report.

10.5.2. Gradescope¶

On Gradescope, find the written assignment for the project 3. Part of your assignment requires to report experimental results under the form of a graph.

10.6. Project 4: Local Search¶

In this project, you will have to develop a local search solver for the Pigment Sequencing Problem (PSP). It is a Discrete Lot Sizing problem where several items must be produced by a single machine that is able to produce one item per time unit. Each item must be produced at the latest at its deadline. Additionally, there are stocking costs and sequence-dependent changeover costs. The objective is to find a production schedule that respects all deadlines and minimizes the sum of stocking and changeover costs.

10.6.1. Formal definition¶

Let $I$ be a set of items to be produced and $T$ a set of types for those items. Each item $i \in I$ is associated to a deadline $d_i$ and a type $t_i \in T$. We write $p_i$ the production period of item $i \in I$. Each item must be produced at a different time period between 0 and $p_{max}$. The stocking cost for each item produced is proportional to the number of time units between the deadline and the production period. Its value for one period of time depends on the item type $S^{t_i}$. Moreover, a changeover cost $C^{t_i,t_j}$ is induced when switching the production of from item type $t_i$ to $t_j$.

Let $x_p$ denote the item produced at time period $p$. If $s_p$ is the first item produced after period $p$ (the machine can be idle at some periods of time), then the PSP can be written as:

$$\begin{aligned} \text{minimize } & \sum_{p = 0}^{p_{max}-1} S^{t_{x_p}} * (d_{x_p} - p) + C^{t_{x_p},t_{s_p}} & \\ \text{such that } & p \leq d_{x_p}, & 0 \leq p < p_{max} \\ & x_{p_1} \neq x_{p_2}, & 0 \leq p_1 < p_2 < p_{max}, x_{p_1} \neq IDLE, x_{p_2} \neq IDLE \\ & x_p \in I \cup \{IDLE\}, & 0 \leq p < p_{max} \end{aligned} $$

10.6.2. Gradescope¶

On Gradescope, find the written assignment for the project about local search. You will first solve a PSP instance by hand and then report and discuss experimental results.

10.6.3. Implementation¶

All the files related to this project are in the package localsearch.

In your local search solver, a candidate solution is an array of variables that represent the production schedule $x$. Implement the missing functions in ChangeoverCostInvariant.java and StockingCostInvariant.java to compute incrementally the cost of a production schedule after an update.
Then, implement the functions in PSP.java to compute an initial feasible solution of the problem, and check if a swap move (with any number of variables concerned) is feasible.
Finally, design your local search solver in LocalSearch.java that finds the best possible solution under a given time limit, by calling the method solve. Some features that can be implemented: swap moves with a dynamic number of periods concerned (similar to $k$-opt), random restarts, intensification vs. diversification tradeoff, etc. Some mandatories functions to implement are:
1. resetSearch that restarts the search, keeping some elements from the best candidate registered
2. getNBestSwaps, an utility method returning the best n swaps that can be operated over the current candidate
3. selectSwap, an utility method selecting a swap to perform within a list of swaps.
4. maybeSaveCurrentCandidate, an utility method replacing the current candidate by the best candidate if its value is better.
These functions will be useful to design your local search solver. How to combine them exactly, when to call them, and what parameters to give them is left for you to implement. You can find related tests for those functions in the LocalSearchTestFast class. Note that these tests will need at least (part of) your solve method to be implemented.

Warning

As this task is quite computationally expensive, please test your code locally and only submit on Inginious when you have made substantial improvements to it.
If you decide to use randomness in your code, be sure to use seeds to ensure that the results found on your machine are the same as the ones on Inginious.

10.7. Project 5: Constraint Programming¶

In the 5th project, you will discover Constraint Programming by solving 2 exercises: the Magic Square Problem and the Killer Sudoku Problem. Those problems are rather hard to solve, and you will use a Constraint Programming solver to tackle them. But first you have to fill in certain functions to ensure that your solver is ready to be used.

10.7.1. Solver implementation¶

Here are the required steps to have your required constraints working:

Implement the removeAbove and removeBelow methods from the Domain class. Those methods will remove all values within a domain that are greater / lower than a given threshold.
Implement the propagator from the Sum constraint. This constraint is applied on an array of Variable $x$ and on one expected sum, $y$. It ensures that $\sum x = y$. Your algorithm must be bound-consistent: you only need to update the maximum and minimum values of the variables present within the constraint.
Implement the propagator from the LessOrEqual constraint. This constraint is applied on two Variable: $x$ and $y$, and ensures that $x \leq y$. Your algorithm must be bound-consistent: you only need to update the maximum and minimum values of the variables present within the constraint.

For each of those steps, you will find corresponding unit tests to ensure that your solver is working as expected before moving on to the modeling.

10.7.2. Modeling the problems¶

There are two problems to model in this project:

The Magic Square Problem. Given an square of $n\times n$ cells, you need to find an assignment of values to each cell such that

Every value appears once and only once;

The sum of every row, column and of both diagonal within the square are the same.

The Killer Sudoku Problem. In this variation of the Sudoku, the cells belong to a group. The sum of values within the cell belonging to a group must equal to a given input value. The whole set of constraints in this problem is thus

Each row, column, and subsquare contains each number exactly once;

The sum of all numbers in a group must match the expected sum of the group.

The implementation needs to be done within the MagicSquareSolver and KillerSudokuSolver files, by completing the TODO’s. In each of those model, you need to give all solutions according to the given input instance by relying on your TinyCSP solver. You can also refer to the already implemented NQueens model if you wish to see how variables should be created, how to add constraints and how to solve a problem.

10.7.3. Gradescope¶

On Gradescope, find the written assignment for the project about constraint programming. You will first give some details about the modeling of a Magic Square Problem. Afterwards, you will examine how to derive additional solutions by examining the symmetries within the problem. Finally, a last step will ask you to run some experiments using your solver.

10.8. Project 6: MDD¶

In the 6th project, you will optimize hard combinatorial problems using the branch-and-bound with MDD paradigm. In practice you are asked to implement: a sequential version for the solver interface, and a model + relaxation to solve the maximum decarbonation problem.

10.8.1. Solver implementation¶

To get started with your implementation of the SequentualSolver we advise you to go read the pseudo-code given in the slides and then to give a look at the parallel version which is implemented for you (ParallelSolver).

Once you are done with the implementation of your sequential solver, you will be able to validate it against the tests in TestSequentialSolver.

10.8.2. Modeling the Max Decarbonation Problem¶

After that, you are asked to model the maximum decarbonation problem in terms of dynamic programming. To that end, you will want to start by defining the content of your state (class MaximumDecarbonationState) and then to implement the required methods in MaximumDecarbonationProblem.

Once you have completed these first two steps, you should validate your implementation against the tests provided in TestMaximumDecarbonationModelFast and TestMaximumDecarbonationModel.

The second step to solving the max decarbonation problem with BaB-MDD will be to implement a relaxation (merge heuristic) to use when compiling relaxed DDs. You are expected to write that implementation in the class MaximumDecarbonationRelaxation. Finally, you will write the implementation of a state ranking which will be used to compare states and select the ones that are deemed the most promising (in class MaximumDecarbonationStateRanking).

Then, you will validate your implementation work using: the tests in TestMaximumDecarbonationFast and TestMaximumDecarbonation.

10.8.3. Gradescope¶

On Gradescope, find the written assignment for the project about branch-and-bound with decision diagrams. You will first get a hands-on reminder of what relaxed and restricted DDs are. Afterwards, you will give the details of how to model the maximum decarbonation problem in terms of dynamic programming along with a relaxation to merge nodes when a layer grows too large.