# Improving model formulation
**URL:** https://discourse.julialang.org/t/improving-model-formulation/109252
**Category:** Optimization (Mathematical)
**Tags:** jump, optimization
**Created:** [January 25, 2024, 12:15pm UTC](https://discourse.julialang.org/t/improving-model-formulation/109252 "2024-01-25T12:15:02Z")
**Posts on this page:** 11
**Page:** 1
### Author:  [@Lemma](https://discourse.julialang.org/u/Lemma)
#### Post date: [January 25, 2024, 12:15pm UTC](https://discourse.julialang.org/t/improving-model-formulation/109252/1 "2024-01-25T12:15:03Z")
I’m currently working on a sales optimization problem using JuMP in Julia. The challenge involves representing the total sales value under specific constraints. However, my current approach leads to bilinear terms, which seem overly complex for this problem. I’m wondering if there’s a more straightforward formulation that avoids these bilinear terms. There are binary variables as well which will make the problem MIQP, but these have been left out from here.
**Conditions** :
1. **Item Purchase** : Each year, exactly one item is purchased, represented by `y[i]`.
2. **Item Sale** : Items purchased in previous years can be sold in the current year. The amount sold is a fixed percentage of all items held.
**JuMP Model Setup** :
```using
model = Model()
@variable(model, 0 <= y[i=1:3] <= 1) # Percentage of item purchased each year
@variable(model, 0 <= z[i=1:3, t=1:3] <= 1) # Percentage of item sold
# Sale price matrix
sales_matrix = [100 95 90;
0 98 92;
0 0 80]
```
**Current Expression** :
The total sales value at time `t` is formulated as:
```julia
# Fix z[i, t] to 0 for t < i, as we cannot sell an item before it is bought
for i in 1:3
for t in 1:(i-1)
fix(z[i, t], 0;force=true) # This fixes z[i, t] to 0 for t < i
end
end
@expression(model, total_sales[t=1:3],
sum(sales_matrix[i,t] * (y[i] - sum(z[i,k] for k in 1:(t-1))) * z[i,t] for i in 1:t))
```
**Additional Constraints** :
- To ensure the amount sold does not exceed the amount purchased:
```julia
for i in 1:3
@constraint(model, sum(z[i,t] for t in 1:3) <= y[i])
end
```
- For a uniform sale percentage across all items:
```julia
@variable(model, 0 <= alpha[t=1:3] <= 1)
for t in 1:3
for i in 1:t
@constraint(model, z[i,t] == alpha[t])
end
end
```
**Question** :
Is there an alternative formulation for this optimization problem that avoids the use of bilinear terms? The current model seems overly complex for what appears to be a straightforward problem. I’m looking for suggestions on how to simplify the model or represent it more efficiently, especially regarding the bilinear terms in the `total_sales` expression.
---
### Author:  [@gdalle](https://discourse.julialang.org/u/gdalle)
#### Post date: [January 25, 2024, 12:41pm UTC](https://discourse.julialang.org/t/improving-model-formulation/109252/2 "2024-01-25T12:41:12Z")
Maybe split the variables into “amount bought and kept” and “amount bought and sold”?
---
### Author:  [@Lemma](https://discourse.julialang.org/u/Lemma)
#### Post date: [January 25, 2024, 1:07pm UTC](https://discourse.julialang.org/t/improving-model-formulation/109252/3 "2024-01-25T13:07:36Z")
Thanks for the suggestion. Could you please elaborate how this will work in this problem? Each year we can sell, but it has to the same percentage of all items held.
---
### Author:  [@gdalle](https://discourse.julialang.org/u/gdalle)
#### Post date: [January 25, 2024, 2:58pm UTC](https://discourse.julialang.org/t/improving-model-formulation/109252/4 "2024-01-25T14:58:53Z")
I’m not sure I understand the problem. How many item types are there? I thought `i` and `t` were both time variables? Why speak of percentage and not quantities?
---
### Author:  [@Lemma](https://discourse.julialang.org/u/Lemma)
#### Post date: [January 25, 2024, 3:10pm UTC](https://discourse.julialang.org/t/improving-model-formulation/109252/5 "2024-01-25T15:10:39Z")
I use i to represent the time at which an item is purchased and t to represent the time at which we evaluate this expression. So each year, we can purchase an item or sell an item. If we sell, we will need to sell a percentage of all items held at that time. If we look at 100 years, we will have 100 items at t=100. We can work with quantities instead of percentages and it will require changing variable definitions, but we will still need to enforce that if we sell at a particular year it should be the same percentage of all items held. Mathematically, this is how this expression evaluates assuming sales prices are given as:
\begin{bmatrix} S\_{1,1} & S\_{1,2} & S\_{1,3} \\ 0 & S\_{2,2} & S\_{2,3} \\ 0 & 0 & S\_{3,3} \end{bmatrix}
#### Expanded Expression for Years ( t = 1, 2, 3 ):
- Year t = 1:
\text{Total Sales Value at } t = 1: S\_{1,1} \cdot y\_{1} \cdot z\_{1,1}
- Year t = 2:
\text{Total Sales Value at } t = 2: S\_{1,2} \cdot \left( y\_{1} - z\_{1,1} \right) \cdot z\_{1,2} + S\_{2,2} \cdot y\_{2} \cdot z\_{2,2}
- Year t = 3:
\text{Total Sales Value at } t = 3: S\_{1,3} \cdot \left( y\_{1} - z\_{1,1} - z\_{1,2} \right) \cdot z\_{1,3} + S\_{2,3} \cdot \left( y\_{2} - z\_{2,2} \right) \cdot z\_{2,3} + S\_{3,3} \cdot y\_{3} \cdot z\_{3,3}
---
### Author:  [@odow](https://discourse.julialang.org/u/odow)
#### Post date: [January 25, 2024, 8:18pm UTC](https://discourse.julialang.org/t/improving-model-formulation/109252/6 "2024-01-25T20:18:29Z")
Do you have access to Gurobi? It can solve MIQPs. So as a first step, I would see if it can solve your problem in a reasonable time, and only if it can’t would I look to reformulate.
But as @gdalle says, the issue is the use of percentages. If the denominator is a decision variable, that inherently makes the problem non-linear because you have `numerator / denominator`. Percentages usually work well when the total quantity is a constant.
---
### Author:  [@Lemma](https://discourse.julialang.org/u/Lemma)
#### Post date: [January 25, 2024, 9:10pm UTC](https://discourse.julialang.org/t/improving-model-formulation/109252/7 "2024-01-25T21:10:57Z")
I do not have access to Gurobi, so it seems that reformulating the problem is the most practical approach. I am open to exploring solutions that may provide approximate or locally optimal results.
I seek further clarification regarding the use of percentages in the model. Although I can define the variables as either quantities or percentages, the benefits of shifting to a quantity-based approach are not fully apparent to me. In my existing model, I assume a sales price matrix is given that can be scaled to represent percentages. On the other hand, a direct approach using quantities is possible, assuming I set certain arbitrary upper limits for the variables y\_{i} and z\_{i,t}. One alternative formulation I have considered is as follows: \sum\_{i}^t S\_{i,t} \cdot z\_{i,t}, \forall t. However, this doesn’t seem equivalent and may not ensure that the same percentage of all held items is sold.
The complexity introduced by what appears to be a straightforward expression, leading to MIQP problem, is somewhat baffling to me. I am convinced that there must be a more streamlined and simpler way to frame this problem. Any insights or suggestions on this matter would be highly appreciated.
---
### Author:  [@gdalle](https://discourse.julialang.org/u/gdalle)
#### Post date: [January 26, 2024, 7:45am UTC](https://discourse.julialang.org/t/improving-model-formulation/109252/8 "2024-01-26T07:45:12Z")
I think I understand a bit better, and after some fiddling with variable definitions, I was able to shift the bilinear term from the objective to the constraints but not remove it entirely.
Can you explain the business reason behind selling the same percentage for all items?
---
### Author:  [@Lemma](https://discourse.julialang.org/u/Lemma)
#### Post date: [January 26, 2024, 8:52am UTC](https://discourse.julialang.org/t/improving-model-formulation/109252/9 "2024-01-26T08:52:50Z")
There is not a particular reason behind selling same percentage of all items. If this was not required then I believe the problem is much simpler. This expression that contains bilinear terms appears in constraints only and not in the objective function.
---
### Author:  [@odow](https://discourse.julialang.org/u/odow)
#### Post date: [January 28, 2024, 10:48pm UTC](https://discourse.julialang.org/t/improving-model-formulation/109252/10 "2024-01-28T22:48:36Z")
> [@Lemma](#):
>
> The complexity introduced by what appears to be a straightforward expression, leading to MIQP problem, is somewhat baffling to me.
Using a percentage in which the denominator is a decision variable results in a non-convex problem.
I thin this example is a simplification of what you’re trying to do:
```Julia
model = Model()
@variable(model, inventory_in == 1)
@variable(model, inventory_out >= 0)
@variable(model, purchase >= 0)
@variable(model, 0 <= sell_fraction <= 1)
@expression(model, sales, inventory_in * sell_fraction) # <-- this is the difficulty
@constraint(model, inventory_out == inventory_in - sales + purchase)
```
Dealing with `continuous * continuous` is hard.
You need to approximate it somehow.
One option is to discretize the set of `sell_fraction`:
```julia
fractions = [0.0, 0.25, 0.5, 0.75, 1.0]
N = length(fractions)
@variable(model, sell_fraction[1:N], Bin)
@constraint(model, sum(sell_fraction) == 1)
@expression(
model,
sales,
# continuous * constant * binary
sum(inventory_in * fractions[i] * sell_fraction[i] for i in 1:N),
)
```
Now you have `continuous * binary`, which you can reformulate using a big-M:
```julia
fractions = [0.0, 0.25, 0.5, 0.75, 1.0]
N = length(fractions)
@variable(model, sell_fraction[1:N], Bin)
@variable(model, sales)
M = 100
@constraints(model, begin
sum(sell_fraction) == 1
[i in 1:N], sales <= fractions[i] * inventory_in + M * (1 - sell_fraction[i])
[i in 1:N], sales >= fractions[i] * inventory_in - M * (1 - sell_fraction[i])
end)
```
---
### Author:  [@Lemma](https://discourse.julialang.org/u/Lemma)
#### Post date: [January 30, 2024, 11:14am UTC](https://discourse.julialang.org/t/improving-model-formulation/109252/11 "2024-01-30T11:14:30Z")
Thank you