06. List of all analyzed problems

List of all analyzed LP problems

The Portfolio Optimization Problem

This LP problem involves finding the optimal allocation of assets in a portfolio in order to maximize returns or minimize risk.

Parameters:

• $C$ : available capital

Decision variables:

• $x_1$ : amount of money invested in stock of type 1
• $x_2$ : amount of money invested in stock of type 2

The Resource Allocation Problem

This LP problem involves finding the optimal allocation of resources (such as time, money, or materials) to different activities in order to maximize some objective.

The Production Planning Problem

This LP problem involves finding the optimal production levels of different products in order to maximize profits or minimize costs.

Typical example:

Sets:

• $T=\{1,\dots ,3\}:$ set of months

Parameters:

• $b$ : production capacity of $A$
• $b^{\prime }:$ production capacity of $B$
• $c$ : unit production cost for $A$
• $c^{\prime }$ : unit production cost for $B$
• $m:$ inventory cost per unit and month
• $d_t$ : sales forecast for month $t$, for $t\in T$

Decision variables

• $x_t$ : units produced by $A$ in month $t$, for $t\in T$
• $x_t^{\prime }$ : units bought from $B$ in month $t$, for $t\in T$
• $z_t$ : units in inventory at the end of month $t$, for $t\in T\cup \{0\}$

Model

$$\begin{array}{rl}& \min \sum _{t\in T}\left(c{x}_t+c^{\prime }{x}_t^{\prime }+m{z}_t\right)\text{ (cost) }\\ & \text{ s. t. }{x}_t\le bt\in T\text{ (capacity of A) }\\ & x_t^{\prime }\le b^{\prime }t\in T\text{ (capacity of B) }\\ & z_{t-1}+x_t+x_t^{\prime }\ge d_{t}t\in T\text{ (demand) }\\ & z_{t-1}+x_t+x_t^{\prime }-d_t=z_{t}t\in T\text{ (inventory balance) }\\ & z_0=0\text{ (starting condition) }\\ & x_t,x_t^{\prime },z_t\ge 0t\in T\text{ (nonnegative variables) }\end{array}$$

Observe that the (demand) constraint is redundant, as it is implied by $z_{t-1}+x_t+x_t^{\prime }-d_t=z_t\ge 0$.

Minimum lot size example

It’s not so rare that you have to account a minimum lot size. We add the binary variables:

• $y_t:1$ if production is active at month $t$, or 0 otherwise, for $t\in T$

and the constraints

$$\begin{array}{lll}{x}_t\ge l{y}_t& t\in T& \text{ (minimum lot size) }\\ x_t\le M{y}_t& t\in T& \text{ (activation) }\end{array}$$

where is the minimum lot size, and $M$ is equal to the monthly productive capacity.

Note that the activation variable is a common “pattern” to keep the LP linear.

Diet optimization

This is a classic LP problem that involves finding the optimal combination of foods to eat in order to meet certain nutritional requirements at the lowest cost.

Packet routing

With $a_i$ the capacity consumed by $i$-th packet, $c_{i1}$ cost consumed by the $i$-th packet on link 1, $k_1$ and $k_2$ the constraints on each link and $x_i$ decision variables.

$$\begin{array}{cl}\text{min}{\sum }_{i\in I}{c}_{i1}{x}_i+c_{i2}\left(1-x_i\right)& \text{ (cost) }\\ {\sum }_{i\in I}{a}_i{x}_i\le k_1& \text{ (capacity 1) }\\ {\sum }_{i\in I}{a}_i\left(1-x_i\right)\le k_2& \text{ (capacity 2) }\\ x_i\in \{0,1\},i\in I& \text{ (binary variables) }\end{array}$$

We can also ‘expand’ this formulation obviously for many links. In that case the decision variables will be $x_{ij}$ : set to 1 if packet $i$-th is sent over $j$-th link.

Also remember to explicit the constraint: ${\sum }_j^{\text{number of links}}{x}_{ij}=1$ which in case of 2 links was kept ‘implicit’.

The Assignment Problem

This LP problem involves finding the optimal assignment of workers to tasks, in order to minimize the total cost of the assignments.

Sets:

• $I=\{1,\dots ,n\}$ : months

Parameters:

• $d_i$ : demand for month $i,i\in I$

Decision variables:

• $x_i$: number of expert workers available in month $i,i\in I$
• $y_i$: number of workers training during month $i,i\in I$

Model:

$$\begin{array}{ccc}\min & 2000{\sum }_{i\in I}{x}_i+1000{\sum }_{i\in I}{y}_i& \\ \text{ s. t. }& 160x_i-50y_i\ge d_i,i\in I& \text{ (demand) }\\ \lfloor 0.95x_i\rfloor +y_i=x_{i+1},i\in I& \text{ (number) }& \\ x_1=\text{initial number of workers}& & \\ x_i,y_i\in {\mathbb{Z}}^{+},i\in I& \text{ (nonnegative integer variables) }& \end{array}$$

Floor function replacement example

Constraint (number) is nonlinear. By dropping the $\lfloor \cdot \rfloor$ operator, we obtain the constraint

$$0.95x_i+y_i=x_{i+1}i\in I$$

which is not correct since, due to the integrality requirements on the variables, it forces $x_i$ to be a multiple of 100 (such that $0.95x_i$ will always be an integer value).

Constraint (number) can be formulated in a linear way by introducing for each $i\in I$ an auxiliary integer variable $z_i$ that represents $\lfloor 0.95x_i\rfloor$, and by adding the auxiliary constraints:

$$\begin{array}{cl}{z}_i+y_i=x_{i+1},i\in I& \text{ (number2) }\\ 100z_i\le 95x_i\le 100z_i+100,i\in I& \text{ (floor) }\\ z_i\in {\mathbb{Z}}^{+},i\in I& \text{ (nonnegative integer variables) }\end{array}$$

Then we clearly have $z_i=\lfloor 0.95x_i\rfloor$.

Transportation problem

This LP problem involves finding the optimal way to distribute a product from a set of sources to a set of destinations at the lowest cost.

The Facility Location Problem

This LP problem involves finding the optimal location for a facility (such as a factory or warehouse) in order to minimize costs or maximize profits.

The problem is an important extension of the transportation problem where we have to decide not only the transportation plan for supplying the goods from the wharehouses to the clients, but also the candidate sites (locations) in which to open (activate) the warehouses.

The Knapsack Problem

This LP problem involves finding the optimal selection of items to include in a knapsack, in order to maximize the total value of the items while staying within the knapsack’s weight limit.

IMP - Influence maximization in social networks

The problem of finding a set of $k$ most influential users in a social network which maximizes the diffusion spread of a marketing campaign can be seen as an Influence Maximization Problem $(\mathrm{IMP})$.

To solve the Influence Maximization Problem (IMP), we are given a directed weighted graph $G=⟨V,A⟩$ representing a network where each node $i$ corresponds to a user, and each arc $(i,j)\in A$ indicates a relationship between user $i$ and user $j$.

To define the diffusion spread, we use the deterministic Linear Threshold (LT) model, where each node $j$ gets active only if the sum of the incoming arc weights $w_{ij}$ over all the active neighboring nodes of $j$, reaches a given threshold ${\theta }_j$.

The propagation defined by the LT model evolves as a deterministic process over a discrete time horizon.

DNA sequence

To store a large set of strings, such as DNA sequences, we can use compact storage for similar sequences. The problem is to store many similar entries in a compact way, assuming the strings are binary. We can compute the Hamming distance between each pair of sequences (number of bits that need to be flipped to obtain the other sequence) to satisfy the properties of a distance function. Indeed distance hamming satisfies the three usual properties of a distance: nonnegativity, symmetry and triangle inequality. In order to exploit redundancies between sequences and to save memory, we can store only one of the sequences and then construct a complete graph $G$ with a node for each difference. The problem of deciding which differences to memorize, so as to minimize the total number of bits used for storage, can be reduced to the problem of finding a minimum-cost spanning tree in an appropriate graph: only one sequence is completely stored, the spanning tree will be connected so that is possible to retrieve any sequence.

In order to exploit redundancies between sequences and to save memory, we can store only one of the sequences and then construct a complete graph $G$ with a node for each difference. The problem of deciding which differences to memorize, so as to minimize the total number of bits used for storage, can be reduced to the problem of finding a minimum-cost spanning tree in an appropriate graph: only one sequence is completely stored, the spanning tree will be connected so that is possible to retrieve any sequence.