(3, 1) : 0 : 0.0 : None : False : False : NonNegativeIntegers (2, 3) : 0 : 4.0 : None : False : False : NonNegativeIntegers (2, 2) : 0 : 8.0 : None : False : False : NonNegativeIntegers (2, 1) : 0 : 8.0 : None : False : False : NonNegativeIntegers (1, 3) : 0 : 0.0 : None : False : False : NonNegativeIntegers (1, 2) : 0 : 0.0 : None : False : False : NonNegativeIntegers (1, 1) : 0 : 0.0 : None : False : False : NonNegativeIntegers Key : Lower : Value : Upper : Fixed : Stale : Domain Mdl.c3 = pyo.Constraint(mdl.prohibited, rule=limit_prohib) Mdl.c2 = pyo.Constraint(mdl.invs, rule=use_all) Return sum(mdl.X for b in mdl.bins) = mdl.X_used*mdl.weight Mdl.c1 = pyo.Constraint(mdl.bins, rule=bin_limit) Return sum(mdl.X for i in mdl.invs) <= mdl.bin_cap Mdl.OBJ = pyo.Objective(expr=sum(mdl.X*mdl.value for Mdl.X_used = pyo.Var(mdl.invs, domain=pyo.Binary) Mdl.X = pyo.Var(mdl.invs, mdl.bins, domain=pyo.NonNegativeIntegers) # the amount from invoice i in bin j Mdl.bin_cap = pyo.Param(mdl.bins, initialize= bins) I think OR-Tools is pretty similar in structure. Below is an example that I think fits the design pattern. This is not too big of a leap from the basic Knapsack problem and can be handled with only 3 constraints for the bin size, all-or-nothing, and the prohibited placements. This is a not homework, my items are actually invoices that I am trying to assign to investment bins. I am using OR-Tools to explore this problem, but so far I haven't had any luck implementing this variation. Is possible to solve with the solvers from OR-Tools? It looks similar to the knapsack problem to me but does this variation have a name? If I knew the proper name for this problem I could search for solutions for it. My questions are: Is this a known problem? Note: all numbers are integers.Įven if the item can be divided, I must also make sure that all parts of the item weight are assigned to bins. The item can be divided, an item with 100 could be divided into two so that it fits two bins of 50. Item x can only be added to the bins A and B. Some bins might not accept some items, e.g.: I have item x and bins A, B, and C. Like the classical multiple knapsacks problem, I have a set of items, each one with a weight and a value and I am trying to divide them into multiple bins and find the combination with the best value.īut unlike the classical, I also need the following: I am trying to solve a problem that I believe is a variation of the multiple knapsacks.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |