Formal name for this optimization algorithm?

Question

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:

• 8 Apples
• 1 Yam
• 2 Soups
• 3 Steaks
• 20 Orange Juices

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

• 50 Apples

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.

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.

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 same length as the number of rows in A and the number of columns in both c and x. 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.