CSC 495-001, Spring 2020 Programming/Homework Assignment 2 page 1 of 3
Due: Tuesday, March 24, at 11:00 PM
Note: Due dates for the last two homeworks may need to be adjusted or, the two
homeworks may be combined.
Purpose. This assignment has several objectives.
1. You will formulate branching strategies, upper bounds, and lower bounds for a
new problem.
2. You will formulate a problem instance as a binary integer programming instance.
3. You will carry out computational experiments and document their results.
4. You will develop a branch and bound algorithm with at least two levels of so-
phistication.
5. You will develop/use infrastructure for running and documenting experiments,
including techniques for reporting runtime, solution quality, and other statistics,
putting these in spreadsheets, and creating charts.
6. You will (use scripts to) generate random problem instances to assess effective-
ness of algorithms.
Written part (counts as homework)
Recall the definition of the knapsack (optimization) problem.
Given n items, where item i has a weight wi and a value vi, and a capacity
C, find a subset I of {1, . . . , n} such that ∑i∈I wi ≤ C and ∑i∈I vi is
maximized.
The following questions address strategies that will lead to a good branch and bound
algorithm for the knapsack problem and an approach that allows it to be solved using
CPLEX.
Note: Since knapsack is a maximization problem the traditional roles of upper and
lower bounds are reversed: the total value of a feasible solution is a lower bound on
the value of an optimum solution; a “proof” that the value of a solution cannot be
more than V is an upper bound.
1. Based on what we learned about the greedy heuristic for knapsack, what might
be a good branching strategy?
2. A trivial lower bound for a smaller instance of knapsack is simply the total value
of items chosen to be part of the solution. Come up with a better lower bound.
CSC 495-001, Spring 2020 Programming/Homework Assignment 2 page 2
3. A trivial upper bound on the value of a solution is the value of items already
packed plus the total value of the remaining items (omitting ones that have been
excluded). Come up with a better upper bound. Think about the maximum
value that could possibly fill the remaining empty space.
4. Formulate the knapsack problem as a binary integer programming problem.
Programming part
Your assignment is to implement a branch and bound algorithm for the knapsack
problem that incorporates your answers to questions 1–3 above. Your program should
be able to run in either plain mode (trivial lower and upper bound) or with the answers
to 2 and 3 incorporated (tuned). Branching should be the same for both modes (using
your answer to 1).
Input format. Input should be a text file with the following specifications: (i) a line
that begins with # should be ignored – it is a comment; (ii) (ignoreing comments)
the file begins with a line of the form k n C, where n is the number of items and C
the capacity; and (iii) each subsequent line is of the form i wi vi, where wi and vi are
integers representing weight and value of item i, respectively. A small example of an
input file is
# This example is used to illustrate
# case 1 of the proof of the ratio for the modified greedy heuristic
k 4 30
# item a
1 10 15
# item b
2 10 14
# intem c
3 15 20
# item d
4 16 20
Output Format. When you debug your programs and even when you are running
them in “production mode” you will want to print a variety of information. Anything
that is not part of the specifications detailed below should be printed to stderr
instead of stdout.
Output for each run should consist of the filename, the number of items, the capacity,
the number of items packed, the total value of items packed, the total weight of items
packed, the mode (plain or tuned), the runtime (integer in milliseconds), the number
of branches (each smaller instance generated counts as a branch), and a list of items
in the solution, each item on a line starting with i- Each line should contain the
name of the field, followed by whitespace (a tab makes the output easy to read). A
sample output is as follows (runtime and branches are made up).
CSC 495-001, Spring 2020 Programming/Homework Assignment 2 page 3
filename case_1.txt
items 4
capacity 30
packed 2
value 35
weight 26
mode plain
runtime 119
branches 2
i- 1
i- 4
Supporting scripts are still in progress. The highest priority is a script that generates
random instances given the following information
• number of items n (mandatory)
• range of weights wlow, whigh
• capacity, default is n/2·wavg, rounded to nearest integer, where wavg = (wlow + whigh)/2
• range of values vlow, vhigh
Weights and values, respectively, will be chosen uniformally at random in ranges
[wlow, whigh] and [vlow, vhigh].
Recommendations. As with Program 1, you may find it convenient to suppress
output of the solutions when running on a large number of larger instances. Consider
adding a command-line option that accomplishes this, e.g., -q or --quiet.
The best way to store smaller instances is to maintain a vector of length n with each
item marked as one of in, out, or undecided. When doing a recursive call, there is no
need to copy this vector. All you need to do is push the item you are branching on
onto a stack. When you return, you simply pop the item and reset it to undecided.
You will also want to have a vector (or list) that records the current best lower bound.
Report. The report and the grading scheme for the programming are based on those
for Program 1. Be sure to take comments on your first program submission to heart.