Optimization Project KPC

Implementation and experimental evaluation of $S_{i}$, a branching heuristic guided by the structure of the conflict graph for the Knapsack Problem with Conflicts (KPC). The heuristic is compared against the classical Most Fractional rule and against the default CPLEX branching strategy.

The project solves KPC instances through exact Branch and Bound (IBM ILOG CPLEX), under two experimental layers.

Layer 1 (Isolated). $S_{i}$ versus Most Fractional, with CPLEX presolve, cuts, and primal heuristics disabled. This isolates the pure effect of the branching rule.

Layer 2 (Commercial). $S_{i}$ versus default CPLEX, with all commercial features enabled. This evaluates the practical viability of the heuristic in a production like scenario.

Repository structure

optimization-project-kpc/
├── instances/          60 synthetically generated KPC instances
├── scripts/
│   ├── generate_instances.py   Instance generation
│   └── plot_results.py         Statistical analysis and plots
├── src/
│   ├── main.cpp         Solver implementation in C++ with CPLEX
│   ├── Makefile          Build configuration for the solver
│   ├── pre_solver_results.csv    Layer 1 output, generated at runtime
│   └── post_solver_results.csv   Layer 2 output, generated at runtime
├── requirements.txt      Python dependencies
└── .gitignore
└── KnapsackProblem_Article.pdf

Requirements

IBM ILOG CPLEX Optimization Studio with Concert Technology for C++, installed and licensed. The Makefile expects the standard CPLEX installation paths. Adjust CPLEXDIR and CONCERTDIR inside the Makefile if your installation lives elsewhere.

A C++ compiler. The code relies on std::filesystem, which requires at least C++17. Check the CXXFLAGS entry in src/Makefile to confirm the standard flag actually configured for the build.

Python 3.10 or newer.

make.

CPLEX is proprietary software from IBM. This repository does not distribute the solver. A valid license, academic or commercial, is required to compile and run the project.

Installation

Clone the repository and install the Python dependencies.

git clone https://github.com/mathk32/optimization-project-kpc.git
cd optimization-project-kpc
pip install -r requirements.txt

Python dependencies

contourpy==1.3.3
cycler==0.12.1
fonttools==4.63.0
kiwisolver==1.5.0
matplotlib==3.11.0
numpy==2.5.0
packaging==26.2
pandas==3.0.3
pillow==12.2.0
pyparsing==3.3.2
python-dateutil==2.9.0.post0
seaborn==0.13.2
six==1.17.0

Instances

The 60 instances under instances/ were generated by scripts/generate_instances.py, covering 12 combinations of item count (n) and conflict graph density (delta), with 5 instances per combination.

n (items)	delta (density)
100	0.2, 0.4, 0.6, 0.8
150	0.2, 0.4, 0.6, 0.8
200	0.2, 0.4, 0.6, 0.8

To regenerate the instances, which is optional since the repository already includes the 60 instances used in the experiments:

python scripts/generate_instances.py

How to run

1. Build the solver

cd src
make

2. Run the experiments

./kpc_solver

This processes every instance under instances/, solving each one under the four configurations: Most Fractional and Si for Layer 1, default CPLEX and Si for Layer 2. Two output files are produced in src/.

pre_solver_results.csv holds the Layer 1 results. post_solver_results.csv holds the Layer 2 results.

Each row reports, per instance: item count, density, optimal profit, number of explored nodes, CPU time, and optimality status, for both methods being compared.

Note on runtime. Layer 1 disables presolve and cuts, which can lead to very large search trees on low density, larger instances (n around 200, delta around 0.2). Some of these instances may take tens of minutes to solve under this configuration.

3. Generate analysis and plots

cd ../scripts
python plot_results.py

This script reads both CSV files from src/, runs an integrity check confirming optimal profit parity between the compared methods, prints a statistical summary grouped by density range, and produces the comparative plots.

Main results

Across the 60 tested instances.

Layer	Mean node reduction	Mean time reduction
1, Isolated, $S_i$ vs Most Fractional	44.31 percent	34.90 percent
2, Commercial, $S_i$ vs default CPLEX	see article	see article

In Layer 1, $S_i$ consistently outperforms Most Fractional across all instances, with the strongest effect observed on low density graphs. In Layer 2, the advantage does not hold against default CPLEX running with all commercial features active. This is partly explained by CPLEX automatically disabling Dynamic Search whenever a Legacy Callback for branching control is registered, and partly by the intrinsic overhead of keeping a control callback active at every node. Full methodology, results, and discussion are available in the article associated with this repository.

Technologies

C++17. Used for the solver implementation and the branching callbacks.

IBM ILOG CPLEX, Concert Technology. Used for exact resolution through Branch and Bound.

Python, with pandas, matplotlib, and seaborn. Used for statistical analysis and visualization of the results.