1 Ob jective
CO 353 Winter 2018: Project 4
Due: April 4nd at 8pm
The project consists in implementing the branch-and-bound algorithm for integer programming. Given c ∈ Zn, l ∈ Zn, u ∈ Zn, b ∈ Rm and A ∈ Rm×n, an integer programming problem is formulated as
min cTx s.t. Ax = b
l≤x≤u x ∈ Zn.
To cope with floating-point rounding inaccuracies, we use a tolerance ε = 10−6 for (i) the reduced costs, (ii) the bound constraints, and (iii) the integrality constraints: if, for all j, x∗ satisfies
l j − ε ≤ x ∗j ≤ u j + ε
and eitherx∗j −⌊x∗j⌋≤εorx∗j −⌊x∗j⌋≥1−ε,
then x∗ is considered feasible.
This project can be completed in groups of 1 or 2. You can also form groups of 3, but only if you first get my approval by email (lpoirrier (at uwaterloo)) by March 26th. If you already had approval for a group of 3 for a previous assignment, then you are automatically allowed (but not required) to form the same group of 3 for this assignment (no need to contact me in this case).
2 Input and output
The input is exactly the same as for the previous assignment (Project 3). We simply add the implicit constraint xj ∈ Z for all j. Also, note that for simplicity we can assume c, l, u ∈ Zn.
The output file contains either one or two lines (aside from optional comment and empty lines that are ignored, see below). The first line is either the word infeasible if the problem is infeasible, or the word optimal if the problem is feasible. In the latter case, the second line describes an optimal integer solution (n integers: x∗j for j = 0, . . . , n − 1). If the problem is infeasible, there is no second line.
In order to (optionally) let you include more information in the output file, everything between a # sign and the end of a line will be ignored. Empty lines are also allowed and ignored.
Example input and output files are given at https://www.math.uwaterloo.ca/~lpoirrie/co353.html.
1
3 Running the code
Your code must take exactly two arguments. The first argument is the name of a file containing the input integer programming instance. The second argument is the name of a file where the output is to be written.
You have a choice between the following languages for the implementation: C, C++ or Python.
3.1 In C or C++
Your code must be portable to any environment with a standards-conforming C or C++ compiler. It must be possible to compile and run it by using the following commands:
in C: in C++:
In other words, you must implement your code in a file called bb.c (in C) or bb.cpp (in C++). BB stands for branch-and-bound.
Note: Optionally, you may provide a Makefile, in which case your code will be compiled by running make. The resulting executable must be named bb. If you choose to do this, it is your responsibility to ensure that the Makefile is correct, so do it only if you are familiar with Makefiles already.
3.2 In Python
It must be possible to run your code by executing the following command:
In other words, you must provide a source file called bb.py (if you want, bb.py can import code from other files). BB stands for branch-and-bound. If you need a specific version of the Python language, include the string ”python2” or ”python3” somewhere in bb.py, for example in a comment.
4 Submitting the project
You submit your implementation by sending a single email to both lpoirrier (at uwaterloo) and wjtoth (at uwaterloo), by 8pm on Monday, April 4nd, 2018. Late submissions will not be accepted. The subject line of your email must contain the string CO353. Your email must contain a single attachment file: an archive in the format .zip or .tgz. The name of the archive is formed by the UWaterloo IDs of your group members, in any order, separated by underscores. For example: jwtoth lpoirrie.tgz. The archive contains (at least) two files:
• a source file for your implementation, and
• a file called notes.txt (or notes.md if you prefer).
gcc -O3 -o bb bb.c ./bb input.txt output.txt
g++ -O3 -o bb bb.cpp ./bb input.txt output.txt
python bb.py input.txt output.txt
2
The file notes.txt only specifies the names of the (1, 2 or 3) members of your group. No further explanations are required for this assignment (although you are allowed to put explanations there if you wish to highlight something you did particularly well in your code).
5 Contribution
You can use the standard library in your language of choice. In addition, you are allowed to use an external library that handles linear algebra, and to reuse the code that you wrote for the previous assignment (Project 3). For C++ you can use Eigen, for Python you can use NumPy. Do not include these libraries in the archive that you send by email: you can assume that they are installed and available (for example, #include “Eigen/Dense”, #include <Eigen/Dense>, import numpy and from numpy import * will all work in their respective languages).
Aside from that, no other library is allowed. In case of doubt ask me. You can consult any source of information you want (books, internet, scientific papers, etc.), but copying code is not allowed, regardless of the source. Every single line of your code must be written by a member of the group. Each member of the group must understand (and must be able to justify) every line of the code, including the ones they did not write. After the due date, I may call an individual group member to come to my office hours; if that member does not show sufficient understanding of the code, all group members will get zero.
6 Grading criteria
The project will be graded on a total of 10 marks, divided in 4 categories. Pay attention to the first one: if your code does not follow the specification, it will not be tested, and you will get zero for all the rest.
- Specification (1 mark). Your submission must follow the specifications given in this document (your email must have the correct recipients/subject/attachment, your source files must follow the template given above, your code must compile and take the right arguments). The rules are rigid because testing is automated.
- Code quality (1 mark). It should be reasonably easy to understand your code. Comments can be used to help in that regard, but with moderation. The code itself must be clear and readable.
- Correctness (4 marks). Your code must be an implementation of the branch-and-bound method. When the problem given in input is feasible, the output must describe an optimal solution. When the instance is infeasible, this must be correctly identified.
- Efficiency (4 marks). Your code must correctly implement “pruning” (whenever possible, branching is avoided), and “warm-start” (whenever possible, restart from some previously-optimal simplex basis instead of the all-slack basis).
3