01-marketsplit

01 - Market Split Problem

Alternative Names: Multi-Dimensional Subset Sum Problem

← Back to Main Repository

---

Overview

The Market Split Problem is a multi-dimensional variant of the classic subset sum problem, where multiple constraints must be satisfied simultaneously. Each row represents its own subset sum problem, making this a challenging combinatorial optimization task.

Problem Description

Given a matrix $A \in \mathbb{N}^{m,n}$ and a right-hand side vector $b \in \mathbb{N}^m$, find a feasible binary vector $x \in {0,1}^{n}$ that satisfies:

$$ Ax = b $$

where each row $i \in {1,\ldots,m}$ represents an independent subset sum constraint that must be fulfilled simultaneously.

Directory Contents

• instances/ - Problem instances in various formats
• models/ - Mathematical model formulations
• solutions/ - Optimal or best-known solutions
• check/ - Solution verification tools
• misc/ - Utility scripts and instance generators
• submissions/ - Community solution submissions

References

• Cornuéjols, G., Dawande, M. (1998). A Class of Hard Small 0—1 Programs. In: Bixby, R.E., Boyd, E.A., Ríos-Mercado, R.Z. (eds) Integer Programming and Combinatorial Optimization. IPCO 1998. Lecture Notes in Computer Science, vol 1412. Springer, Berlin, Heidelberg.