CODEWITHSUNDEEP
algorithmsortingoptimizationsearch
Tabish Mir
Tabish Mir

Reputation: 799

Minimizing the number of warehouses for an order

I am trying to figure out an algorithm to efficiently solve the following problem:

The goal is to pick the minimum number of warehouses from which the order could be allocated.

E.g. the distribution of inventory in three warehouses is as follows

                |   Product 1   |   Product 2   |   Product 3   |
|---------------|---------------|---------------|---------------|
| Warehouse 1   |       2       |       5       |       0       |
| Warehouse 2   |       1       |       4       |       4       |
| Warehouse 3   |       3       |       1       |       4       |

Now suppose an order is placed with the following ordered quantities:

                |   Product 1   |   Product 2   |   Product 3   |
|---------------|---------------|---------------|---------------|
| Ordered Qty   |       5       |       4       |       1       |

The optimal solution here would be to allocate the order from Warehouse 1 and Warehouse 3. No other smaller subset of the 3 warehouses would be a better choice

I have tried using brute force to solve this, however, for a larger number of warehouses, the algorithm performs very poorly. I have also tried a few greedy allocation algorithms, however, as expected, they are unable to minimize the number of sub-orders in many cases. Are there any other algorithms/approaches that I should look into?

Upvotes: 3

Views: 1431

Answers (2)

Nelewout
Nelewout

Reputation: 6564

If you want to go down the ILP route, you could formulate the following programme:

model

Where w is the number of warehouses, p the number of products, n_j the quantity of product j ordered, and C_ij the quantity of product j stored in warehouse i. Then, the decisions are to select warehouse i (x_i = 1) or not (x_i = 0).

Using Google's ortools and the open-source CBC solver, this could be implemented as follows in Python:

import numpy as np
from ortools.linear_solver import pywraplp


# Some test data, replace with your own.
p = 50
w = 1000
n = np.random.randint(0, 10, p)
C = np.random.randint(0, 5, (w, p))

solver = pywraplp.Solver("model", pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
x = [solver.BoolVar(f"x[{i}]") for i in range(w)]
    
for j in range(p):
    solver.Add(C[:, j] @ x >= n[j])
    
solver.Minimize(sum(x))

This formulation solves instances with up to a thousand warehouses in a few seconds to a minute. Smaller instances solve much quicker, for (I hope) obvious reasons.

The following outputs the solution, and some statistics:

assert solver.Solve() is not None
    
print("Solution:")
print(f"assigned = {[i + 1 for i in range(len(x)) if x[i].solution_value()]}")
print(f"     obj = {solver.Objective().Value()}")
print(f"    time = {solver.WallTime() / 1000}s")

Upvotes: 1

Arty
Arty

Reputation: 16747

Part 1 (see also Part 2 below)

Your task looks like a Set Cover Problem which is NP-complete, hence having exponential solving time.

I decided (and implemented in C++) my own solution for it, which might be sub-exponential in one case - if it happens that many sub-sets of warehouses produce same amount of products in sum. In other words if an exponential size of a set of all warehouses sub-sets (which is 2^NumWarehouses) is much bigger than a set of all possible combinations of products counts produced by all sub-sets of warehouses. It often happens like so in most of tests of such problem like your in online competition. If so happens then my solution will be sub-exponential both in CPU and in RAM.

I used Dynamic Programming approach for this. Whole algorithm may be described as following:

  1. We create a map as a key having vector of amount of each product, and this key points to a triple, a) set of previous taken warehouses that reach current products amounts, this is to restore exact chosen warehouses, b) minimal amount of needed to take warehouses to achieve this products amounts, c) previous taken warehous that achieved this minimum of needed warehouses. This set is initialized with single key - vector of 0 products (0, 0, ..., 0).

  2. Iterate through all warehouses in a loop and do 3.-4..

  3. Iterate through all current products amounts (vectors) in a map and do 4..

  4. To iterated vector of products (in a map) we add amounts of products of iterated warehouse. This sum of two vectors is a new key in a map, inside a value pointed by this key we add to set an index of iterated warehouse, while minimum and previous warehouse we set to -1 (uninitialized).

  5. Using a recursive function for each key of a map find a minimum needed amount of warehouses and also find previous warehous achieving this minimum. This is easily done if for given key to iterate all warehouses in a Set, and find (recursively) their minimums, then minimum of current key will be minimum of all minimums plus 1.

  6. Iterate through all keys in a map that are bigger or equal (as a vector) to ordered amount of products. All these keys will give a solution, but only some of them will give Minimal solution, save a key that gives minimal solution of all. In a case if all keys in a map are smaller than current ordered vector then there is no possible solution and we can finish program with error.

  7. Having a minimal key we restore path backwards of all used warehouses to achieve this minimum. This is easy because for each key in a map we keep minimal amount of warehouses and previous warehouse that should be taken to achieve this minimum. Jumping by "previous" warehouses we restore whole path of needed warehouses. Finally output this found minimal solution.

As already mentioned this algorithm has Memory and Time complexity equal to amount of different distinct vectors of products that can be formed by all sub-sets of all warehouses. Which may (if we're lucky) or may not be (if we're unlucky) sub-exponential.

Full C++ code implementing algorithm above (implemented from scratch by me):

Try it online!

#include <cstdint>
#include <vector>
#include <tuple>
#include <map>
#include <set>
#include <unordered_map>
#include <functional>
#include <stdexcept>
#include <iostream>
#include <algorithm>

#define ASSERT(cond) { if (!(cond)) throw std::runtime_error("Assertion (" #cond ") failed at line " + std::to_string(__LINE__) + "!"); }
#define LN { std::cout << "LN " << __LINE__ << std::endl; }

using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;

int main() {
    std::vector<std::vector<u32>> warehouses_products = {
        {2, 5, 0},
        {1, 4, 4},
        {3, 1, 4},
    };
    std::vector<u32> order_products = {5, 4, 1};

    size_t const nwares = warehouses_products.size(),
        nprods = warehouses_products.at(0).size();

    ASSERT(order_products.size() == nprods);
    
    std::map<std::vector<u32>, std::tuple<std::set<u16>, u16, u16>> d =
        {{std::vector<u32>(nprods), {{}, 0, u16(-1)}}};

    for (u16 iware = 0; iware < nwares; ++iware) {
        auto const & wprods = warehouses_products[iware];
        ASSERT(wprods.size() == nprods);
        auto dc = d;
        for (auto const & [k, _]: d) {
            auto prods = k;
            for (size_t i = 0; i < wprods.size(); ++i)
                prods[i] += wprods[i];
            dc.insert({prods, {{}, u16(-1), u16(-1)}});
            std::get<0>(dc[prods]).insert(iware);
        }
        d = dc;
    }

    std::function<u16(std::vector<u32> const &)> FindMin =
        [&](auto const & prods) {
            auto & [a, b, c] = d.at(prods);
            if (b != u16(-1))
                return b;
            u16 minv = u16(-1), minw = u16(-1);
            for (auto iware: a) {
                auto const & wprods = warehouses_products[iware];
                auto cprods = prods;
                for (size_t i = 0; i < wprods.size(); ++i)
                    cprods[i] -= wprods[i];
                auto const fmin = FindMin(cprods) + 1;
                if (fmin < minv) {
                    minv = fmin;
                    minw = iware;
                }
            }
            ASSERT(minv != u16(-1) && minw != u16(-1));
            b = minv;
            c = minw;
            return b;
        };

    for (auto const & [k, v]: d)
        FindMin(k);

    std::vector<u32> minp;
    u16 minv = u16(-1);
    for (auto const & [k, v]: d) {
        bool matched = true;
        for (size_t i = 0; i < nprods; ++i)
            if (order_products[i] > k[i]) {
                matched = false;
                break;
            }
        if (!matched)
            continue;
        if (std::get<1>(v) < minv) {
            minv = std::get<1>(v);
            minp = k;
        }
    }

    if (minp.empty()) {
        std::cout << "Can't buy all products!" << std::endl;
        return 0;
    }

    std::vector<u16> answer;
    while (minp != std::vector<u32>(nprods)) {
        auto const & [a, b, c] = d.at(minp);
        answer.push_back(c);
        auto const & wprods = warehouses_products[c];
        for (size_t i = 0; i < wprods.size(); ++i)
            minp[i] -= wprods[i];
    }

    std::sort(answer.begin(), answer.end());

    std::cout << "WareHouses: ";
    for (auto iware: answer)
        std::cout << iware << ", ";
    std::cout << std::endl;
}

Input:

WareHouses Products:
{2, 5, 0},
{1, 4, 4},
{3, 1, 4},

Ordered Products:
{5, 4, 1}

Output:

WareHouses: 0, 2,

Part 2

Totally different solution I also implemented below.

Now it is based on Back Tracking using Recursive Function.

This solution although being exponential in worth case, yet it gives close to optimal solution after little time. So you just run this program as long as you can afford and whatever it has found so far you output as approximate solution.

Algorithm is as follows:

  1. Suppose we have some products left to buy. Lets sort in descending order all not taken so far warehouses by total amount of all products that they can buy us.

  2. In a loop we take each next warehouse from sorted descending list, but we take only first limit (this is fixed given value) elements from this sorted list. This way we take greedely warehouses in order of relevance, in order of the amount of products left to buy.

  3. After warehouse is taken we do recursive descend into current function in which we again form a sorted list of warehouses and take another most relevant warehouse, in other words jump to 1. of this algorithm.

  4. On each function call if we bought all products and amount of taken warehouses is less than current minimum then we output this solution and update minimum value.

Thus algorithm above starts from very greedy behaviour and then becomes slower and slower while becoming less greedy and more of brute force approach. And very good solutions appear already on first seconds.

As an example below I create 40 random warehouses with 40 random amounts of products each. This quite large task is solved Probably optimal within first second. By saying Probably I mean that next minutes of run don't give any better solution.

Try it online!

#include <cstdint>
#include <iomanip>
#include <iostream>
#include <random>
#include <vector>
#include <functional>
#include <chrono>
#include <cmath>

using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using i32 = int32_t;

double Time() {
    static auto const gtb = std::chrono::high_resolution_clock::now();
    return std::chrono::duration_cast<std::chrono::duration<double>>(
        std::chrono::high_resolution_clock::now() - gtb).count();
}

void Solve(auto const & wps, auto const & ops) {
    size_t const nwares = wps.size(), nprods = ops.size(), max_depth = 1000;
    
    std::vector<u32> prods_left = ops;
    std::vector<std::vector<u16>> sorted_wares_all(max_depth);
    std::vector<std::vector<u32>> prods_copy_all(max_depth);
    std::vector<u16> path;
    std::vector<u8> used(nwares);
    size_t min_wares = size_t(-1);
    
    auto ProdGrow = [&](auto const & prods){
        size_t grow = 0;
        for (size_t i = 0; i < nprods; ++i)
            grow += std::min(prods_left[i], prods[i]);
        return grow;
    };
    
    std::function<void(size_t, size_t, size_t)> Rec = [&](size_t depth, size_t off, size_t lim){
        size_t prods_need = 0;
        for (auto e: prods_left)
            prods_need += e;
        if (prods_need == 0) {
            if (path.size() < min_wares) {
                min_wares = path.size();
                std::cout << std::endl << "Time " << std::setw(4) << std::llround(Time())
                    << " sec, Cnt " << std::setw(3) << path.size() << ":   ";
                auto cpath = path;
                std::sort(cpath.begin(), cpath.end());
                for (auto e: cpath)
                    std::cout << e << ", ";
                std::cout << std::endl << std::flush;
            }
            return;
        }
        auto & sorted_wares = sorted_wares_all.at(depth);
        auto & prods_copy = prods_copy_all.at(depth);
        sorted_wares.clear();
        for (u16 i = off; i < nwares; ++i)
            if (!used[i])
                sorted_wares.push_back(i);
        std::sort(sorted_wares.begin(), sorted_wares.end(),
            [&](auto a, auto b){
                return ProdGrow(wps[a]) > ProdGrow(wps[b]);
            });
        sorted_wares.resize(std::min(lim, sorted_wares.size()));
        for (size_t i = 0; i < sorted_wares.size(); ++i) {
            u16 const iware = sorted_wares[i];
            auto const & wprods = wps[iware];
            prods_copy = prods_left;
            for (size_t j = 0; j < nprods; ++j)
                prods_left[j] -= std::min(prods_left[j], wprods[j]);
            path.push_back(iware);
            used[iware] = 1;
            Rec(depth + 1, iware + 1, lim);
            used[iware] = 0;
            path.pop_back();
            prods_left = prods_copy;
        }
        for (auto e: sorted_wares)
            used[e] = 0;
    };
    
    for (size_t lim = 1; lim <= nwares; ++lim) {
        std::cout << "Limit " << lim << ", " << std::flush;
        Rec(0, 0, lim);
    }
}

int main() {
    size_t const nwares = 40, nprods = 40;
    std::mt19937_64 rng{std::random_device{}()};
    std::vector<std::vector<u32>> wps(nwares);
    for (size_t i = 0; i < nwares; ++i) {
        wps[i].resize(nprods);
        for (size_t j = 0; j < nprods; ++j)
            wps[i][j] = rng() % 90 + 10;
    }
    std::vector<u32> ops;
    for (size_t i = 0; i < nprods; ++i)
        ops.push_back(rng() % (nwares * 20));
    Solve(wps, ops);
}

Output:

Limit 1, Limit 2, Limit 3, Limit 4,
Time    0 sec, Cnt  13:   6, 8, 12, 13, 29, 31, 32, 33, 34, 36, 37, 38, 39,
Limit 5,
Time    0 sec, Cnt  12:   6, 8, 12, 13, 28, 29, 31, 32, 36, 37, 38, 39,
Limit 6, Limit 7,
Time    0 sec, Cnt  11:   6, 8, 12, 13, 19, 26, 31, 32, 33, 36, 39,
Limit 8, Limit 9, Limit 10, Limit 11, Limit 12, Limit 13, Limit 14, Limit 15,

Upvotes: 2

Related Questions