A comprehensive collection of advanced optimization algorithms for solving NP-complete problems in Java.
Features • Structure • Quick Start • Testing
NP-Optimization is a complete implementation of advanced optimization algorithms designed to tackle NP-complete problems. The repository covers techniques ranging from dynamic programming and branch-and-bound to constraint programming and decision diagrams. Each implementation is paired with comprehensive unit tests and detailed LaTeX reports.
- Dynamic Programming (DP) — Optimal substructure exploitation
- Branch-and-Bound (BnB) — Tree search with pruning strategies
- Linear Programming (LP) — Simplex and relaxation methods
- Local Search (LS) — Neighborhood-based heuristics
- Constraint Programming (CP) — Declarative constraint solving
- Decision Diagrams (MDD) — Multi-valued decision diagram optimization
| Category | Implementations |
|---|---|
| TSP | Traveling Salesman Problem solvers, Held-Karp bounds |
| Knapsack | 0/1 Knapsack, Multi-dimensional variants |
| Scheduling | Job scheduling, Resource allocation |
| Puzzles | Magic Square, Knight's Tour, Killer Sudoku |
| Graphs | One-Tree bounds, Cheapest Incident edges |
NP-Optimization/
├── src/
│ ├── main/java/
│ │ ├── branchandbound/ # Branch-and-Bound algorithms
│ │ ├── constraintprogramming/ # CP solver and problems
│ │ ├── dynamicprogramming/ # DP implementations
│ │ ├── linearprogramming/ # LP methods
│ │ ├── localsearch/ # Local Search heuristics
│ │ ├── mdd/ # Decision Diagrams
│ │ └── util/ # Shared utilities
│ │
│ └── test/java/ # Unit tests (mirrors main/)
│
├── data/ # Test instances and benchmarks
├── tex/ # LaTeX reports and figures
└── pom.xml # Maven configuration
| Module | Description |
|---|---|
| Branch-and-Bound | TSP solver, One-Tree/Held-Karp lower bounds, pruning strategies |
| Constraint Programming | Domain propagation, Sum/LessOrEqual constraints, puzzle solvers |
| Dynamic Programming | Optimal TSP, state-space exploration |
| Linear Programming | LP relaxations, optimization formulations |
| Local Search | Neighborhood search, improvement heuristics |
| MDD | Relaxed/restricted diagrams, sequential solving |
- Java 9+
- Maven 3.6+
- Git
# Clone the repository
git clone https://github.com/mathisdelsart/NP-Optimization.git
cd NP-Optimization
# Build the project
mvn compile
# Run fast tests
mvn test# Run all tests (including slow ones)
mvn test -Pslow-testsComprehensive test suite covering all optimization algorithms.
# Run fast tests only
mvn test# Run all tests (including slow/exhaustive)
mvn test -Pslow-tests
# Run tests for a specific module
mvn test -Dtest="branchandbound.*"# Run a specific test class
mvn test -Dtest="BranchAndBoundTSPTest"LaTeX reports for each project are available in the tex/ directory:
- Dynamic Programming — DP formulations and complexity analysis
- Branch-and-Bound — Lower bound techniques and pruning
- Linear Programming — LP relaxations and formulations
- Local Search — Neighborhood definitions and convergence
- Constraint Programming — Propagation and search strategies
- Decision Diagrams — MDD construction and optimization
 | Mathis DELSART |
This project is developed for academic purposes as part of university coursework.
Built for LINFO2266 - Advanced Algorithms for Optimization @ UCLouvain (Universite catholique de Louvain).