Improving model formulation

Specific Domains Optimization (Mathematical)
,
1

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:


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:

# 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:
    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:
    @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.

2

Maybe split the variables into “amount bought and kept” and “amount bought and sold”?

3

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.

4

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?

5

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}

6

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.

1 Like
7

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.

8

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?

9

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.

10

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:

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:

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:

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)
11

Thank you

1 Like