[AMPL 24698] Assignnemt problem - Help to write simple constraint

Google Group Mirror
1

HI,

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 c

2

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.

3

Hello,

That’s why I’ve added the 1 to be sure that the model use thé minimum of cart if cart cost is thé same.
I guess i need à condition that say total of order assigned must be équal to total order.

Thabks again

4

Adding a constant to the objective does not cause any change to the optimal values of the variables. The only change is that the optimal value of the objective is increased by the value of the constant. Thus you will get the same results by dropping the constant and just minimizing the total cost:

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

But you can put an order, o, in any cart, and it will have the same cost, Cost[o]. Thus the total cost will always be sum {o in ORDERS} Cost[o], and it will not matter which cart you put each order in – as long as you have enough carts to fit all the orders.

So this seems to be a trivial problem: to get the number of carts needed, divide Max_Order_Per_Cart by the total number of orders, and round up to the next highest integer. Or is there some other complication that makes the problem harder?

5

Hi,

Thanks for your answer, in fact the problem can be solve with the model below.
But i have an error “The redefinition of an indicator constraint “bin_var==0/1 ==> c’x<=d” into a big-M constraint failed due to the absence of a finite upper bound on c’x. If the solver supports indicator constraints, it will be passed to the solver, otherwise this is a fatal error. To remove this error/warning, the following options can be available:”

How can I deal with it ?
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 = 2;

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)
var Cart_Has_Assign{c in 1…Max_Carts} binary; # Variable binaire pour indiquer si un chariot a des commandes assignées

minimize Total_Cost: sum {c in 1…Max_Carts} (Cart_Cost[c] + if Cart_Cost[c] > 0 then 1 else 0); # Minimisation du coût total

subject to Total_Orders_Constraint:
sum {o in ORDERS, c in 1…Max_Carts} Assign[o, c] = card(ORDERS);

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

Regards,
Stéphane

6

That message appeared when using some older versions of solvers. As an example, it is seen when using an older version (1.4.0) of HiGHS:

ampl: option solver highs;
ampl: solve;
HiGHS 1.4.0: Error: The redefinition of an indicator constraint "bin_var==0/1 ==> c'x<=d" into a big-M constraint failed due to the absence of a finite upper bound on c'x. If the solver supports indicator constraints, it will be passed to the solver, otherwise this is a fatal error. To remove this error/warning, the following options can be available:
1. Provide tight bounds on variables entering logical expressions;
2. Use option cvt:mip:bigM to set the default value of big-M (use with care);
3. If available, set acc:indle=2 for native handling of the constraint.
exit value 18446744073709551615
<BREAK>

But here is what I see when I run the current version (1.5.1):

ampl: solve;
HiGHS 1.5.1: Set bounds on variables
participating in logical expressions,
or use option cvt:bigM (with caution).
See more: https://amplmp.readthedocs.io/en/latest/rst/modeling-numerics.html

The “logical expression” in your model is an if-then-else expression, “if Cart_Cost[c] > 0 then 1 else 0”. So the solver is asking you to set bounds on the variable Cart_Cost[c] that appears in that expression. You already have a lower bound of 0, but you need to give an upper bound. For example, you would expect that in any optimal solution, Cart_Cost[c] would not be greater than the total cost of all orders, so you could write

var Cart_Cost{c in 1..Max_Carts} >= 0, <= sum {o in ORDERS} Cost[o];

With that change, HiGHS gives me an optimal solution (using some random data for testing):

ampl: solve;
HiGHS 1.5.1: optimal solution; objective 205.7502378
3 simplex iterations
1 branching nodes

(When the upper bounds are added, the older version can find the solution, too.) You should get similar results with other solvers, but if you have any trouble with the solver you are using, post all of the output from the solver here.