
You might have heard about classical mathematical problems, such as the Travelling Salesman Problem or the 0/1 Knapsack Problem. There are several options to solve such optimization problems, but the most basic one is trying to find the exact solution. For this purpose, most mathematicians apply integer linear programming, ILP in short. When I was introduced to this in a university course, it was very confusing. Usually the professor would give us an elaborate problem statement, which could be boiled down to an ILP containing less than ten lines. The trick is to make the conversion from such a real life problem to a mathematical model. Together with my classmates I found it quite challenging to do so. Fortunately along the way we developed a list of five questions which enabled us to analyse the problem in a structured way. Even more: it made writing down the actual model much easier. In this article I will explain this approach in detail in order to help you with modeling your next ILP. This will be done by applying it immediately to a real-life problem: the 0/1 Knapsack problem. To start, here are the five questions:
- What are the sets?
- What are the parameters?
- What are the decision variables?
- What is the goal of the optimization?
- What are the constraints that I should keep in mind?
Problem statement
An investor is considering seven investments. In the figure below you can find the cash required and the net present value (NPV) per investment.

The investor has €15,000 available and wants to invest in such a way that the total NPV gets maximized without exceeding the available cash. An investment can either be taken or not, but not partially. The question to you is: which investments should be bought?
Sets
In essence, a set is a collection of elements. Elements can be literally anything: cities, patients, trucks, you name it. Usually, it becomes clear what the sets are when reading the problem statement. In this case the table shows a collection of investments, so that will be our set. We will refer to this set with the letter I.
Parameters
A parameter can also be called a variable, and contains a specific value, usually connected to one of the sets. This can, again, be literally anything. In our case it is the cash required and the NPV by each investment, which will be denoted as cᵢ and npvᵢ respectively. Note that the subscript i specifies the investment for c and npv. Finally, there is a parameter that is not connected to one of the sets, but is nevertheless quite important: the investment budget b.
Decision variable
The decision variable is, as the name already suggests, a variable that can be altered by the decision maker. In ILPs this is done in such a way to maximize (or minimize) the objective function. So, you should look for choices that should be made by you, according to the problem statement. In our example, it is stated in the very last sentence of the problem: which investments should be bought? Mathematically, we use the binary variable xᵢ to indicate whether investment i is bought (1) or not (0).
Goal
The goal of a mathematical model is usually quantified with an objective function. It is common to maximize this function, but minimization comes down to the same idea. The goal of our example is to maximize the NPV of the investor’s portfolio. For each investment, it should be determined if it is bought or not, and if so, we should add the corresponding NPV to our total revenue. This is done in line 1a in the next figure: it sums over all investments and multiplies the decision variable xᵢ with the parameter npvᵢ. After all, if xᵢ equals 0, nothing gets added, but it does when xᵢ equals __ 1. Note that _ma_x is written before the objective function, making clear that the goal is maximization.
Constraints
If there would be no restrictions, the ILP with only line (1a) will decide to go for all investments. However, this is not the case: there is a cash budget b that cannot be exceeded. So, the cash required for all the investments made cannot be bigger than this b. Similar to line (1a), the total cash required is computed with a summation over all investments and a multiplication between the decision variable xᵢ and the parameter cᵢ.
In mathematical notation…

The last line, (1c), is called the integrality constraint and tells us what kind of values the decision variable can get. In this case it is a binary variable, because we are solving the 0/1 Knapsack problem.
But what about the investor?
Having transferred the problem statement into an actual ILP, you might wonder what the solution of this Knapsack problem is. Ideally, you would select investments 1, 2, and 5 which require €14,500 (leaving €500 as a leftover) and have a total NPV of €46,000.
For next time…
So, what I would like you to take home is the structured approach that we followed. Try to ask yourself these five questions everytime you read the problem statement. If you have done this a couple of times, it will become much easier to model more complex ILPs and to analyse them. So next time you come across a Traveling Salesman Problem, Knapsack problem, or a Set Cover, you know what to do!