Clash Royale CLAN TAG#URR8PPP

Formal name for this optimization algorithm?

I have the following problem in one of my coding project which I will simplify here:

I am ordering groceries online and want very specific things in very specific quantities. I would like to order the following:

There are many stores equidistant from me which I will have food delivered from. Not all stores have what I need. I want to obtain what I need with the fewest number of orders made. For example, ordering from Store #2 below is a wasted order, since I can complete my items in less orders by ordering from different stores. What is the name of the optimization algorithm that solves this?

Store #1 Supply

Store #2 Supply

1 Orange Juice

2 Steaks

1 Soup

Store #3 Supply

25 Soup

50 Orange Juices

Store #4 Supply

25 Steaks

10 Yams

The lowest possible orders is 3 in this case. 8 Apples from Store #1. 2 Soup and 20 Orange Juice from Store #3. 1 Yam and 3 Steaks from Store #4.

3

1 Answer
1

To me, this most likely sounds like a restricted case of the Integer Linear programming problem (ILP), namely, its 0-or-1 variant, where the integer variables are restricted to the set 0, 1. This is known to be NP-hard (and the corresponding decision problem is NP-complete).

The problem is formulated as follows (following the conventions in the op. cit.):

Given the matrix A, the constraint vector b, and the weight vector c, find the vector x ∈ 0, 1^N such that all the constraints A⋅x ≥ b are satisfied, and the cost c⋅x is minimal.

Note that I flipped the constraint inequality, but this is equivalent to changing the sign of both A and b.

The inequalities indicate satisfaction of your order: that you can buy at the least the amount of every item in the visited store. Note that b has the length the same as the number of rows in A, and both c and x the number of columns. The dot-product c⋅x is, naturally, a scalar.

Since you are minimizing the number of trips, each trip costs the same, so that c = 1, and c⋅x is the total number of trips. The store inventory matrix A has a row per item, and a column per store, and the b is your shopping list.

Naturally, the exact best solution is found by trying all possible 2^N values for the x.

Since there is no single approach to NP-hard problems, consider the problem size, and how close to the optimum you want to arrive. A greedy approach would work well (when your next store to visit has the most total number of items not yet satisfied) when the "inventories" are large. If you have the idea in advance about the expected minimum number of trips, you can trim the search beam at some value, exceeding the number of trips by some multiplication coefficient. This is the best approach when your search is time constrained (I routinely do beam searches, closely related to the branch-and-cut approach mentioned in the article, in graphs that take a few GB of memory slightly faster than the limit of 30ms per exploration step with a beam as wide as 10,000). Simulated annealing also works, if the search landscape is not excessively rough.

Also search on cs.SE; it may be even a better place for questions of this type.

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.