Optimal Balanced 1D Bin Packing

📌 Datasets → small to large (N) → uniform random values (1k–10M) → optimal packings → K ≤ 250,133 🚀

Author: mllmso

Overview

• Benchmark datasets for the 1D Bin Packing problem with Cardinality Constraints—at scale.
• All solutions achieve the theoretical optimum—with minimal K bins (dual constraints).
• Large-scale verified optimal packings—where optimality is generally not guaranteed (see 📜 SOTA_BPCC_25).
• Important: Computed on non-adversarial instances with an original algorithm—not included in the repository.

1. Problem

💬 Bin Packing with Cardinality Constraints (BPCC)

Given a bin capacity C and a max items per bin limit L, the goal is to pack N positive integers (items) into the minimum number of bins such that:

• the sum of items in each bin does not exceed C, and
• the number of items in each bin does not exceed L.

The problem is NP-hard—no polynomial-time algorithm can solve all instances optimally, unless P = NP.

BPCC has practical applications in cloud instance packing, parcel packing, and order batching.

2. Datasets

📊 Instances

• Total: 131
• Sizes: Small (N = 100) to large (N = 1,000,000)
• Packing: Low (K = 2) to high (K = 250,133)

🎲 Distributions

• Uniform:
  • True random, fully traceable, and unique positive integers from RANDOM.ORG
  • 1M unique random positive integers generated locally via a high-quality PRNG
• Ranges: Small [1-1,000] to large [1-10,000,000]

🔗 Constraints

• Bin capacity: C
• Number of bins: K = ceil(sum(multiset) / C)
• Max items per bin: limit = ceil(size(multiset) / K)
• Objective: Minimal K bins with sums ≤ C and items count ≤ limit 🟦

📄 File formats

• .json: Structured object with multiset, constraints, and packing keys

🔍 Validate packing

• Use the portable pseudocode in validate_packing_BPCC.txt

📅 First published in 2020

3. State of the Art

📈 mllmso—largest instances

• Small to large values

#	N	K	L	Range	Filename	Optimal
1	100	45	3	[1-1,000]	capacity-1001-k-45-limit-3	100% 🟦
2	1,000	443	3	[1-100,000]	capacity-110862-k-443-limit-3	100% 🟦
3	10,000	2,829	4	[1-100,000]	capacity-175454-k-2829-limit-4	100% 🟦
4	100,000	24,991	5	[1-1,000,000]	capacity-2000000-k-24991-limit-5	100% 🟦
5	1,000,000	250,133	4	[1-10,000,000]	capacity-20000000-k-250133-limit-4	100% 🟦

+Full list

According to 📜 SOTA_BPCC_25:

• In theory, instances #1–#5 are classified as "Easy".
• In practice, no known method guarantees optimality on instances #2–#5.

4. License

Author: mllmso

• ✅ Free to share, use, and adapt
• 💼 Commercial use allowed
• ℹ️ Attribution required — credit the author

Review the ⚖️ Full Legal Code