Closed joseph1125 closed 8 years ago
bchevalier
commented
8 years ago Yes, it should be possible. Considering the problem is NP-Hard it might take some time to solve though.
If you can detail your exact problem or give us the formulation we might be able to help you solve it with the jsLPSolver.
joseph1125
commented
8 years ago I have to buy p Products from v Vendors. Each Vendors have all of these Products, but they sell different Price.
And, the problem is: Find the best way to buy p Product from limit x Vendors ( There are v Vendors , x<=v).
joseph1125
commented
8 years ago minimize c(i, j) y(i, j) # cost of all of the orders subject to for all i: sum over j of y(i, j) = 1 # buy each product once for all i, j: y(i, j) <= z(j) # buy products only from chosen vendors sum over j of z(j) <= x # choose at most x vendors for all i, j: 0 <= y(i, j) <= 1 for all j: z(j) in {0, 1} The interpretation of the variables is that i is a product, j is a vendor, c(i, j) is the cost of product i from vendor j, y(i, j) is 1 if we buy product i from vendor j and 0 otherwise, z(j) is 1 is we buy from vendor j at all and 0 otherwise.
bchevalier
commented
8 years ago When it comes to using jsLPSolver you have 2 possible ways to create your model. The most popular way is using a JSON or JavaScript object. I made a small instance of your problem, with 5 products and 5 vendors (prices generated randomly) and 2 max vendors. The formulation is quite big for such a small problem:
{
"name": "Vendor Selection",
"optimize": "cost",
"opType": "min",
"constraints": {
"exactlyOne_0": {
"equal": 1
},
"exactlyOne_1": {
"equal": 1
},
"exactlyOne_2": {
"equal": 1
},
"exactlyOne_3": {
"equal": 1
},
"exactlyOne_4": {
"equal": 1
},
"vendorSelection_0_0": {
"max": 0
},
"vendorSelection_0_1": {
"max": 0
},
"vendorSelection_0_2": {
"max": 0
},
"vendorSelection_0_3": {
"max": 0
},
"vendorSelection_0_4": {
"max": 0
},
"vendorSelection_1_0": {
"max": 0
},
"vendorSelection_1_1": {
"max": 0
},
"vendorSelection_1_2": {
"max": 0
},
"vendorSelection_1_3": {
"max": 0
},
"vendorSelection_1_4": {
"max": 0
},
"vendorSelection_2_0": {
"max": 0
},
"vendorSelection_2_1": {
"max": 0
},
"vendorSelection_2_2": {
"max": 0
},
"vendorSelection_2_3": {
"max": 0
},
"vendorSelection_2_4": {
"max": 0
},
"vendorSelection_3_0": {
"max": 0
},
"vendorSelection_3_1": {
"max": 0
},
"vendorSelection_3_2": {
"max": 0
},
"vendorSelection_3_3": {
"max": 0
},
"vendorSelection_3_4": {
"max": 0
},
"vendorSelection_4_0": {
"max": 0
},
"vendorSelection_4_1": {
"max": 0
},
"vendorSelection_4_2": {
"max": 0
},
"vendorSelection_4_3": {
"max": 0
},
"vendorSelection_4_4": {
"max": 0
},
"maxSelectedVendors": {
"max": 2
}
},
"variables": {
"y_0_0": {
"cost": 4,
"exactlyOne_0": 1,
"vendorSelection_0_0": 1
},
"y_0_1": {
"cost": 4,
"exactlyOne_0": 1,
"vendorSelection_1_0": 1
},
"y_0_2": {
"cost": 4,
"exactlyOne_0": 1,
"vendorSelection_2_0": 1
},
"y_0_3": {
"cost": 4,
"exactlyOne_0": 1,
"vendorSelection_3_0": 1
},
"y_0_4": {
"cost": 4,
"exactlyOne_0": 1,
"vendorSelection_4_0": 1
},
"y_1_0": {
"cost": 93,
"exactlyOne_1": 1,
"vendorSelection_0_1": 1
},
"y_1_1": {
"cost": 85,
"exactlyOne_1": 1,
"vendorSelection_1_1": 1
},
"y_1_2": {
"cost": 83,
"exactlyOne_1": 1,
"vendorSelection_2_1": 1
},
"y_1_3": {
"cost": 97,
"exactlyOne_1": 1,
"vendorSelection_3_1": 1
},
"y_1_4": {
"cost": 92,
"exactlyOne_1": 1,
"vendorSelection_4_1": 1
},
"y_2_0": {
"cost": 16,
"exactlyOne_2": 1,
"vendorSelection_0_2": 1
},
"y_2_1": {
"cost": 16,
"exactlyOne_2": 1,
"vendorSelection_1_2": 1
},
"y_2_2": {
"cost": 18,
"exactlyOne_2": 1,
"vendorSelection_2_2": 1
},
"y_2_3": {
"cost": 17,
"exactlyOne_2": 1,
"vendorSelection_3_2": 1
},
"y_2_4": {
"cost": 17,
"exactlyOne_2": 1,
"vendorSelection_4_2": 1
},
"y_3_0": {
"cost": 25,
"exactlyOne_3": 1,
"vendorSelection_0_3": 1
},
"y_3_1": {
"cost": 21,
"exactlyOne_3": 1,
"vendorSelection_1_3": 1
},
"y_3_2": {
"cost": 22,
"exactlyOne_3": 1,
"vendorSelection_2_3": 1
},
"y_3_3": {
"cost": 21,
"exactlyOne_3": 1,
"vendorSelection_3_3": 1
},
"y_3_4": {
"cost": 21,
"exactlyOne_3": 1,
"vendorSelection_4_3": 1
},
"y_4_0": {
"cost": 38,
"exactlyOne_4": 1,
"vendorSelection_0_4": 1
},
"y_4_1": {
"cost": 40,
"exactlyOne_4": 1,
"vendorSelection_1_4": 1
},
"y_4_2": {
"cost": 44,
"exactlyOne_4": 1,
"vendorSelection_2_4": 1
},
"y_4_3": {
"cost": 41,
"exactlyOne_4": 1,
"vendorSelection_3_4": 1
},
"y_4_4": {
"cost": 38,
"exactlyOne_4": 1,
"vendorSelection_4_4": 1
},
"z_0": {
"vendorSelection_0_0": -1,
"vendorSelection_0_1": -1,
"vendorSelection_0_2": -1,
"vendorSelection_0_3": -1,
"vendorSelection_0_4": -1,
"maxSelectedVendors": 1
},
"z_1": {
"vendorSelection_1_0": -1,
"vendorSelection_1_1": -1,
"vendorSelection_1_2": -1,
"vendorSelection_1_3": -1,
"vendorSelection_1_4": -1,
"maxSelectedVendors": 1
},
"z_2": {
"vendorSelection_2_0": -1,
"vendorSelection_2_1": -1,
"vendorSelection_2_2": -1,
"vendorSelection_2_3": -1,
"vendorSelection_2_4": -1,
"maxSelectedVendors": 1
},
"z_3": {
"vendorSelection_3_0": -1,
"vendorSelection_3_1": -1,
"vendorSelection_3_2": -1,
"vendorSelection_3_3": -1,
"vendorSelection_3_4": -1,
"maxSelectedVendors": 1
},
"z_4": {
"vendorSelection_4_0": -1,
"vendorSelection_4_1": -1,
"vendorSelection_4_2": -1,
"vendorSelection_4_3": -1,
"vendorSelection_4_4": -1,
"maxSelectedVendors": 1
}
},
"binaries": {
"y_0_0": 1,
"y_0_1": 1,
"y_0_2": 1,
"y_0_3": 1,
"y_0_4": 1,
"y_1_0": 1,
"y_1_1": 1,
"y_1_2": 1,
"y_1_3": 1,
"y_1_4": 1,
"y_2_0": 1,
"y_2_1": 1,
"y_2_2": 1,
"y_2_3": 1,
"y_2_4": 1,
"y_3_0": 1,
"y_3_1": 1,
"y_3_2": 1,
"y_3_3": 1,
"y_3_4": 1,
"y_4_0": 1,
"y_4_1": 1,
"y_4_2": 1,
"y_4_3": 1,
"y_4_4": 1,
"z_0": 1,
"z_1": 1,
"z_2": 1,
"z_3": 1,
"z_4": 1
}
}This small model gets solved by jsLPSolver in 15ms on my machine. It returns the following result:
{ constraints: 6,
variables: 30,
evaluation: 163,
time: 0.015815038,
iter: 1,
solutionSet:
{
y_1_2: 1,
y_4_4: 1,
y_0_2: 1,
z_2: 1,
y_2_4: 1,
y_3_4: 1,
z_4: 1},
feasible: true }I also solved a bigger instance with 30 vendors and 30 products (it translates into 900 constraints and as many variables) in 1.3secs. But if I try to go higher the solver has some memory issues I think. How big would your problem be in terms of vendors and products?
joseph1125
commented
8 years ago In fact, 30 vendors and 30 products is more than I required, and the performance is already better than my existing solution, thanks a lot
bchevalier
commented
8 years ago Actually, I did not pay enough attention to the model. The y variables do not need to be binary variables. The binaries property should only include the z variables, as follow:
"binaries": {
"z_0": 1,
"z_1": 1,
"z_2": 1,
"z_3": 1,
"z_4": 1
}This way it should be even faster to solve (I could go up to 50 vendors and 50 products in 14secs). But you have to know that sometime an instance could take exceptionally longer or shorter than usual to solve due to the NP-Hardness of the problem.
joseph1125
commented
8 years ago understood, many thanks! But does it mean that the y should be in the variables section, can you show the final json to me?
bchevalier
commented
8 years ago All the variables should be in the variable section (continuous, integer and binary variables). The final version is the following:
{
"name": "Vendor Selection",
"optimize": "cost",
"opType": "min",
"constraints": {
"exactlyOne_0": {
"equal": 1
},
"exactlyOne_1": {
"equal": 1
},
"exactlyOne_2": {
"equal": 1
},
"exactlyOne_3": {
"equal": 1
},
"exactlyOne_4": {
"equal": 1
},
"vendorSelection_0_0": {
"max": 0
},
"vendorSelection_0_1": {
"max": 0
},
"vendorSelection_0_2": {
"max": 0
},
"vendorSelection_0_3": {
"max": 0
},
"vendorSelection_0_4": {
"max": 0
},
"vendorSelection_1_0": {
"max": 0
},
"vendorSelection_1_1": {
"max": 0
},
"vendorSelection_1_2": {
"max": 0
},
"vendorSelection_1_3": {
"max": 0
},
"vendorSelection_1_4": {
"max": 0
},
"vendorSelection_2_0": {
"max": 0
},
"vendorSelection_2_1": {
"max": 0
},
"vendorSelection_2_2": {
"max": 0
},
"vendorSelection_2_3": {
"max": 0
},
"vendorSelection_2_4": {
"max": 0
},
"vendorSelection_3_0": {
"max": 0
},
"vendorSelection_3_1": {
"max": 0
},
"vendorSelection_3_2": {
"max": 0
},
"vendorSelection_3_3": {
"max": 0
},
"vendorSelection_3_4": {
"max": 0
},
"vendorSelection_4_0": {
"max": 0
},
"vendorSelection_4_1": {
"max": 0
},
"vendorSelection_4_2": {
"max": 0
},
"vendorSelection_4_3": {
"max": 0
},
"vendorSelection_4_4": {
"max": 0
},
"maxSelectedVendors": {
"max": 2
}
},
"variables": {
"y_0_0": {
"cost": 4,
"exactlyOne_0": 1,
"vendorSelection_0_0": 1
},
"y_0_1": {
"cost": 4,
"exactlyOne_0": 1,
"vendorSelection_1_0": 1
},
"y_0_2": {
"cost": 4,
"exactlyOne_0": 1,
"vendorSelection_2_0": 1
},
"y_0_3": {
"cost": 4,
"exactlyOne_0": 1,
"vendorSelection_3_0": 1
},
"y_0_4": {
"cost": 4,
"exactlyOne_0": 1,
"vendorSelection_4_0": 1
},
"y_1_0": {
"cost": 93,
"exactlyOne_1": 1,
"vendorSelection_0_1": 1
},
"y_1_1": {
"cost": 85,
"exactlyOne_1": 1,
"vendorSelection_1_1": 1
},
"y_1_2": {
"cost": 83,
"exactlyOne_1": 1,
"vendorSelection_2_1": 1
},
"y_1_3": {
"cost": 97,
"exactlyOne_1": 1,
"vendorSelection_3_1": 1
},
"y_1_4": {
"cost": 92,
"exactlyOne_1": 1,
"vendorSelection_4_1": 1
},
"y_2_0": {
"cost": 16,
"exactlyOne_2": 1,
"vendorSelection_0_2": 1
},
"y_2_1": {
"cost": 16,
"exactlyOne_2": 1,
"vendorSelection_1_2": 1
},
"y_2_2": {
"cost": 18,
"exactlyOne_2": 1,
"vendorSelection_2_2": 1
},
"y_2_3": {
"cost": 17,
"exactlyOne_2": 1,
"vendorSelection_3_2": 1
},
"y_2_4": {
"cost": 17,
"exactlyOne_2": 1,
"vendorSelection_4_2": 1
},
"y_3_0": {
"cost": 25,
"exactlyOne_3": 1,
"vendorSelection_0_3": 1
},
"y_3_1": {
"cost": 21,
"exactlyOne_3": 1,
"vendorSelection_1_3": 1
},
"y_3_2": {
"cost": 22,
"exactlyOne_3": 1,
"vendorSelection_2_3": 1
},
"y_3_3": {
"cost": 21,
"exactlyOne_3": 1,
"vendorSelection_3_3": 1
},
"y_3_4": {
"cost": 21,
"exactlyOne_3": 1,
"vendorSelection_4_3": 1
},
"y_4_0": {
"cost": 38,
"exactlyOne_4": 1,
"vendorSelection_0_4": 1
},
"y_4_1": {
"cost": 40,
"exactlyOne_4": 1,
"vendorSelection_1_4": 1
},
"y_4_2": {
"cost": 44,
"exactlyOne_4": 1,
"vendorSelection_2_4": 1
},
"y_4_3": {
"cost": 41,
"exactlyOne_4": 1,
"vendorSelection_3_4": 1
},
"y_4_4": {
"cost": 38,
"exactlyOne_4": 1,
"vendorSelection_4_4": 1
},
"z_0": {
"vendorSelection_0_0": -1,
"vendorSelection_0_1": -1,
"vendorSelection_0_2": -1,
"vendorSelection_0_3": -1,
"vendorSelection_0_4": -1,
"maxSelectedVendors": 1
},
"z_1": {
"vendorSelection_1_0": -1,
"vendorSelection_1_1": -1,
"vendorSelection_1_2": -1,
"vendorSelection_1_3": -1,
"vendorSelection_1_4": -1,
"maxSelectedVendors": 1
},
"z_2": {
"vendorSelection_2_0": -1,
"vendorSelection_2_1": -1,
"vendorSelection_2_2": -1,
"vendorSelection_2_3": -1,
"vendorSelection_2_4": -1,
"maxSelectedVendors": 1
},
"z_3": {
"vendorSelection_3_0": -1,
"vendorSelection_3_1": -1,
"vendorSelection_3_2": -1,
"vendorSelection_3_3": -1,
"vendorSelection_3_4": -1,
"maxSelectedVendors": 1
},
"z_4": {
"vendorSelection_4_0": -1,
"vendorSelection_4_1": -1,
"vendorSelection_4_2": -1,
"vendorSelection_4_3": -1,
"vendorSelection_4_4": -1,
"maxSelectedVendors": 1
}
},
"binaries": {
"z_0": 1,
"z_1": 1,
"z_2": 1,
"z_3": 1,
"z_4": 1
}
}I also made a bigger instance (40 vendors and 40 products) that you can find in this PR by clicking on the View button.
joseph1125
commented
8 years ago Thank you, 4_0 means productId = 4 and shopId = 0, right?
bchevalier
commented
8 years ago Ah, the indexes might be confusing. vendorSelection_ 4_0 is for shopId 4, productId 0 but y_4_0 is for productId 4 shopId 0.
joseph1125
commented
8 years ago z_4 means shopId 4?
bchevalier
commented
8 years ago yes
bchevalier
commented
8 years ago If you look at the solution:
{
y_1_2: 1,
y_4_4: 1,
y_0_2: 1,
z_2: 1,
y_2_4: 1,
y_3_4: 1,
z_4:
}Products are being bought from shops 2 and 4. Products 0 and 1 are bought from shop 2 and products 2, 3 and 4 are being bought from shop 4.
joseph1125
commented
8 years ago understood, thanks
joseph1125
commented
8 years ago Sorry to bother you, I wrote a page that read the matrix (x-axis is products and y-axis is shops) and transform it into a object that you show here. However, the result that I receive is wrong, as the best cost is 23 while the solver gives me 28.
Folder https://drive.google.com/folderview?id=0B4sd8MQwTpVncUlLeUYtX2djQjg&usp=sharing Path /test/test.html
Test data 9 5 11 6 7 4 13 5 8 5 7 8
Make sure the numbers in test data is separated by tab, thanks.
bchevalier
commented
8 years ago I think I know the issue. You have specified a maximum of 3 vendors. But the weight of each shop is 3 in this constraint:
"z_0": {
"maxSelectedVendors": 3,
"vendorSelection_0_0": -1,
"vendorSelection_0_1": -1,
"vendorSelection_0_2": -1,
"vendorSelection_0_3": -1
},
"z_1": {
"maxSelectedVendors": 3,
"vendorSelection_1_0": -1,
"vendorSelection_1_1": -1,
"vendorSelection_1_2": -1,
"vendorSelection_1_3": -1
},
"z_2": {
"maxSelectedVendors": 3,
"vendorSelection_2_0": -1,
"vendorSelection_2_1": -1,
"vendorSelection_2_2": -1,
"vendorSelection_2_3": -1
}Notice that the maxSelectedVendors coefficient should be 1 and not 3 for each of those variables. The correct model for those variables is:
"z_0": {
"maxSelectedVendors": 1,
"vendorSelection_0_0": -1,
"vendorSelection_0_1": -1,
"vendorSelection_0_2": -1,
"vendorSelection_0_3": -1
},
"z_1": {
"maxSelectedVendors": 1,
"vendorSelection_1_0": -1,
"vendorSelection_1_1": -1,
"vendorSelection_1_2": -1,
"vendorSelection_1_3": -1
},
"z_2": {
"maxSelectedVendors": 1,
"vendorSelection_2_0": -1,
"vendorSelection_2_1": -1,
"vendorSelection_2_2": -1,
"vendorSelection_2_3": -1
}In your model generation code, change the following line:
result["z_"+shopId]["maxSelectedVendors"] = shopsAllowed;to
result["z_"+shopId]["maxSelectedVendors"] = 1;By doing so I get a result of 23, just as you expect.
joseph1125
commented
8 years ago Thank you very much, you are my saviour!
bchevalier
commented
8 years ago no problem!
I have a problem similar to this website http://stackoverflow.com/questions/8133755/find-the-best-way-to-buy-p-product-from-limit-x-vendors
I would like to ask if it is possible to solve this using your work