We have 10 bags. Each bag has 5 compartments numbered from 1 to 5. We have 100 objects to fill all the compartments and bags. Compartment number x in a bag is identical to compartment of the same number in the other bags. Putting some objects together in a bag may be dangerous. The danger ranges from 0 to 3.

  • Putting an object in a compartment has a score from 0 to 3: S_obj_o_comp_c
  • Putting an object in a bag has a value from 0 to 3: S_obj_o_bag_b
  • Putting object x in the same bag as object y has a cost from 0 to -3: C_obj_x_obj_y.

The problem is how to put objects into compartments to gain maximum score.

The number of different combinations of objects/compartments/bags is 100 * 99 * ... * 50 which is 100!/49! Clearly, it is not feasible to solve this by Backtrack or brute-force.

Is it possible to find an exact solution for this problem? What about approximate solution?

  • 1
    This appears to be a variant of the Knapsack problem – Bart van Ingen Schenau Mar 6 '17 at 7:29
  • Finding the optimal solution is generally only possibly by evaluating all eligible solutions. So to do that, we need to narrow the solution space. Finding sets of equivalent solutions is one strategy. E.g. the order of bags and the order of compartments in a bag does not seem to matter here. You can pre-process the objects to determine worst-case/best-case scores. When traversing all solutions, we can perhaps discard candidate solutions if it's impossible for them to outperform the currently known optimum. Carefully studying the score function might open up shortcuts. – amon Mar 6 '17 at 12:39
  • @BartvanIngenSchenau Kind of. But the main difference is that we have many bags. – Hans Mar 7 '17 at 0:50
  • @amon Correct but how? I though it might be a typical problem in combinatoric optimization. – Hans Mar 7 '17 at 0:51

This part is not necessarily clear from your problem description but I am going to assume that you can only put one object per compartment.

If you drop the fact that putting together object x and y in the same bag can have an impact on the objective function, then you can model your problem as a min cost flow problem (which can be efficiently solved):

  • Each object is represented by a node.

  • Each compartment is represented by a node.

  • An arc of capacity 1 and cost 0 links the source of the graph to each object node.

  • An arc of capacity 1 and cost 0 links each compartment node to the sink of the graph.

  • An arc of capacity 1 and cost between 0 and -6 links every object node to every compartment node (-6 because we reverse the costs in order to have a minimization problem).

However, this is not your original problem description. In order to capture the cost of combining two objects in the same bag you could model your problem as a Mixed Integer Problem, and solve it with a dedicated solver (see glpk or cbc for open source ones, cplex or gurobi for commercial ones). If you decide to go this way, you could adopt the following model:

  • For each pair of object and compartment in a given bag define a binary variable indicating whether or not that object is put in that compartment of that bag. The contribution of this variable to the objective function is between 0 and 6.

  • For each object add a constraint stating that the sum of all the associated binary variable linking it to a given bag compartment should be less or equal than one.

  • For every pair of objects add a binary variable representing if the two objects are combined in the same bag. The contribution of this variable to the objective function should be between 0 and -3.

  • For every combination of objects pair and bag add a constraint stating that the binary variable representing if the two objects are combined in the same bag should be bigger or equal to -1 + the sum of all assignment variable linking one of those two objects with a compartment of the bag.

Regarding a heuristic approach to the problem, you could do the following thing:

  • Start with the first compartment of the first bag:

  • Assign the object that leads to the biggest increase of the score. Break ties by selecting the object for which the sum of its danger with remaining bags is minimum. Remove the object from the list of remaining objects, move on to the next compartment.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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