Convex-Relaxation

This repository contains Julia code for studying convex relaxations of box-constrained quadratic programming (BoxQP) problems. The project is organized as a small research codebase: it defines several optimization models, runs those models on benchmark instances, stores the numerical results, and produces figures from the recorded data.

At a high level, the workflow is:

1. load BoxQP benchmark instances,
2. solve them with several relaxations / solver configurations,
3. save experiment outputs to CSV-style data files,
4. generate plots and performance profiles from those outputs.

What problem is this code studying?

The code focuses on box-constrained quadratic programs, where the decision variables are constrained to lie in a box (in this repo, typically 0 <= x <= 1) and the objective is quadratic. These problems can be difficult to solve directly, so the repository compares several relaxation strategies, including:

• the original nonlinear quadratic program,
• an RLT relaxation,
• a DNN / SDP-style relaxation,
• a DNN-SOCP relaxation solved with an iterative cutting-plane style procedure,
• a time-limited SDP variant.

Repository structure

The repository is intentionally simple and centered around a few scripts:

• Main.jl
  Main experiment driver. It reads instance files, calls the models defined in Relaxation Models.jl, times the runs, and writes result tables such as EXP_Original_problem.csv, EXP_RLT_problem.csv, EXP_DNP_problem.csv, EXP_SOCP_problem.csv, and EXP_DNPTimLim_problem.csv.

• Relaxation Models.jl
  Core model definitions. This file contains the JuMP implementations of:

  • the original box-constrained quadratic program,
  • the RLT relaxation,
  • the doubly-nonnegative / semidefinite relaxation,
  • the SOCP-based approximation with iterative constraint generation,
  • the time-limited semidefinite relaxation.

• Plots.jl
  Plotting / post-processing script. It reads the saved experiment outputs and generates figures such as solver performance profiles and iteration-process plots.

• Results for Solvers.in
  Numerical solver timing data used for the performance-profile plots.

• Records for Iterations.csv
  Detailed iteration history for the SOCP-based cutting-plane method, used for the plotting script.

Main ideas in the code

1. Baseline nonlinear solve

The function QP(...) solves the original box-constrained quadratic program directly using Ipopt.

2. Convex relaxation models

The repo then constructs lifted relaxations using variables such as x and X, and compares multiple formulations:

• RLT relaxation solved with Mosek,
• DNN / SDP relaxation solved with Mosek,
• SOCP approximation solved with CPLEX.

3. Iterative SOCP-based approximation

One of the most important parts of the code is the SOCP-based method. After solving an initial relaxation, it checks the eigenvalues of X - xx'. If the matrix is not sufficiently positive semidefinite, the code adds additional second-order cone constraints derived from the eigenvectors associated with negative eigenvalues, then re-solves the model. This repeats until one of the stopping conditions is reached:

• the minimum eigenvalue is above a tolerance,
• the iteration limit is reached,
• the time limit is reached.

Expected input data

The experimental instances are not fully generated inside this repository. The README in the original project references benchmark data from Prof. Burer's BoxQP instance repository:

• sburer/BoxQP_instances: https://github.com/sburer/BoxQP_instances

Main.jl expects those instance files to exist in a relative path like:

• ./Experiments/BoxQP_instances-master/basic/

There are also commented alternatives in the code for:

• ./Experiments/BoxQP_instances-master/extended/
• ./Experiments/BoxQP_instances-master/extended2/

Julia packages / solver backends

The scripts use the following Julia packages and solver interfaces:

• JuMP
• Ipopt
• MosekTools
• Gurobi
• CPLEX
• CSV
• DataFrames
• DelimitedFiles
• LinearAlgebra
• TickTock
• BenchmarkProfiles
• Plots
• LazyStack

Some of these rely on commercial solvers, so you may need local solver installations and licenses before running the experiments successfully.

Typical workflow

Run experiments

Use Main.jl to run the optimization experiments over the benchmark set and write output files.

Generate figures

Use Plots.jl after the result files are available. It reads the stored data and creates plot PDFs for comparison and iteration analysis.

Good starting points for new readers

If you are new to the project, the best reading order is:

1. This README for the overall picture.
2. Relaxation Models.jl to understand the actual mathematical models.
3. Main.jl to see how experiments are run in batch.
4. Plots.jl to understand how the saved results are analyzed.

Notes for contributors / future improvements

A few things that could make the repo easier to reproduce and extend in the future:

• adding a Project.toml / Julia environment file,
• documenting the exact format of the benchmark instance files,
• documenting the schema of the generated CSV outputs,
• parameterizing instance paths and output locations,
• refactoring repeated experiment loops in Main.jl into reusable helper functions.

Summary

In short, this repository is a research-oriented Julia implementation for comparing convex relaxation approaches for BoxQP instances. If you want to understand the project quickly, focus on:

• the model definitions in Relaxation Models.jl,
• the experiment orchestration in Main.jl,
• the result visualization in Plots.jl.