E-Commerce and Security

Arne Andersson

Integer Programming, a useful optimization tool for business


Integer Programming (IP), a standard language for optimization

Integer Programming (IP) is related to Linear Programming (LP), which is often studied in Algebra courses (and often solved with the Simplex method). The main difference between LP and IP is that in IP, we require that some of the variables, or all variables, in the solution are integers. This, in turn, causes the problem to be computationally more complex. While LP can be solved with polynomial algorithms, IP is NP-hard, which means that no polynomial-time algorithm is known (and probably there will never be a polynomial-time algorithm). Still, there are a number of good software optimizers that can handle many IP problem instances very efficiently in practice. Therefore, by formulating an optimization problem as IP, one can apply a number of carefully tuned standard software solutions. Examples of commercial IP solvers are CPLEX from ILOG and Xpress from Dash Optimization.

Formulating an optimization problem

The basic mathematical formulation of an optimization problem can be described as:

Maximize
expression
subject to
constraints.

This general formulation turns out to be extremely useful in many business optimization cases.
We may for example consider an auction where a seller tries to

Maximize
income
subject to
bid constraints

Example 1

We illustrate how IP can be used to formulate the problem of finding the winning bids in a combinatorial auction.

Assume that you sell four commodities, and receive the following bids:
  Bid A Bid B Bid C Bid D Bid E
Commodity 1 100 102 x    
Commodity 2 103 99   x x
Commodity 3 100     x x
Commodity 4 105 106 x   x
Comb price     200 205 305

Altogether, there are a total of 10 bids, three of them are combinatorial bids.

In order to apply Integer Programming, we would define one binary variable per bid:

We can now express the income from bid A1 as 100 * A1, i.e. if A1 = 1 the income from bid A1 is 100, otherwise the income is 0.
In the same way, we can express the income from each bid. The total income is the sum of all incomes, and this is the expression we wish to maximize:

Maximize
100 A1 + 103 A2 + 100 A3 + 105 A4 + 102 B1 + 99 B2 + 106 B4 + 200 C + 205 D + 305 E (total income)

However, we can not accept all bids, since we can only sell one of each commodity. Therefore, we need to express the fact that for each commodity, we can only accept one of the bids. This gives the following constraints:

subject to
A1 + B1 + C = 1 (A1, B1, C bid on Commodity 1, so only one of them can win)
A2 + B2 + D + E = 1 (A2, B2, D, E bid on Commodity 2, so only one of them can win)
A3 + D + E = 1 (A3, D, E bid on Commodity 3, so only one of them can win)
A4 + B4 + C + E = 1 (A4, B4, C, E bid on Commodity 4, so only one of them can win)

In this case, there is one unique optimal solution with three winning bids:
B1 = 1, B4 = 1, D= 1, all other variasbles are 0.
The income becomes 413.

Example 2

Assume that we have received the bids above, and we wish to solve the following problem:
"Given the bids, what is my largest income if I sell only three of the four commodities?"

We use one binary variable per bid, A1, A2, ... E, as above. But we also use one binary variable per commodity:

Our IP formulation becomes

Maximize
100 A1 + 103 A2 + 100 A3 + 105 A4 + 102 B1 + 99 B2 + 106 B4 + 200 C + 205 D + 305 E (total income)
subject to
A1 + B1 + C = Com1 (Com1 tells whether we sell Commodity 1 or not)
A2 + B2 + D + E = Com2 (Com2 tells whether we sell Commodity 2 or not)
A3 + D + E = Com3 (Com3 tells whether we sell Commodity 3 or not)
A4 + B4 + C + E = Com4 (Com4 tells whether we sell Commodity 4 or not)
Com1 + Com2 + Com3 + Com4 = 3 (This equation states that we sell three commodities)

In this case, the optimal solution contains two winning bids
B4 = 1, D= 1, all other variables are 0.
The income becomes 311.