3
$\begingroup$

There are $m$ items to be allocated into $n$ bins. The profit generated by placing the $i$-th item into the $j$-th bin is $c_{ij}$, and the service level is $s_{ij}$. A allocation scheme is required to maximize the total profit while satisfying a certain service level $M$.

To represent the mathematical model of this problem, a variable $y_i$ is introduced to represent the bin number where the $i$-th item is placed. However, it is not possible to obtain the corresponding profit and service level based on the index.

Therefore, another approach is used, where 0-1 variables $x_{ij}$ are introduced to represent whether the $i$-th item is placed in the $j$-th bin. The corresponding mathematical model can be expressed as:

$\max \sum\limits_{ij}{c_{ij}x_{ij}}$

s.t.

$\sum\limits_{j}{x_{ij}}=1 \;\;\;\; \forall i$

$\sum\limits_{ij}{s_{ij}x_{ij}} \geq M$

SCIP can be used to find the optimal solution for small-scale problems. Howerver, for this problem with a large scale of hundreds of millions of items, it need a long time. Therefore, I would like to know if there are any effective heuristic methods that can guarantee near-optimal solutions, or whether the problem can be transformed into an assignment or graph matching problem, and then solved using specific graph theory methods to find the optimal solution?

$\endgroup$
8
  • 1
    $\begingroup$ There is no constraint on the bins mentioned in either your description or your model. Is it true that you can place any number of items into a bin? $\endgroup$ Nov 1, 2023 at 15:32
  • $\begingroup$ As @NaturalLogZ points out, you list no constraint on the content of any bin. Under that assumption, the solution is trivial: assign each item to its most profitable bin. $\endgroup$
    – prubin
    Nov 1, 2023 at 15:55
  • $\begingroup$ @prubin assigning each item to its most profitable bin isn't guaranteed to meet the service requirement, since the service level depends on both the item and bin. But it does feel like the problem should be much easier under this assumption. I wonder if something along the lines of taking pairings $ij$ such that $c_{ij}s_{ij}$ is maximized until the service requirement is satisfied, and then assigning each remaining item to its most profitable bin would be a good heuristic. $\endgroup$ Nov 1, 2023 at 18:15
  • 1
    $\begingroup$ It's close to a multiple-choice knapsack problem $\endgroup$
    – fontanf
    Nov 1, 2023 at 19:10
  • $\begingroup$ @NaturalLogZ Indeed, we can place any number of items into a bin. Is the heuristic algorithm you mentioned first try to maximize the product of c and s, i.e., $c_{ij}s_{ij}$? $\endgroup$
    – Ying
    Nov 2, 2023 at 3:14

2 Answers 2

2
$\begingroup$

I don't think the following heuristic can be said to "guarantee near-optimal solutions", but it is quite straightforward to code and can make efficient use of parallel threading/multiple cores.

If we do a partial Lagrangean relaxation of the original problem, relaxing only the service level constraint, we end up maximizing $$\sum_{i,j} (c_{i,j}+\lambda s_{i,j})x_{i,j} - \lambda M$$ subject to the single assignment constraint and $x$ being binary, with $\lambda \ge 0$ the Lagrangean multiplier value. The constant term is irrelevant.

So the heuristic proceeds as follows. Pick a positive value for $\lambda.$ For each item $i,$ evaluate $c_{i,j} + \lambda s_{i,j}$ for all bins $j$ and assign $i$ to the bin $j$ for which that expression is maximal, breaking ties in favor of higher service levels. Compute the service total $\sum_{i,j} s_{i,j}x_{i,j}$ and see if it meets or exceeds $M.$ If yes, try lowering $\lambda.$ If no, try raising $\lambda.$ Keep track of the feasible solution with best objective value. Stop when you run out of time or enthusiasm. Since this is basically a line search on the one-dimensional parameter $\lambda,$ you could use bisection search.

$\endgroup$
3
  • $\begingroup$ Can we use the subgradient method to improve the value of $\lambda$,which may result a Lagrange relaxation method? $\endgroup$
    – Ying
    Nov 2, 2023 at 3:48
  • 1
    $\begingroup$ The subgradient method is useful when there are multiple variables to optimize. To optimize a single variable, a dichotomic search should work better $\endgroup$
    – fontanf
    Nov 3, 2023 at 10:40
  • $\begingroup$ Great, thanks, I understand. $\endgroup$
    – Ying
    Nov 4, 2023 at 14:51
-1
$\begingroup$

The assignment and packing problem (APP) is a combinatorial optimization problem that involves assigning a set of items to a set of bins, such that each item is assigned to exactly one bin and the total profit or service level is maximized. The problem has a wide range of applications in logistics, manufacturing, and other fields.

There are a number of effective methods for solving the APP, including:

Branch-and-bound: This is a general-purpose algorithm for solving combinatorial optimization problems. It works by recursively exploring the solution space, pruning branches that cannot lead to optimal solutions.

  • Hungarian method: This is a specific algorithm for solving the assignment problem. It works by finding a minimum-cost matching between the items and the bins.
  • Genetic algorithms: This is a population-based algorithm that mimics the process of natural selection to find optimal solutions to problems. It works by creating a population of solutions and then iteratively evolving the population by combining and mutating solutions.
  • Particle swarm optimization: This is another population-based algorithm that mimics the behavior of a swarm of particles to find optimal solutions to problems. It works by creating a swarm of particles and then iteratively updating the position of each particle based on the positions of the other particles in the swarm.

The best method for solving the APP depends on a number of factors, including the size of the problem, the desired accuracy, and the available computational resources. For small problems, it is often possible to find optimal solutions using branch-and-bound or the Hungarian method. For larger problems, it may be necessary to use a heuristic method, such as a genetic algorithm or particle swarm optimization.

Here are some additional details about the methods mentioned above:

Branch-and-bound:

Branch-and-bound works by recursively exploring the solution space, pruning branches that cannot lead to optimal solutions. At each node of the search tree, a lower bound on the cost of the optimal solution is calculated. If the lower bound is greater than the cost of the best solution found so far, then the branch is pruned. Otherwise, the branch is split into two new branches, corresponding to the two possible assignments of the next item.

Hungarian method:

The Hungarian method works by finding a minimum-cost matching between the items and the bins. A matching is a set of pairs of items and bins, such that each item is assigned to exactly one bin and each bin is assigned to exactly one item. The cost of a matching is the sum of the costs of assigning each item to its bin.

The Hungarian method works by iteratively reducing the cost of the current matching. In each iteration, the algorithm identifies a set of unassigned items and bins, and then finds a minimum-cost assignment of the items and bins in the set. The algorithm terminates when no further improvement can be made to the matching.

Genetic algorithms:

Genetic algorithms are population-based algorithms that mimic the process of natural selection to find optimal solutions to problems. They work by creating a population of solutions and then iteratively evolving the population by combining and mutating solutions.

In the context of the APP, a solution can be represented by a vector, where each element of the vector represents the bin to which an item is assigned. The genetic algorithm works by creating a population of such vectors. The algorithm then iteratively evolves the population by selecting two solutions from the population at random and creating a new solution by combining the two solutions. The new solution is then mutated by randomly changing the assignment of one or more items.

Particle swarm optimization:

Particle swarm optimization is another population-based algorithm that mimics the behavior of a swarm of particles to find optimal solutions to problems. It works by creating a swarm of particles and then iteratively updating the position of each particle based on the positions of the other particles in the swarm.

In the context of the APP, a particle can be represented by a vector, where each element of the vector represents the bin to which an item is assigned. The particle swarm optimization algorithm works by creating a swarm of such vectors. The algorithm then iteratively updates the position of each particle by moving it towards the position of the best particle in the swarm. The algorithm also allows the particles to move randomly to explore the solution space.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.