Optimization problem with Julia - Launch sequence

Say you have n different shops in which you want to launch a product for n different months, and you want to maximize profits. The problem is determining the order of the launch sequence of the product when the price in shop_i refers to the average price for the product in some given set of the shops. It is only possible to launch in one shop for every month, and it is only possible to launch one time in each shop. For every shop there is an initial price of the product, some given customer size, and baskets referring prices. Look at the following example:

initial_price = [1,2,4],

customer_size = [20, 15, 10]

referring_basket_shop_1 = {price_shop_2,price_shop_3}

referring_basket_shop_2 = {price_shop_3}

referring_basket_shop_3 = {price_shop_1, price_shop_2}

The first shop to launch the product initiates the price with the initial_price parameter. If referring_basket_shop_i contains no launched shops, price_shop_i = initial_price_i. If referring_basket_shop_i contains launched shops, price_shop_i will be the average price of the launched prices in referring_basket_shop_i.

Calculating all possible outcomes and determining the best one is a n! problem, so I want to use Julia optimization (I don’t know which solver is the best, but in the following example I used Ipopt).

I tried to formulate the problem like this:

x is a n by n matrix containing the price for shop_i and month_i for i, j = 1:n.

y is a n by n matrix containing binary elements as decision variables i.e. if shop_i launches in month_j for i,j = 1:n.

nr is a n by n matrix containing only integer elements and it’s used to calculate the average i.e. ensuring that we divide with the correct number.

Here is my code:

using JuMP
using Ipopt
using MathOptInterface
using Juniper

n = 3

optimizer = Juniper.Optimizer
nl_solver = optimizer_with_attributes(Ipopt.Optimizer, "print_level" => 0)

m = Model(optimizer_with_attributes(optimizer, "nl_solver"=>nl_solver))


@variable(m, x[i = 1:n, j = 1:n] >= 0)
@variable(m, y[i = 1:n, j = 1:n], Bin)
@variable(m, nr[i = 1:n, j = 1:n], Int)


start = [1,2,4]
pop = [20,15,10]


@objective(m, Max, sum(x[i,j]*y[i,j] * pop[j] for i =1:n, j = 1:n) )

#Launch one time per shop
for j = 1:n
    @constraint(m, sum(y[i,j] for i = 1:n) == 1 )
end
#Launch one time per month
for i = 1:n
    @constraint(m, sum(y[i,j] for j = 1:n) == 1 )
end

#Initial price
for i = 1:n
    @constraint(m, x[i,1]*y[i,1] <= start[i] )
end

#Constraining nr
for i = 1:n
    for j = 1:n
        @constraint(m, nr[i,j] >= 1 )
        @constraint(m, nr[i,j] <= n )
    end
end

#Calculating launch sequence
for j = 2:n
    @constraint(m, nr[1,j] >= sum(y[2,i] + y[3,i] for i = 1:j-1) )
    @NLconstraint(m, x[1,j] == sum(y[2,i]*x[2,i] + y[3,i]*x[3,i] for i = 1:j-1) / nr[1,j] )

    @constraint(m, nr[2,j] >= sum(y[3,i] for i = 1:j-1) )
    @NLconstraint(m, x[2,j] == sum(y[3,i]*x[3,i]  for i = 1:j-1) / nr[2,j] )

    @constraint(m, nr[3,j] >= sum(y[2,i] + y[1,i] for i = 1:j-1) )
    @NLconstraint(m, x[3,j] == sum(y[2,i]*x[2,i] + y[1,i]*x[1,i] for i = 1:j-1) / nr[3,j]  )
end



optimize!(m)
println(JuMP.value.(x))
println(JuMP.value.(y))
println(JuMP.value.(nr))
println(JuMP.objective_value(m))
println(JuMP.termination_status(m))

My code does not give any useful results, and I am stuck. Any suggestions?

Can you clarify what you mean by: “Does not give any useful results”?

Juniper only solves the problem locally and your problem seems to be non-convex.

My results are not a feasible solution to the problem, I get:
x = [100000.0 6.0 2.0; 1.78582e8 1.33333 4.0; 4.0 2.0 8.0]
y = [0.0 1.0 5.38607e-9; 1.11994e-8 0.0 1.0; 1.0 1.58657e-8 0.0]

Does Julia have any non-convex solvers and what kind of problems do they solve?

There are very few MINLP solvers, and Juniper happens to be very good. You’ve just picked a very hard problem.

I suggest you step back and reconsider the formulation.

For example, if x has bounds l and u, such that l <= x <= u, then you can replace x * y with a new variable z and constraints l * y <= z and z <= u * y.

You should also declare nr as

@variable(model, 1 <= nr[1:n, 1:n] <= n)

instead of adding the linear constraints.

If you do all of that, it should be representable as a mixed-integer linear program, which is “easy” to solve.

3 Likes

Thank you for a good answer. I just don’t see how it can be expressed as a MILP, since we still have to divide with nr, and variable-division is non-linear.
Also I tried to implement your approach with Juniper, but I’m producing NaN’s. Without Juniper and Ipopt I cannot make any non linear constraints, so I have not been able to implement the linear program that you mentioned.

using JuMP
using Ipopt
using GLPK
using MathOptInterface
using Juniper
using GLPKMathProgInterface
using Statistics
using Cbc

n = 3

optimizer = Juniper.Optimizer
nl_solver = optimizer_with_attributes(Ipopt.Optimizer, “print_level” => 0)

m = Model(optimizer_with_attributes(optimizer, “nl_solver”=>nl_solver))

@variable(m, x[i = 1:n, j = 1:n] >= 0)
@variable(m, y[i = 1:n, j = 1:n], Bin)
@variable(m, z[i = 1:n, j = 1:n] >= 0)
@variable(m, 1 <= nr[i = 1:n, j = 1:n] <= n, Int)

start = [8,7,6]
pop = [10,15,20]

l = 6 #min of start
u = 8 #max of start

@objective(m, Max, sum(z[i,j] * pop[j] for i =1:n, j = 1:n) )

for j = 1:n
@constraint(m, sum(y[i,j] for i = 1:n) == 1 )
end

for i = 1:n
@constraint(m, sum(y[i,j] for j = 1:n) == 1 )
end

for i = 1:n
for j = 1:n
@constraint(m, z[i,j] == x[i,j]*y[i,j])
end
end

#Initial price
for i = 1:n
@constraint(m, z[i,1] <= start[i] )
end

for i = 1:n
for j = 1:n
@constraint(m, l * y[i,j] <= z[i,j])
@constraint(m, z[i,j] <= u * y[i,j])
end
end

for j = 2:n
@constraint(m, nr[1,j] >= sum(y[2,i] + y[3,i] for i = 1:j-1) )
@NLconstraint(m, x[1,j] == sum(z[2,i] + z[3,i] for i = 1:j-1) / nr[1,j] )

@constraint(m, nr[2,j] >= sum(y[3,i] for i = 1:j-1) )
@NLconstraint(m, x[2,j] == sum(z[3,i]  for i = 1:j-1) / nr[2,j] )

@constraint(m, nr[3,j] >= sum(y[2,i] + y[1,i] for i = 1:j-1) )
@NLconstraint(m, x[3,j] == sum(z[2,i] + z[1,i] for i = 1:j-1) / nr[3,j]  )

end

optimize!(m)
println(JuMP.value.(x))
println(JuMP.value.(y))
println(JuMP.value.(nr))
println(JuMP.objective_value(m))
println(JuMP.termination_status(m))

What am I doing wrong?

Multiply both sides by nr to remove the division, then expand out nr to the sum of the binary variables y.

1 Like

I tried to follow your hint, but I keep getting NaNs and errors. What do you mean by expand out nr, when nr is defined as a sum of y just above?
The GLPK solver is supposed to support MIPs, but it refuses to deal with some of the constraints i.e. z = x * y and the constraints where I multiplied with nr to avoid division prompting that “constraints of type MathOptInterface.ScalarQuadraticFunction.EqualTo{Float64} are not supported by the solver”. Am I supposed to use GLPK or Ipopt/Juniper and what about nr? Thank you very much for your help.

using JuMP
using GLPK
using MathOptInterface
using GLPKMathProgInterface

n = 3

m = Model(optimizer_with_attributes(GLPK.Optimizer, “tm_lim” => 60000))

@variable(m, x[i = 1:n, j = 1:n] >= 0)
@variable(m, y[i = 1:n, j = 1:n], Bin)
@variable(m, z[i = 1:n, j = 1:n] >= 0)
@variable(m, 1 <= nr[i = 1:n, j = 1:n] <= n, Int)

start = [8,7,6]
pop = [10,15,20]

l = 6 #min of start
u = 8 #max of start

@objective(m, Max, sum(z[i,j] * pop[j] for i =1:n, j = 1:n) )

for j = 1:n

@constraint(m, sum(y[i,j] for i = 1:n) == 1 )

end

for i = 1:n

@constraint(m, sum(y[i,j] for j = 1:n) == 1 )

end

for i = 1:n
for j = 1:n

    @constraint(m, z[i,j] == x[i,j] * y[i,j] )
end

end

#Initial price
for i = 1:n

@constraint(m, z[i,1] <= start[i] )

end

for i = 1:n
for j = 1:n

    @constraint(m, l * y[i,j] <= z[i,j])
    @constraint(m, z[i,j] <= u * y[i,j])
end

end

for j = 2:n

@constraint(m, nr[1,j] >= sum(y[2,i] + y[3,i] for i = 1:j-1) )
@constraint(m, nr[1,j] * x[1,j] == sum(z[2,i] + z[3,i] for i = 1:j-1)  )

@constraint(m, nr[2,j] >= sum(y[3,i] for i = 1:j-1) )
@constraint(m, nr[2,j] * x[2,j] == sum(z[3,i]  for i = 1:j-1)  )

@constraint(m, nr[3,j] >= sum(y[2,i] + y[1,i] for i = 1:j-1) )
@constraint(m, nr[3,j] * x[3,j] == sum(z[2,i] + z[1,i] for i = 1:j-1)  )

end

optimize!(m)
println(JuMP.value.(x))
println(JuMP.value.(y))
println(JuMP.value.(nr))
println(JuMP.objective_value(m))
println(JuMP.termination_status(m))

  1. Remove the z = x * y constraint.
  2. nr[1,j] * x[1,j] is equivalent to x[1, j] * y[2, i] + x[1, j] * y[3, i] + ... you you can apply the same trick. For the inequality, if nr >=, then when it was on the denominator, increasing it acts to make the right-hand side smaller. Therefore, you can replace
@constraint(m, x[1,j] == sum(z[2,i] + z[3,i] for i = 1:j-1) / nr[1,j])

with something like

@constraint(m, x[1, j] * y[2, i] + x[1, j] * y[3, i] + ... >= sum(z[2,i] + z[3,i] for i = 1:j-1))

Alternatively, just use a solver like Gurobi.jl, and you can write x * y directly and it will do this reformulation for you.

Okay, I used the Gurobi solver and the code is running! Thank you a lot for your help, you really got me out of the rabbit hole. Do you by any chance know the complexity of the algorithm for the launch problem of n shops with the Gurobi solver? And it is possible to make changes that will minimize the run time? (I’m currently at 7 hours for n = 12 and it is still running, which worries me a bit since I figure that I would be done by now for n = 12 with a brute force approach.)

What’s your new model? MIP solve time can be very sensitive to formulation. Make sure you put good bounds on x.

For complexity, see: https://en.wikipedia.org/wiki/Integer_programming#Proof_of_NP-hardness

2 Likes

It looks like this:

using JuMP
using GLPK
using MathOptInterface
using GLPKMathProgInterface
using Gurobi

n = 12

env = Gurobi.Env()


m = Model(Gurobi.Optimizer)
set_optimizer_attribute(m, "NonConvex", 2)

@variable(m, x[i = 1:n, j = 1:n] >= 0)
@variable(m, y[i = 1:n, j = 1:n], Bin)
@variable(m, 1 <= nr[i = 1:n, j = 1:n] <= n, Int)


start = [18, 15, 17, 17, 20, 13, 15, 17, 17, 21, 18, 15]
pop = [100, 80, 130, 90, 1500, 1200, 200, 250, 800, 1000, 1100, 750]
growth = [0.2, 0.15, 0.22, 0.24, 0.12, 0.42, 0.1, 0.11, 0.14, 0.2, 0.05, 0.05]
mgrowth = zeros(n,n)

for i = 1:n
    for j = 1:n
        mgrowth[i,j] = (1 + growth[i])^(n-j)
    end
end

@objective(m, Max, sum(x[i,j]*y[i,j] * pop[j] * mgrowth[i,j] for i =1:n, j = 1:n) )

for j = 1:n
    @constraint(m, sum(y[i,j] for i = 1:n) == 1 )
end

for i = 1:n
    @constraint(m, sum(y[i,j] for j = 1:n) == 1 )
end

for i = 1:n
    @constraint(m, x[i,1]*y[i,1] <= start[i] )
end

for j = 2:n
    @constraint(m, nr[1,j] >= sum(y[2,i] + y[3,i] for i = 1:j-1) )
    @constraint(m, nr[1,j] * x[1,j] == sum(y[2,i]*x[2,i] + y[3,i]*x[3,i] for i = 1:j-1)  )

    @constraint(m, nr[2,j] >= sum(y[3,i] + y[1,i] + y[12,i] for i = 1:j-1) )
    @constraint(m, nr[2,j] * x[2,j] == sum(y[3,i]*x[3,i] + y[1,i]*x[1,i] + y[12,i]*x[12,i]  for i = 1:j-1) )

    @constraint(m, nr[3,j] >= sum(y[2,i] + y[1,i] + y[4,i] + y[5,i] for i = 1:j-1) )
    @constraint(m, nr[3,j] * x[3,j] == sum(y[2,i]*x[2,i] + y[1,i]*x[1,i] + y[4,i]*x[4,i] + y[5,i]*x[5,i] for i = 1:j-1)  )

    @constraint(m, nr[4,j] >= sum(y[1,i] + y[2,i] + y[3,i] for i = 1:j-1) )
    @constraint(m, nr[4,j] * x[4,j] == sum(y[1,i]*x[1,i] + y[2,i]*x[2,i] + y[3,i]*x[3,i]  for i = 1:j-1) )

    @constraint(m, nr[5,j] >= sum(y[1,i] + y[2,i] + y[3,i] + y[4,i] + y[10,i] + y[11,i] + y[12,i] for i = 1:j-1) )
    @constraint(m, nr[5,j] * x[5,j] == sum(y[1,i]*x[1,i] + y[2,i]*x[2,i] + y[3,i]*x[3,i] + y[4,i]*x[4,i]
     + y[10,i]*x[10,i] + y[11,i]*x[11,i] + y[12,i]*x[12,i] for i = 1:j-1)  )

    @constraint(m, nr[6,j] >= sum(y[2,i] + y[12,i] for i = 1:j-1) )
    @constraint(m, nr[6,j] * x[6,j] == sum(y[2,i]*x[2,i] + y[12,i]*x[12,i] for i = 1:j-1)  )

    @constraint(m, nr[7,j] >= sum(y[8,i] for i = 1:j-1) )
    @constraint(m, nr[7,j] * x[7,j] == sum(y[8,i]*x[8,i] for i = 1:j-1)  )

    @constraint(m, nr[8,j] >= sum(y[7,i] for i = 1:j-1) )
    @constraint(m, nr[8,j] * x[8,j] == sum(y[7,i]*x[7,i] for i = 1:j-1)  )

    @constraint(m, nr[9,j] >= sum(y[10,i] + y[11,i] + y[12,i] for i = 1:j-1) )
    @constraint(m, nr[9,j] * x[9,j] == sum(y[10,i]*x[10,i] + y[11,i]*x[11,i] + y[12,i]*x[12,i]  for i = 1:j-1) )

    @constraint(m, nr[10,j] >= sum(y[9,i] + y[11,i] for i = 1:j-1) )
    @constraint(m, nr[10,j] * x[10,j] == sum(y[9,i]*x[9,i] + y[11,i]*x[11,i] for i = 1:j-1)  )

    @constraint(m, nr[11,j] >= sum(y[7,i] + y[8,i] + y[9,i] + y[10,i] + y[12,i] for i = 1:j-1) )
    @constraint(m, nr[11,j] * x[11,j] == sum(y[7,i]*x[7,i] + y[8,i]*x[8,i] + y[9,i]*x[9,i] + y[10,i]*x[10,i] + y[12,i]*x[12,i]  for i = 1:j-1) )

    @constraint(m, nr[12,j] >= sum(y[1,i] + y[2,i] + y[3,i] + y[4,i] + y[5,i] + y[6,i] + y[7,i] + y[8,i] + y[9,i] for i = 1:j-1) )
    @constraint(m, nr[12,j] * x[12,j] == sum(y[1,i]*x[1,i] + y[2,i]*x[2,i] + y[3,i]*x[3,i] + y[4,i]*x[4,i]
     + y[5,i]*x[5,i] + y[6,i]*x[6,i] + y[7,i]*x[7,i] + y[8,i]*x[8,i] + y[9,i]*x[9,i] for i = 1:j-1)  )
end

optimize!(m)
println(JuMP.value.(x))
println(JuMP.value.(y))
println(JuMP.value.(nr))
println(JuMP.objective_value(m))
println(JuMP.termination_status(m))

As you can see, I added a mgrowth to the objective which is a shop-specific monthly growth in the customer size.

Can I do anything to make the code run more efficient, so that I can obtain the results?

You probably still need to do the same trick of expanding out the nr into a sum of y terms, so that you only have x * y, not nr * x. The reformulation only works if one of the terms is binary.

The other thing you should do is add good initial bounds on x. For example, 13 <= x <= 21.

1 Like

You can use: https://github.com/joaquimg/QuadraticToBinary.jl if you have (good) bounds on all variables that appear in products. It will perform automatic binary expansion for all products.
However, it might lead to a hard MIP problem. Also the resulting problem is a relaxation, and as you increase the precision (the package allows that) the problem get much more difficult to solve.

1 Like

I rewrote the code with good bounds on all variables and with expansion of nr; it is fast now, and I’m thankful for your help.