3
$\begingroup$

I am interested in the following problem. The input is a set of $n$ integers, and a fixed integer $k$. The required output is a partitioning of the integers into $k$ subsets, such that the smallest sum of a subset is as large as possible. This is a variant of the NP-hard multiway number partitioning problem.

I found several references for Python solutions of a related problem - bin packing:

But it is a different problem. Also, I am not sure what is the most efficient way to approach this problem - should I search for solutions for this specific problem? Or should I just present it as a general integer programming or use a generic solver?

EDIT: Following the answer by Rob Pratt, I installed PuLP and solved the problem using an integer linear program. In case anyone is interested, here is the code.

def mms_partition(values:list, k:int)->int:
    parts = range(k)
    items = range(len(values))
    min_value = pulp.LpVariable("min_value", cat=pulp.LpContinuous)
    vars = [
        [pulp.LpVariable(f"x_{item}_{part}", lowBound=0, upBound=1, cat=pulp.LpInteger)
        for part in parts]
        for item in items
    ]         # vars[i][j] is 1 iff item i is in part j.
    mms_problem = pulp.LpProblem("MMS_problem", pulp.LpMaximize)
    mms_problem += min_value    # Objective function: maximize min_value
    for item in items:  # Constraints: each item must be in exactly one part.
        mms_problem += (pulp.lpSum([vars[item][part] for part in parts]) == 1)
    for part in parts:  # Constraint: the sum of each part must be at least min_value (by definition of min_value).
        mms_problem += (min_value <= pulp.lpSum([vars[item][part]*values[item] for item in items]))
    pulp.PULP_CBC_CMD(msg=False).solve(mms_problem)
    return min_value.value()

Usually it works quite fast, but in some cases it is very slow. Here are some run-times on random instances, all with $k=3$:

3 items, 1-of-3 MMS: 0.013010892027523369 seconds.
    [1, 8, 14]
4 items, 1-of-3 MMS: 0.07400063099339604 seconds.
    [47, 49, 54, 64]
5 items, 1-of-3 MMS: 0.07231759402202442 seconds.
    [20, 64, 71, 72, 94]
6 items, 1-of-3 MMS: 0.08935485797701403 seconds.
    [45, 55, 61, 70, 86, 93]
7 items, 1-of-3 MMS: 0.11710083403158933 seconds.
    [13, 41, 42, 55, 56, 88, 90]
8 items, 1-of-3 MMS: 0.1803806659881957 seconds.
    [9, 31, 45, 49, 54, 55, 62, 62]
9 items, 1-of-3 MMS: 0.1663428150350228 seconds.
    [3, 6, 23, 35, 38, 38, 46, 77, 84]
10 items, 1-of-3 MMS: 0.28711252100765705 seconds.
    [29, 34, 43, 46, 54, 56, 70, 81, 92, 95]
11 items, 1-of-3 MMS: 0.03978497500065714 seconds.
    [3, 9, 11, 26, 37, 41, 49, 76, 82, 83, 96]
12 items, 1-of-3 MMS: 0.6636879530269653 seconds.
    [3, 8, 9, 12, 38, 47, 53, 65, 71, 73, 85, 94]
13 items, 1-of-3 MMS: 0.08022642397554591 seconds.
    [31, 31, 32, 39, 40, 46, 49, 50, 55, 59, 61, 62, 90]
14 items, 1-of-3 MMS: 0.13822774798609316 seconds.
    [22, 29, 35, 50, 51, 62, 66, 74, 78, 80, 82, 87, 93, 97]
15 items, 1-of-3 MMS: 0.06699130398919806 seconds.
    [5, 6, 8, 9, 12, 15, 15, 18, 19, 54, 56, 59, 73, 73, 88]
16 items, 1-of-3 MMS: 7.507785552996211 seconds.
    [18, 29, 30, 30, 44, 47, 57, 60, 66, 77, 77, 78, 79, 82, 83, 93]
17 items, 1-of-3 MMS: 0.09432925801957026 seconds.
    [2, 3, 9, 14, 15, 25, 29, 32, 36, 39, 42, 62, 65, 68, 79, 81, 92]
18 items, 1-of-3 MMS: 0.14621741196606308 seconds.
    [6, 6, 8, 10, 16, 26, 26, 38, 42, 48, 51, 60, 72, 79, 89, 94, 95, 98]
19 items, 1-of-3 MMS: 7.723582196980715 seconds.
    [23, 36, 41, 44, 54, 56, 66, 67, 72, 75, 79, 86, 87, 88, 92, 93, 95, 96, 98]
20 items, 1-of-3 MMS: 132.41131251398474 seconds.
    [10, 10, 11, 13, 24, 26, 26, 28, 29, 35, 51, 62, 66, 69, 79, 80, 82, 87, 88, 94]

EDIT: Here is the log of CBC solving the 20-item problem:

Welcome to the CBC MILP Solver 
Version: 2.9.0 
Build Date: Feb 12 2015 

command line - /usr/local/lib/python3.8/dist-packages/pulp/apis/../solverdir/cbc/linux/64/cbc /tmp/3de7ce0a9b7f41edbfad00526ae9bffd-pulp.mps max branch printingOptions all solution /tmp/3de7ce0a9b7f41edbfad00526ae9bffd-pulp.sol (default strategy 1)
At line 2 NAME          MODEL
At line 3 ROWS
At line 28 COLUMNS
At line 273 RHS
At line 297 BOUNDS
At line 359 ENDATA
Problem MODEL has 23 rows, 61 columns and 123 elements
Coin0008I MODEL read with 0 errors
Continuous objective value is 323.333 - 0.00 seconds
Cgl0004I processed model has 23 rows, 61 columns (60 integer (60 of which binary)) and 123 elements
Cbc0038I Initial state - 4 integers unsatisfied sum - 0.632799
Cbc0038I Pass   1: suminf.    0.00000 (0) obj. -309 iterations 3
Cbc0038I Solution found of -309
Cbc0038I Relaxing continuous gives -309
Cbc0038I Before mini branch and bound, 56 integers at bound fixed and 0 continuous
Cbc0038I Full problem 23 rows 61 columns, reduced to 2 rows 2 columns
Cbc0038I Mini branch and bound did not improve solution (0.00 seconds)
Cbc0038I Round again with cutoff of -310.433
Cbc0038I Pass   2: suminf.    0.03050 (2) obj. -310.433 iterations 1
Cbc0038I Pass   3: suminf.    0.62908 (2) obj. -310.433 iterations 1
Cbc0038I Pass   4: suminf.    0.82473 (2) obj. -310.433 iterations 8
Cbc0038I Solution found of -310.433
Cbc0038I Relaxing continuous gives -312
Cbc0038I Before mini branch and bound, 40 integers at bound fixed and 0 continuous
Cbc0038I Full problem 23 rows 61 columns, reduced to 3 rows 11 columns
Cbc0038I Mini branch and bound improved solution from -312 to -322 (0.00 seconds)
Cbc0038I Round again with cutoff of -322.267
Cbc0038I Pass   5: suminf.    0.30922 (3) obj. -322.267 iterations 1
Cbc0038I Pass   6: suminf.    0.37730 (3) obj. -322.267 iterations 1
Cbc0038I Pass   7: suminf.    0.63034 (4) obj. -322.267 iterations 10
Cbc0038I Pass   8: suminf.    0.09867 (4) obj. -322.267 iterations 4
Cbc0038I Pass   9: suminf.    0.68337 (4) obj. -322.267 iterations 7
Cbc0038I Pass  10: suminf.    0.30922 (3) obj. -322.267 iterations 4
Cbc0038I Pass  11: suminf.    0.37730 (3) obj. -322.267 iterations 5
Cbc0038I Pass  12: suminf.    1.21920 (4) obj. -322.267 iterations 7
Cbc0038I Pass  13: suminf.    0.25604 (4) obj. -322.267 iterations 6
Cbc0038I Pass  14: suminf.    0.77137 (4) obj. -322.267 iterations 7
Cbc0038I Pass  15: suminf.    0.35177 (3) obj. -322.267 iterations 6
Cbc0038I Pass  16: suminf.    0.41986 (3) obj. -322.267 iterations 5
Cbc0038I Pass  17: suminf.    0.83404 (4) obj. -322.267 iterations 16
Cbc0038I Pass  18: suminf.    0.54975 (4) obj. -322.267 iterations 6
Cbc0038I Pass  19: suminf.    1.27959 (4) obj. -322.267 iterations 9
Cbc0038I Pass  20: suminf.    0.56454 (3) obj. -322.267 iterations 5
Cbc0038I Pass  21: suminf.    0.63262 (3) obj. -322.267 iterations 8
Cbc0038I Pass  22: suminf.    1.31931 (4) obj. -322.267 iterations 15
Cbc0038I Pass  23: suminf.    1.00000 (3) obj. -322.267 iterations 8
Cbc0038I Pass  24: suminf.    1.00000 (3) obj. -322.267 iterations 9
Cbc0038I Pass  25: suminf.    1.00000 (3) obj. -322.267 iterations 6
Cbc0038I Pass  26: suminf.    1.37854 (4) obj. -322.267 iterations 12
Cbc0038I Pass  27: suminf.    0.56454 (3) obj. -322.267 iterations 8
Cbc0038I Pass  28: suminf.    0.63262 (3) obj. -322.267 iterations 10
Cbc0038I Pass  29: suminf.    1.02096 (4) obj. -322.267 iterations 12
Cbc0038I Pass  30: suminf.    0.98971 (4) obj. -322.267 iterations 6
Cbc0038I Pass  31: suminf.    1.42328 (4) obj. -322.267 iterations 13
Cbc0038I Pass  32: suminf.    1.42328 (4) obj. -322.267 iterations 5
Cbc0038I Pass  33: suminf.    1.01418 (4) obj. -322.267 iterations 11
Cbc0038I Pass  34: suminf.    1.01418 (4) obj. -322.267 iterations 3
Cbc0038I No solution found this major pass
Cbc0038I Before mini branch and bound, 15 integers at bound fixed and 0 continuous
Cbc0038I Full problem 23 rows 61 columns, reduced to 14 rows 40 columns
Cbc0038I Mini branch and bound did not improve solution (0.03 seconds)
Cbc0038I After 0.03 seconds - Feasibility pump exiting with objective of -322 - took 0.03 seconds
Cbc0012I Integer solution of -322 found by feasibility pump after 0 iterations and 0 nodes (0.03 seconds)
Cbc0038I Full problem 23 rows 61 columns, reduced to 3 rows 10 columns
Cbc0031I 3 added rows had average density of 61
Cbc0013I At root node, 3 cuts changed objective from -323.33333 to -323.33333 in 100 passes
Cbc0014I Cut generator 0 (Probing) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.007 seconds - new frequency is -100
Cbc0014I Cut generator 1 (Gomory) - 352 row cuts average 60.9 elements, 0 column cuts (0 active)  in 0.008 seconds - new frequency is -100
Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.003 seconds - new frequency is -100
Cbc0014I Cut generator 3 (Clique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.001 seconds - new frequency is -100
Cbc0014I Cut generator 4 (MixedIntegerRounding2) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.005 seconds - new frequency is -100
Cbc0014I Cut generator 5 (FlowCover) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.001 seconds - new frequency is -100
Cbc0014I Cut generator 6 (TwoMirCuts) - 28 row cuts average 47.3 elements, 0 column cuts (0 active)  in 0.003 seconds - new frequency is -100
Cbc0010I After 0 nodes, 1 on tree, -322 best solution, best possible -323.33333 (0.09 seconds)
Cbc0038I Full problem 23 rows 61 columns, reduced to 3 rows 15 columns
Cbc0004I Integer solution of -323 found after 961 iterations and 81 nodes (0.13 seconds)
Cbc0038I Full problem 23 rows 61 columns, reduced to 4 rows 13 columns
Cbc0038I Full problem 23 rows 61 columns, reduced to 4 rows 13 columns
Cbc0038I Full problem 23 rows 61 columns, reduced to 5 rows 16 columns
Cbc0038I Full problem 23 rows 61 columns, reduced to 3 rows 14 columns
Cbc0038I Full problem 23 rows 61 columns, reduced to 4 rows 18 columns
Cbc0038I Full problem 23 rows 61 columns, reduced to 5 rows 21 columns
Cbc0010I After 1000 nodes, 8 on tree, -323 best solution, best possible -323.33333 (2.30 seconds)
Cbc0038I Full problem 23 rows 61 columns, reduced to 4 rows 19 columns
Cbc0038I Full problem 23 rows 61 columns, reduced to 3 rows 16 columns
Cbc0038I Full problem 23 rows 61 columns, reduced to 3 rows 17 columns
Cbc0010I After 2000 nodes, 5 on tree, -323 best solution, best possible -323.33333 (4.62 seconds)
Cbc0038I Full problem 23 rows 61 columns, reduced to 3 rows 13 columns
Cbc0038I Full problem 23 rows 61 columns, reduced to 5 rows 22 columns
Cbc0010I After 3000 nodes, 5 on tree, -323 best solution, best possible -323.33333 (7.92 seconds)
Cbc0038I Full problem 23 rows 61 columns, reduced to 3 rows 19 columns
Cbc0010I After 4000 nodes, 5 on tree, -323 best solution, best possible -323.33333 (9.92 seconds)
Cbc0038I Full problem 23 rows 61 columns, reduced to 4 rows 17 columns
Cbc0010I After 5000 nodes, 6 on tree, -323 best solution, best possible -323.33333 (12.14 seconds)
Cbc0038I Full problem 23 rows 61 columns, reduced to 4 rows 17 columns
Cbc0001I Search completed - best objective -323, took 2028836 iterations and 1170256 nodes (13.24 seconds)
Cbc0032I Strong branching done 10846 times (21617 iterations), fathomed 206 nodes and fixed 620 variables
Cbc0041I Maximum depth 20, 257 variables fixed on reduced cost (complete fathoming 2647 times, 1164430 nodes taking 2019718 iterations)
Cuts at root node changed objective from -323.333 to -323.333
Probing was tried 100 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.007 seconds)
Gomory was tried 100 times and created 352 cuts of which 0 were active after adding rounds of cuts (0.008 seconds)
Knapsack was tried 100 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.003 seconds)
Clique was tried 100 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.001 seconds)
MixedIntegerRounding2 was tried 100 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.005 seconds)
FlowCover was tried 100 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.001 seconds)
TwoMirCuts was tried 100 times and created 28 cuts of which 0 were active after adding rounds of cuts (0.003 seconds)

Result - Optimal solution found

Objective value:                323.00000000
Enumerated nodes:               1170256
Total iterations:               2028836
Time (CPU seconds):             13.24
Time (Wallclock seconds):       13.54

Option for printingOptions changed from normal to all
Total time (CPU seconds):       13.24   (Wallclock seconds):       13.54

EDIT: I re-implemented with XPRESS solver. Now I can solve instances with over 100 items in less than a second. I do not know what was the problem with CBC.

Improve this question
$\endgroup$
7
  • $\begingroup$ For the slow cases, do you have any duplicate values in your input list? $\endgroup$
    – RobPratt
    Apr 20, 2021 at 14:59
  • $\begingroup$ @RobPratt there are few duplicate values - I just uploaded my test log. It is interesting that the run-time is not monotone, e.g. the run-time for the random instance with 17 items is much lower than for the random instance with 16 items. $\endgroup$
    – Erel Segal-Halevi
    Apr 20, 2021 at 15:19
  • $\begingroup$ I recommend trying the symmetry-breaking constraints, and using the greedy heuristic to pass in a good feasible solution might also help. $\endgroup$
    – RobPratt
    Apr 20, 2021 at 15:34
  • $\begingroup$ At least one commercial solver handles the largest one instantly. Even if you disable symmetry, presolver, heuristics, and cuts, it still takes only a few seconds. Optimal is 323, and the greedy heuristic yields 320. If you share your solver log, maybe somebody can identify what's taking so long. $\endgroup$
    – RobPratt
    Apr 20, 2021 at 19:09
  • $\begingroup$ I tried this specific instance again, and it took only 13 seconds (log attached). Much less than the 132 seconds (perhaps the 132 was due to a temporary problem). When I add symmetry-breaking constraints as you suggested, the run-time improves to about 11 seconds. I ran several times to be sure. $\endgroup$
    – Erel Segal-Halevi
    Apr 21, 2021 at 12:52

1 Answer 1

Reset to default
4
$\begingroup$

Here's one possible formulation, where $a_1,\dots, a_n$ are the values of the $n$ integers. Let binary decision variable $x_{i,j}$ indicate whether integer $i$ is assigned to subset $j\in\{1,\dots,k\}$. The problem is to maximize $z$ subject to \begin{align} \sum_j x_{i,j} &= 1 &&\text{for all $i$} \tag1\\ \sum_i a_i x_{i,j} &\ge z &&\text{for all $j$} \tag2 \end{align} Constraint $(1)$ assigns each integer to exactly one subset. Constraint $(2)$ enforces the maximin objective.

If you use a solver that does not exploit symmetry, you will want to include explicit symmetry-breaking constraints. For example, impose descending order with respect to $j$: $$\sum_i a_i x_{i,j} \ge \sum_i a_i x_{i,j+1}$$

If you have multiple duplicate values of $a_i$, an integer (rather than binary) formulation is likely to perform better. In that case, the interpretation of $x_{i,j}$ is the number of copies of integer $i$ assigned to subset $j$, and the RHS of $(1)$ should instead be the total number of copies of integer $i$.

In either case, a simple greedy heuristic can provide a good initial feasible solution: sort the values in descending order and assign each item to the subset whose current sum is the smallest.

Another approach for this maximin problem is to apply bisection search for the optimal objective value $z^*$. The greedy heuristic (or any integer feasible solution) provides a lower bound $L$, and $U=(\sum_i a_i)/k$ is an upper bound. Now perform a bisection search on the interval $[L,U]$, in each step fixing $z$ to a trial value $\hat{z}=(L+U)/2$ and solving the resulting feasibility problem. If the problem is feasible for a given $\hat{z}$, it is feasible for all smaller $z$ values, and you can update $L=\hat{z}$. Conversely, if the problem is infeasible for a given $\hat{z}$, it is infeasible for all larger $z$ values, and you can update $U=\hat{z}$. Repeat as needed until the gap $U-L$ is sufficiently small.

Improve this answer
$\endgroup$
11
  • $\begingroup$ What do you mean by "you will want to include explicit symmetry-breaking constraints"? $\endgroup$
    – Erel Segal-Halevi
    Apr 17, 2021 at 23:30
  • $\begingroup$ This formulation is symmetric with respect to $j$, and symmetry can cause redundant computation. Most commercial solvers detect this and avoid the redundancy. What solver are you using? $\endgroup$
    – RobPratt
    Apr 17, 2021 at 23:49
  • 1
    $\begingroup$ Are you looking for a commercial solver or an open-source solver? For open-source, you might look at the COIN-OR projects page (coin-or.org/projects). Expand the "Optimization deterministic linear discrete" section and you will find a number of projects for Python users, typically modeling interfaces to solvers (separate projects) written in C/C++. $\endgroup$
    – prubin ♦
    Apr 18, 2021 at 14:51
  • 1
    $\begingroup$ @ErelSegal-Halevi To get an idea of the performance of MIP solvers on Bin Packing problems, please have a look at this benchmark between LocalSolver and Gurobi: localsolver.com/benchmarkbpp.html. LocalSolver delivers near-optimal solutions in minutes for Bin Packing instances with 10,000 items thanks to the local search heuristics it embeds. Disclaimer: LocalSolver is commercial software, but free for teaching and basic research. $\endgroup$
    – LocalSolver
    Apr 20, 2021 at 16:44
  • 1
    $\begingroup$ @ErelSegal-Halevi If you're ready to implement a specific algorithm: start with a greedy solution as RobPratt suggested, then improve by local search moves. Here is an example of basic moves: exchange one item in a bin with two items in another one. To converge toward near-optimal solutions in minutes, you will need more complex moves related to ejection chains. Check the literature on the topic. LocalSolver embeds hundreds of moves, dynamically autotuned during the search, complementing an automatic column generation approach to derive lower bounds. $\endgroup$
    – LocalSolver
    Apr 20, 2021 at 16:52

Your Answer

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

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