MiniZinc Constraint Programming & Optimization Suite

A production-grade collection of Constraint Programming (CP) and Discrete Optimization models implemented in MiniZinc, coupled with an interactive multi-parameter Python CLI runner. Designed to showcase foundational algorithms, global constraint propagation, symmetry breaking, and mixed-integer resource allocation.

---

📌 Executive Summary & Architecture

Constraint Programming (CP) and Operations Research (OR) allow developers to express high-level mathematical declarations of combinatorial problems without specifying procedural solving steps. MiniZinc compiles these declarative models (.mzn) into FlatZinc (.fzn), which is then solved using state-of-the-art backends such as Gecode, Chuffed, or CBC.

This suite demonstrates 8 benchmark problems ranging from classic Constraint Satisfaction Problems (CSPs) to complex Resource-Constrained Project Scheduling (RCPSP) and Mixed-Integer Linear Programming (MILP) facility location problems.

---

📐 Benchmark Problem Catalog & Multi-Parameter Configurations

1. 🔤 Cryptarithmetic Puzzles (models/send_more_money.mzn)

• Domain: Constraint Satisfaction Problem (CSP)
• Problem Description: Assign distinct decimal digits ($0 \dots 9$) to letters such that mathematical addition equations hold true. Leading digits cannot be zero.
• Dynamic User Parameters:
  • variant: Equation Preset Selection:
    • Variant 1: SEND + MORE = MONEY (Classic 8 letters)
    • Variant 2: FORTY + TEN + TEN = SIXTY (Famous 10 letters)
    • Variant 3: CROSS + ROADS = DANGER (Traffic safety cryptarithm)
    • Variant 4: DONALD + GERALD = ROBERT (Classic 10 letters)
• Mathematical Formulation: $$\text{alldifferent}([S, E, N, D, M, O, R, Y]), \quad S \neq 0, \quad M \neq 0$$ $$(1000S + 100E + 10N + D) + (1000M + 100O + 10R + E) = 10000M + 1000O + 100N + 10E + Y$$

---

2. ♛ N-Queens Problem (models/nqueens.mzn)

• Domain: Constraint Satisfaction Problem (CSP) & Diagonal Arithmetic
• Problem Description: Place $N$ non-attacking queens on an $N \times N$ chessboard such that no two queens share the same row, column, or diagonal.
• Dynamic User Parameters:
  • n: Chessboard size $N$ (e.g. $4, 8, 10, 12, 16$).
• Mathematical Formulation: Let $q_i \in {1 \dots N}$ denote the row position of the queen in column $i$: $$\text{alldifferent}(q)$$ $$\text{alldifferent}({q_i + i \mid i \in 1 \dots N}) \quad \text{(Main Diagonals)}$$ $$\text{alldifferent}({q_i - i \mid i \in 1 \dots N}) \quad \text{(Anti-Diagonals)}$$

---

3. 🧩 Parametric Sudoku Grid Solver (models/sudoku.mzn)

• Domain: CSP & Sub-grid Constraint Indexing
• Problem Description: Fill a partially completed $N \times N$ grid with numbers $1 \dots N$ such that every row, column, and $S \times S$ sub-grid ($S = \sqrt{N}$) contains all digits without repetition.
• Dynamic User Parameters:
  • N: Board Dimension ($N=4$ for $4 \times 4$ with $2 \times 2$ blocks, $N=9$ for $9 \times 9$ with $3 \times 3$ blocks, $N=16$ for $16 \times 16$ with $4 \times 4$ blocks).
• Mathematical Formulation: $$\forall r \in 1 \dots N: \text{alldifferent}([board[r, c] \mid c \in 1 \dots N])$$ $$\forall c \in 1 \dots N: \text{alldifferent}([board[r, c] \mid r \in 1 \dots N])$$ $$\forall br, bc \in 0 \dots S-1: \text{alldifferent}([board[S \cdot br + r, S \cdot bc + c] \mid r, c \in 1 \dots S])$$

---

4. 🎨 Graph Chromatic Coloring (models/graph_coloring.mzn)

• Domain: Discrete Optimization & Graph Theory
• Problem Description: Assign colors to vertices of a graph $G=(V, E)$ such that adjacent vertices receive different colors, while minimizing the total number of distinct colors used (the chromatic number $\chi(G)$).
• Dynamic User Parameters:
  • map_preset: Topology Preset:
    • Preset 1: 4-Country Region Map (North, South, East, West)
    • Preset 2: 6-Country European Network
    • Preset 3: 10-City Wireless Mesh Network
  • max_colors: Upper bound pencil palette limit / frequency channels.
• Mathematical Formulation: $$\text{Minimize } \chi(G) = \max_{v \in V} c(v) \quad \text{s.t.} \quad c(u) \neq c(v) \quad \forall (u, v) \in E, \quad c(v_1) = 1 \text{ (Symmetry Breaking)}$$

---

5. 🎒 0-1 Knapsack Optimization (models/knapsack.mzn)

• Domain: Discrete Optimization & Bounded Capacity Allocation
• Problem Description: Given items with weights $w_i$ and values $v_i$, select a subset of items to maximize overall value without exceeding weight capacity $C$.
• Dynamic User Parameters:
  • item_scenario: Dataset Selection:
    • Scenario 1: Camping Gear (5 Items)
    • Scenario 2: Tech Cargo Shipment (8 Items)
    • Scenario 3: Treasure Chest Looting (10 Items)
  • capacity: Backpack / container weight capacity limit (in kg).
• Mathematical Formulation: $$\text{Maximize } \sum_{i=1}^n x_i \cdot v_i \quad \text{s.t.} \quad \sum_{i=1}^n x_i \cdot w_i \le C, \quad x_i \in {0, 1}$$

---

6. 🚗 Traveling Salesperson Problem - TSP (models/tsp.mzn)

• Domain: Operations Research & Subtour Elimination
• Problem Description: Determine the shortest tour visiting $N$ cities exactly once and returning to the origin city.
• Dynamic User Parameters:
  • route_preset: Delivery Network Scenario:
    • Preset 1: 4-Depot Local Route
    • Preset 2: 6-City Regional Network
    • Preset 3: 8-Capital European Tour (Berlin, Paris, Vienna, Rome, Madrid, Amsterdam, Prague, Warsaw)
  • origin_city: Origin / Departure City ID ($1 \dots N$).
• Mathematical Formulation: Let $succ[i] \in {1 \dots N}$ represent the successor city of city $i$: $$\text{circuit}(succ) \quad \text{(Enforces a single Hamiltonian cycle)}$$ $$\text{Minimize } \sum_{i=1}^N \text{distance}[i, succ[i]]$$

---

7. 🏭 Job-Shop Resource Scheduling (models/jobshop.mzn)

• Domain: Resource-Constrained Project Scheduling (RCPSP)
• Problem Description: Schedule $M$ jobs across $N$ machines. Each job consists of an ordered sequence of tasks with fixed durations and machine requirements. No machine can process multiple tasks simultaneously.
• Dynamic User Parameters:
  • workload_preset: Factory Workload Configuration:
    • Preset 1: Small Workshop ($3 \text{ Jobs} \times 3 \text{ Machines}$)
    • Preset 2: High-Tech Assembly Line ($4 \text{ Jobs} \times 4 \text{ Machines}$)
    • Preset 3: Custom Order Manufacturing ($5 \text{ Jobs} \times 4 \text{ Machines}$)
  • horizon_limit: Shift time limit / horizon bound (in hours).
• Mathematical Formulation: $$\text{Precedence: } start[i, j] + d_{i, j} \le start[i, j+1]$$ $$\text{Disjunctive: } (start[i_1, j_1] + d_{i_1, j_1} \le start[i_2, j_2]) \lor (start[i_2, j_2] + d_{i_2, j_2} \le start[i_1, j_1])$$ $$\text{Minimize Makespan } C_{\max} = \max_{i} (start[i, \text{final}] + d_{i, \text{final}})$$

---

8. 🏢 Warehouse & Facility Location (models/warehouse_location.mzn)

• Domain: Mixed-Integer Optimization & Logistics Supply Chain
• Problem Description: Decide which warehouses to open (each with fixed setup cost $f_w$ and capacity $K_w$) and assign customer demands to open warehouses to minimize total fixed + transport costs.
• Dynamic User Parameters:
  • network_scenario: Supply Chain Network:
    • Scenario 1: National Supply Chain ($4 \text{ Warehouses}, 5 \text{ Customer Hubs}$)
    • Scenario 2: Global Distribution ($6 \text{ Warehouses}, 8 \text{ Customer Regions}$)
  • max_open_warehouses: Maximum open warehouses allowed.
• Mathematical Formulation: $$\text{Minimize } \sum_{w=1}^W open[w] \cdot f_w + \sum_{c=1}^C transport_cost[supplier[c], c]$$ $$\text{s.t.} \quad open[supplier[c]] = 1 \quad \forall c, \quad \sum_{w=1}^W open[w] \le \text{max_open_warehouses}$$

---

📊 Benchmark Summary Matrix

Problem Model	Category	Objective	Dynamic User Inputs	Key Constraints	Complexity
send_more_money.mzn	CSP	Satisfy	Puzzle Equation Variant ($1 \dots 4$)	alldifferent, Positional Arithmetic	NP-Complete
nqueens.mzn	CSP	Satisfy	Board Size $N$ ($4, 8, 10, 12, 16$)	alldifferent, Diagonal Offsets	NP-Complete
sudoku.mzn	CSP	Satisfy	Grid Dimension $N$ ($4 \times 4, 9 \times 9, 16 \times 16$)	Sub-grid Indexing, alldifferent	NP-Complete
graph_coloring.mzn	Discrete Optimization	Minimize $\chi(G)$	Topology Preset ($1 \dots 3$), Max Colors	Adjacency, Symmetry Breaking	NP-Hard
knapsack.mzn	Discrete Optimization	Maximize Value	Dataset Scenario ($1 \dots 3$), Weight Cap	Linear Capacity Inequality	NP-Hard
tsp.mzn	Operations Research	Minimize Distance	Tour Network ($1 \dots 3$), Origin City	circuit (Subtour Elimination)	NP-Hard
jobshop.mzn	Scheduling	Minimize Makespan	Workload Preset ($1 \dots 3$), Time Horizon	Task Precedence, Disjunctive Machine	NP-Hard
warehouse_location.mzn	Mixed-Integer / Logistics	Minimize Total Cost	Network Scenario ($1 \dots 2$), Max Open Limit	Capacity Bounds, Open Activation	NP-Hard

---

🛠️ Prerequisites & Setup

1. Install MiniZinc CLI & IDE

MiniZinc CLI is required to compile and solve models. On Windows:

# Install via Winget
winget install MiniZinc.MiniZincIDE

Or run the provided automated setup script:

.\setup_environment.ps1

2. Python Environment Setup

Install Python dependencies for programmatic solver integration:

pip install -r requirements.txt

---

🚀 Interactive CLI Runner & Usage Guide

The repository includes a launcher script (run_model.py) featuring an interactive menu and CLI argument parser.

Option 1: Interactive Menu Mode

Run run_model.py without arguments to enter interactive mode:

python run_model.py

Double-clicking run_example.bat on Windows launches the interactive runner directly.

Interactive Walkthrough Example (Graph Coloring):

=======================================================================
      MiniZinc Constraint Programming & Optimization Suite            
=======================================================================
Available Benchmark Models:

  [CSP - Constraint Satisfaction Problems]
    [1] Cryptarithmetic Puzzles (SEND+MORE=MONEY, DONALD+GERALD=ROBERT, etc.)
    [2] N-Queens Problem (Chessboard Diagonal Constraints)
    [3] Parametric Sudoku Solver (Dynamic Board Size N: 4x4, 9x9, 16x16)
    [4] Graph Chromatic Coloring (Map Topologies & Frequency Allocation)

  [Optimization & Operations Research]
    [5] 0-1 Knapsack Optimization (Camping, Tech, Treasure Scenarios)
    [6] Traveling Salesperson Problem (Local, Regional, European Tours)
    [7] Job-Shop Resource Scheduling (Workshop, Assembly, Factory Lines)
    [8] Warehouse Location & Facility Allocation (National & Global Networks)
=======================================================================
Select an example to run [1-8] (default: 4): 4

=======================================================================
  Launching: Graph Chromatic Coloring (Map & Frequency Allocation)
  Category:  Discrete Optimization & Graph Theory
=======================================================================
Select map topology preset [1: 4-Country Region Map, 2: 6-Country European Net, 3: 10-City Wireless Mesh] [default: 2]: 3
[+] Parameter 'map_preset' set to 3
Enter max allowed color count (pencil palette limit / frequency channels) [default: 4]: 4
[+] Parameter 'max_colors' set to 4

[+] Executing graph_coloring.mzn with Gecode Solver...

---

Option 2: Direct Command Line Invocations

You can bypass interactive prompts by supplying model ID and positional arguments directly:

# 1. Run Cryptarithmetic DONALD + GERALD = ROBERT puzzle
python run_model.py 1 4

# 2. Run 12-Queens Problem
python run_model.py 2 12

# 3. Run 4x4 Sudoku Solver
python run_model.py 3 4

# 4. Run Graph Coloring on 10-City Mesh Network with 4 Max Colors
python run_model.py 4 3 4

# 5. Run Knapsack Treasure Chest Scenario (10 items) with 20 kg capacity
python run_model.py 5 3 20

# 6. Run 8-Capital European Tour TSP starting from City 1
python run_model.py 6 3 1

# 7. Run Job-Shop High-Tech Assembly Line (4x4) with 30-hour horizon
python run_model.py 7 2 30

# 8. Run Warehouse Location Global Distribution with max 6 open warehouses
python run_model.py 8 2 6

---

📁 Repository Structure

MiniZinc-Optimization-Suite/
├── models/
│   ├── send_more_money.mzn      # Cryptarithmetic Puzzles (4 Variants)
│   ├── nqueens.mzn              # N-Queens CSP with dynamic N
│   ├── sudoku.mzn               # Parametric Sudoku Solver (4x4, 9x9, 16x16)
│   ├── graph_coloring.mzn       # Graph Chromatic Coloring (3 Topologies)
│   ├── knapsack.mzn             # 0-1 Knapsack Optimization (3 Scenarios)
│   ├── tsp.mzn                  # TSP Circuit Routing (3 Networks)
│   ├── jobshop.mzn              # Job-Shop Makespan Scheduling (3 Workloads)
│   └── warehouse_location.mzn   # Capacitated Warehouse Allocation (2 Networks)
├── run_model.py                 # Multi-parameter Interactive & CLI launcher
├── run_example.bat              # Batch runner shortcut
├── setup_environment.ps1        # Automated setup script
├── requirements.txt             # Python dependencies
├── LICENSE                      # MIT License
└── README.md                    # Detailed Documentation

---

👤 Author & License

• Author: Maximilian Reitinger (MaxReit-dev)
• License: MIT License