Benders Decomposition in XpressMP

2026-01-15 · Source: OR in an OB World · Field: Technology & Digital — Artificial Intelligence & Machine Learning, Software Development & Engineering · Depth: Advanced, medium

Summary

This article details the implementation of Benders decomposition using the Java API for FICO's XpressMP solver, specifically for a fixed-cost transportation problem. The author adapted existing Java code, previously used with CPLEX, to XpressMP, highlighting challenges encountered due to XpressMP's design and sparse Java API documentation. The implementation focuses on "one tree Benders," utilizing callbacks within the master problem. Key aspects discussed include the formulation involving binary warehouse opening variables and continuous flow variables, the specific `PreIntsolCallback` interface for adding cuts, and workarounds for variable naming inconsistencies within callbacks. The author also addresses thread safety considerations, noting that XpressMP's design provides problem copies to each thread but initially caused crashes when printing cuts in a multi-threaded environment, a problem resolved by the variable naming workaround.

Key takeaway

For AI Engineers or Research Scientists working with optimization problems in XpressMP, understanding the nuances of its Java API for Benders decomposition is crucial. You should anticipate challenges with callback implementation and variable naming, and be prepared to use workarounds or consult C API documentation. This approach allows for efficient problem solving, but careful debugging, especially in multi-threaded environments, is essential to avoid crashes.

Key insights

Implementing Benders decomposition in XpressMP via Java callbacks presents unique challenges and workarounds.

Principles

• "One tree Benders" uses callbacks for single-pass solution.
• XpressMP callbacks distinguish node vs. heuristic solutions.

Method

Implement `XpressProblem.CallbackAPI.PreIntsolCallback` in the master problem to add Benders cuts, accepting node solutions and rejecting heuristic solutions if infeasible or underestimating costs.

In practice

• Consult C API docs for Java API details.
• Use provided workaround for variable naming in callbacks.
• Throttle Xpress to single thread for debugging cut printing.

Topics

• Benders Decomposition
• XpressMP
• Java API
• Mathematical Optimization
• Callbacks

Best for: Software Engineer, Research Scientist, AI Engineer

Related on AIssential

• Queueing Cuts in XpressMP — A cut queue can enable Benders decomposition to utilize heuristic solutions for cut generation in XpressMP.
• Benders’ Decomposition 101: How to Crack Open a Stochastic Program That’s Too Big to Swallow Whole — Benders' decomposition tackles large stochastic programs by separating first-stage decisions from scenario-specific recourse using iterative cuts.
• XpressMP Java Examples — FICO XpressMP's Java API is transitioning to an object-oriented design, simplifying cut management during presolve.
• Interpreting Neural Combinatorial Optimization via Evolving Programmatic Bottlenecks — EPB interprets black-box Neural Combinatorial Optimization by distilling policies into human-readable program portfolios.
• GraphMend: Code Transformations for Fixing Graph Breaks in PyTorch 2 — High-level code transformation before execution effectively eliminates PyTorch 2 graph breaks, improving performance.
• CuTeGen: An LLM-Based Agentic Framework for Generation and Optimization of High-Performance GPU Kernels using CuTe — CuTeGen iteratively refines GPU kernels using CuTe abstraction and delayed profiling, achieving competitive performance.

Open in AIssential →

Editorial summary, takeaway, and curation by AIssential. Original article published by OR in an OB World.