Cutting Slack: A Toolkit for Slack-Free Quantum Combinatorial Optimization

This repository contains the official implementation for the research paper "Cutting Slack: Quantum Optimization with Slack-Free Methods for Combinatorial Benchmarks." This project provides a comprehensive Python toolkit for exploring and comparing slack-free constraint-handling techniques in quantum combinatorial optimization. It serves as a robust framework for benchmarking Lagrangian-based hybrid quantum-classical algorithms on a variety of well-known optimization problems.

The library allows users to solve the following problems:

• Multi-Dimensional Knapsack Problem (MDKP)

• Maximum Independent Set (MIS)

• Quadratic Assignment Problem (QAP)

It implements a suite of classical Lagrangian dual optimization methods to find optimal penalty parameters (lambda), which are then used to formulate a relaxed QUBO solved by a quantum algorithm (VQE or CVaR-VQE).

Classical Methods Implemented:

• Dual Averaging

• Stochastic Subgradient

• Bundle Method

• Cutting Plane

• Augmented Lagrangian

Project Structure

The codebase is organized into a modular library for ease of use, extension, and maintenance.

cutting-slack/
├── data/
│   ├── mdkp_instances/
│   ├── mis_instances/
│   └── qap_instances/
├── results/
│   ├── mdkp_benchmark_results.txt
│   └── ... (other result files)
├── src/
│   └── quantum_constraint_solver/
│       ├── __init__.py
│       ├── algorithms/
│       │   ├── classical_optimizers.py
│       │   ├── vqe_solver.py
│       │   └── cvar_vqe_solver.py
│       ├── problems/
│       │   ├── base_problem.py
│       │   ├── mdkp.py
│       │   ├── mis.py
│       │   └── qap.py
│       └── utils/
│           ├── instance_loader.py
│           └── logger.py
├── mdkp_runner.py          # Main experiment script for MDKP
├── mis_runner.py           # Main experiment script for MIS
├── qap_runner.py           # Main experiment script for QAP
├── README.md               # This file
└── requirements.txt        # Project dependencies

Installation

1. Clone the repository:

   git clone https://github.com/SMU-Quantum/cutting_slack
   cd cutting-slack

2. Create and activate a virtual environment (recommended):

   python -m venv venv
   source venv/bin/activate  # On Windows, use `venv\Scripts\activate`

3. Install the required dependencies from the provided file:

   pip install -r requirements.txt

   Note: qiskit-optimization may require a commercial solver like CPLEX for some classical functionality. Ensure it is installed and configured if needed.

How to Run Experiments

This project uses a script-driven approach for running benchmarks. Each supported problem has its own dedicated runner script in the root directory.

Running the MDKP Benchmark

To run all classical methods against all MDKP instances in the data/mdkp_instances/ directory:

python mdkp_runner.py

Running the MIS Benchmark

To run all classical methods against all MIS instances in the data/mis_instances/ directory:

python mis_runner.py

Running the QAP Benchmark

To run the implemented methods against all QAP instances in data/qap_instances/:

python qap_runner.py

Command-Line Options

All runner scripts support the following command-line arguments for customization:

• --instance_dir: Specify a different directory for problem instances.

• --results_file: Specify a different output file for the results.

• --solver: Choose the quantum solver. Options: vqe (default) or cvar_vqe.

• --alpha: If using cvar_vqe, specify the alpha value (e.g., --alpha 0.25).

Example (running CVaR-VQE on MDKP):

python mdkp_runner.py --solver cvar_vqe --alpha 0.25

Viewing Results

The results of each run are saved to a human-readable text file in the results/ directory. Each experiment is clearly delimited and contains all relevant parameters, timings, and final solution metrics.

================================================================================
[ EXPERIMENT DETAILS ]

Problem Type                  : MDKP
Instance Name                 : hp1.dat
Known Optimal Value           : 3418

[ CLASSICAL METHOD ]

Method                        : dual_averaging
Parameters                    : {"max_iter": 100, "alpha": 0.1}
Classical Duration (s)        : 0.0070
Best Dual Value               : 3508.4111

[ HYBRID QUANTUM RESULT ]

Total Duration (s)            : 15.3450
Final Objective Value         : 3350.0
Is Feasible                   : True
Optimality Gap (%)            : 8.01%
Solution Probability          : 0.0451
Solution Bitstring            : 1101001001100110101001111111
--------------------------------------------------------------------------------

📄 Citation

If you use this code in your research, please cite the original paper:

@article{sharma2025cutting,
  title={Cutting Slack: Quantum Optimization with Slack-Free Methods for Combinatorial Benchmarks},
  author={Sharma, Monit and Lau, Hoong Chuin},
  journal={arXiv preprint arXiv:2507.12159},
  year={2025}
}