Assignnemt problem - Help to write simple constraint - AMPL

Question

I am currently writing a simple bin packing problem using an AMPL model. The idea is to have orders and carts and minimize the total cost. Each order must be assigned to a cart, and a cart can have more than 20 orders. The objective is to determine which order should be assigned to which cart. I have written the following code, but my modelis not working correctly. When I change Max_Carts, the Total_Cost increases. It seems like model is forcing the carts to have at least one order.

I would like the constraint to ensure that each order is assigned to a cart, but not that each cart must have an order. It is possible for a cart to have zero orders.

Can you help me ?

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

Answer 1

The objective minimize Total_Cost: sum {c in 1..Max_Carts} (Cart_Cost[c] + 1); is equivalent to:

minimize Total_Cost: sum {c in 1..Max_Carts} Cart_Cost[c] + sum {c in 1..Max_Carts} 1;

which is the same as:

minimize Total_Cost: sum {c in 1..Max_Carts} Cart_Cost[c] + Max_Carts;

So, by increasing Max_Carts you are increasing the objective by the same amount even if the additional carts are not used.

If you want to consider a minimum cost of 1 per cart used and you are using an MP-based driver for AMPL (e.g., Gurobi, CPLEX, Xpress, COPT, HiGHS, CBC, etc.) you can do the following:

minimize Total_Cost: sum {c in 1..Max_Carts} (if Cart_Cost[c] > 0 then Cart_Cost[c]+1);