Assignnemt problem - Help to write simple constraint
53 views
Skip to first unread message
Stéphane VIGNERON
Jun 24, 2023, 8:07:01 PM6/24/23
to AMPL Modeling Language
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
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
AMPL Google Group
Jun 24, 2023, 8:53:02 PM6/24/23
to AMPL Modeling Language
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.
(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.
--
Robert Fourer
We're switching to a new, enhanced user forum.
Join it now at discuss.ampl.com.
Stéphane VIGNERON
Jun 25, 2023, 9:34:10 AM6/25/23
to am...@googlegroups.com
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
--
You received this message because you are subscribed to a topic in the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/ampl/_SmoFiFkAn8/unsubscribe.
To unsubscribe from this group and all its topics, send an email to ampl+uns...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/ampl/reply-77152-2283323733-6820987484-1687654377-89483479%40helpscout.net.
Stephane VIGNERON
AMPL Google Group
Jun 26, 2023, 4:57:25 PM6/26/23
to AMPL Modeling Language
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?
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?
{#HS:2283323733-117954#}
On Sun, Jun 25, 2023 at 1:34 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:
Hello,
That's why I've added the 1 to be sure that the model use the minimum of cart if cart cost is the same. I guess i need a condition that say total of order assigned must be equal to total order.
Thabks again
On Sun, Jun 25, 2023 at 12:52 AM UTC, AMPL Google Group <am...@googlegroups.com> wrote:
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.
--
Robert Fourer
We're switching to a new, enhanced user forum.
Join it now at discuss.ampl.com.
developpeur developpeur
Jun 27, 2023, 10:50:04 AM6/27/23
to am...@googlegroups.com
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:"
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);
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
Stéphane
--
You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ampl+uns...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/ampl/reply-77152-2283323733-6825488745-1687813040-721324113%40helpscout.net.
AMPL Google Group
Jun 27, 2023, 6:32:47 PM6/27/23
to AMPL Modeling Language
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:
But here is what I see when I run the current version (1.5.1):
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.
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.
{#HS:2283323733-117954#}
On Tue, Jun 27, 2023 at 2:50 PM UTC, AMPL Modeling Language <am...@googlegroups.com> wrote:
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
Le lun. 26 juin 2023 à 22:57, AMPL Google Group <am...@googlegroups.com> a écrit :
On Mon, Jun 26, 2023 at 8:57 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:
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?
--
Robert Fourer
We're switching to a new, enhanced user forum.
Join it now at discuss.ampl.com.
Reply all
Reply to author
Forward
0 new messages