Why Using CPLEX as an LP Solver Slows MIP Solves by 10×

by

Technical Postmortem: Missing CPLEX Cuts in Custom Branch-and-Bound Implementation

Summary

A production optimization system experienced significantly slower solve times after migrating from CPLEX’s native MIP solver to a custom branch-and-bound framework that used CPLEX solely as an LP solver. The custom implementation solved the same mixed-integer problems but failed to leverage CPLEX’s built-in cut generation mechanisms, resulting in 2-10x longer runtime on production workloads.

Root Cause

The root cause is architectural: CPLEX’s automatic cut separation is tightly coupled to its internal MIP solving infrastructure, not to the LP solver itself. When CPLEX solves an LP relaxation within its own branch-and-bound tree, it invokes cut generators ( Gomory, cover, flow cover, clique, etc.) as part of the MIP callback system. However, when used as a black-box LP solver via CPXlpopt or similar APIs, CPLEX has no knowledge of:

  • Which variables should be integer
  • The current node’s branching decisions
  • The global MIP context required for cut generation

The cuts are not a property of the LP solver—they are a property of the MIP solver’s separation oracle.

Why This Happens in Real Systems

This design exists for sound technical reasons:

  • Cut generation requires MIP context: Valid inequalities like Gomory cuts depend on the fractional solution’s basis matrix and the integrality restrictions. A pure LP solver has no concept of “integrality.”
  • Performance isolation: CPLEX’s LP solver is optimized for raw speed on continuous problems; adding MIP logic would degrade its performance as a general-purpose LP solver.
  • Separation oracle independence: Cut generation is computationally expensive and should only run when beneficial—typically within a MIP search, not on every LP solve.

Real-World Impact

The impact on production systems is substantial:

  • 2-10x slower solve times on medium-sized MIPs (100-10,000 variables)
  • Exponential blowup on combinatorial problems where cuts provide critical bound improvements
  • Memory pressure from deeper branch-and-bound trees without cut tightening
  • Infeasible production runs where the custom solver exceeded time limits that the native CPLEX MIP solver completed within

Example or Code (if necessary and relevant)

The following demonstrates the difference between using CPLEX as a MIP solver versus as a standalone LP solver:

// Using CPLEX's native MIP solver (cuts automatic)
CPXENVptr env = CPXopenCPLEX(envstatus);
CPXLPptr mip = CPXcreateprob(env, &status, "production_model");
CPXcopylp(env, mip, numcols, numrows, ...);
CPXsetintparam(env, CPX_PARAM_MIPEMPHASIS, CPX_MIPEMPHASIS_BALANCED);
CPXmipopt(env, mip);  // Cuts generated automatically

// Using CPLEX as LP solver in custom B&B (NO cuts)
CPXLPptr lp = CPXcreateprob(env, &status, "node_relaxation");
CPXcopylp(env, lp, numcols, numrows, ...);
CPXlpopt(env, lp);  // Pure LP solve, no cuts generated

How Senior Engineers Fix It

Senior engineers address this through several proven approaches:

  • Use CPLEX callbacks: Implement CPXcallback or legacy callbacks to inject custom cuts into CPLEX’s MIP search while maintaining the custom branching strategy
  • Implement custom cut separation: Write explicit separation oracles for problem-specific cuts (knapsack covers, valid inequalities) and add them manually via CPXaddrows or CPXaddcuts
  • Hybrid architecture: Solve the root node with native CPLEX MIP to generate cuts, then export the cut pool and reuse in custom B&B
  • Leverage CPLEX’s lazy constraint callback: For problems with logical constraints, use lazy constraints to replicate cut-like behavior

Why Juniors Miss It

Junior engineers commonly overlook this issue because:

  • API misleadingness: The CPXlpopt function appears to solve “the same problem” but lacks MIP context
  • Documentation gap: Cut generation is documented under MIP parameters, not LP parameters, creating confusion
  • Assumption of modularity: Engineers assume MIP components (branching, cuts, preprocessing) are independently accessible
  • Testing gap: Small test cases often solve fine without cuts; the performance cliff appears only at production scale

Leave a Comment