Issue on simple problem of kind of bin Packing

Support
1

Hi,

I’ve created a simple model to solve this simple picking problem :
We have orders to pick in aisles, each order have a cost (Distance to pick in Items)
We have cart where we can put oders, when I travel i can get orders one by one, so the cost of cart is the distance of the max order distance.
I have written this simple model :

set ORDERS;            # Ensemble des commandes

param Cost{ORDERS};  # Coût de chaque commande
param Max_Order_Per_Cart = 20;  # Nombre maximal de commandes par chariot
param Max_Carts = 30; 

var Assign{ORDERS, c in 1..Max_Carts} binary;  # Variable de décision : affectation d'une commande à un chariot (binaire)
var Cart_Cost{c in 1..Max_Carts} >= 0;  # Coût de chaque chariot (positif ou nul)


minimize Total_Cost: sum {c in 1..Max_Carts} (Cart_Cost[c] + 1);  # Minimisation du coût total

subject to Cart_Assignment{o in ORDERS}:
    sum {c in 1..Max_Carts} Assign[o, c] = 1;  # Contrainte : chaque commande est assignée à au plus un chariot
    
subject to Max_Order_Per_Cart_Constraint{c in 1..Max_Carts}:
    sum {o in ORDERS} Assign[o, c] <= Max_Order_Per_Cart;  # Contrainte : nombre maximal de commandes par chariot
        
subject to Cart_Cost_Constraint2{c in 1..Max_Carts}:
    Cart_Cost[c] >= sum {o in ORDERS} Cost[o] * Assign[o, c];  # Contrainte : le coût du chariot est supérieur ou égal au coût de la commande la plus chère

BUT :
if i execute with a simple list of orders (see attached), it’s allocated only 2 orders per cart … But the best way is to optimize the maximum orders in one cart.
Can you help me ?
And how to remove the max_carts value i want that model
cart.zip (748.1 KB)

2

Please, need help to solve this problem

3

Your .run file does not set any solver for your problem. This can cause MINOS to be used as the default solver, but MINOS cannot enforce integrality of the variables. Be sure that you are giving a command like option solver gurobi; to select a solver that recognizes integrality of variables. Solvers like this that you may have installed include gurobi, xpress, cplex, copt, highs, mosek, and cbc.

If you are getting an optimal solution that does have binary values for all the Assign variables, and you do not like it, then can you explain more exactly what is wrong with the solution? For example, do you know another feasible solution that has a better objective value? Or are your variables not satisfying some restriction that is required by your application?

I realize that your said “the best way is to optimize the maximum orders in one cart” and “how to remove the max_carts value i want” but I am not sure what you mean by these statements.

4

Hi,

Thanks for your answer, I found that my model is not doing what I want but I don’t know how to write constraint. In the code below, the model force each cart to have at least one order instead of just assign each order to one cart. That’s why the result is different when I change Max_Carts.

Can you help me to change the model ?

set ORDERS;            # Ensemble des commandes

param Cost{ORDERS};  # Coût de chaque commande
param Max_Order_Per_Cart = 20;  # Nombre maximal de commandes par chariot
param Max_Carts = 10; 

var Assign{ORDERS, c in 1..Max_Carts} binary;  # Variable de décision : affectation d'une commande à un chariot (binaire)
var Cart_Cost{c in 1..Max_Carts} >= 0;  # Coût de chaque chariot (positif ou nul)

minimize Total_Cost: sum {c in 1..Max_Carts} (Cart_Cost[c] + 1);  # Minimisation du coût total

subject to Cart_Assignment{o in ORDERS}:
    sum {c in 1..Max_Carts} Assign[o, c] = 1;  # Contrainte : chaque commande est assignée à au plus un chariot
    
subject to Max_Order_Per_Cart_Constraint{c in 1..Max_Carts}:
    sum {o in ORDERS} Assign[o, c] <= Max_Order_Per_Cart;  # Contrainte : nombre maximal de commandes> par chariot
        
subject to Cart_Cost_Constraint2{c in 1..Max_Carts}:
    Cart_Cost[c] >= sum {o in ORDERS} Cost[o] * Assign[o, c];  # Contrainte : le coût du chariot est supérieur ou égal au coût de la commande la plus chère
5

You have defined your objective function Total_Cost as

sum {c in 1..Max_Carts} (Cart_Cost[c] + 1)

That is equivalent to

(sum {c in 1..Max_Carts} Cart_Cost[c]) + (sum {c in 1..Max_Carts} 1)

which is equivalent to

(sum {c in 1..Max_Carts} Cart_Cost[c]) + Max_Carts

So, imagine that you increase Max_Carts by 1. If the value of “sum {c in 1…Max_Carts} Cart_Cost[c]” in the optimal solution does not change, then the value of the objective will increase by 1 due to the “+ Max_Carts” term.