Indigenous GPU-Accelerated Optimization Solver (Sovereign Alternative to Express / CEPLEX)

1. Executive Snapshot

Summary

India's critical industrial and strategic sectors—including petroleum refining, petrochemicals, power grids, logistics, and defense—depend almost exclusively on foreign commercial mathematical optimization solvers such as IBM ILOG CPLEX, Gurobi, and FICO Xpress [PS, KNOWN]. These proprietary engines control high-stakes decisions like refinery crude blending, production scheduling, and supply chain allocation, creating foreign software lock-in, high recurring licensing costs, and national security vulnerabilities [PS, INFERENCE]. While open-source CPU solvers (such as COIN-OR CBC, HiGHS, and SCIP) exist, they lag on large-scale mixed-integer industrial models and lack native GPU acceleration for massive sparse linear algebra [PS, RESEARCHED]. This dossier details the architecture, technical roadmap, and implementation strategy for building an Indigenous GPU-Accelerated Optimization Solver Core from mathematical first principles [PS]. Built in modern C++20 and CUDA, the system combines a CPU-based multi-threaded Branch-and-Cut / Presolve framework with a GPU-accelerated linear algebra engine utilizing restarted Primal-Dual Hybrid Gradient (PDHG) and Interior Point Methods (IPM) [INFERENCE, RESEARCHED]. Designed to handle ill-conditioned, highly degenerate, and sparse industrial constraints from Mangalore Refinery and Petrochemicals Limited (MRPL) and benchmarked against MIPLIB 2017 and Netlib LP, this project establishes a sovereign foundation for Indian mathematical optimization software [PS, RESEARCHED].

Metadata Table

Fundamental System Objective

To build a sovereign, numerically stable, C++/CUDA mathematical optimization solver core from scratch that leverages GPU acceleration to solve industrial-scale Linear Programming (LP), Mixed-Integer Linear Programming (MILP), and Quadratic Programming (QP) models with performance competitive with commercial solvers [PS, INFERENCE].

2. Problem Deconstruction

Extracting explicit and implied requirements from the source text:

1. Requirement 2.1 (Sovereign Engine Foundation): Build the solver core entirely from scratch using mathematical foundations, without wrapping or building upon existing open-source solver engines (e.g., COIN-OR CBC, HiGHS, GLPK, SCIP) [PS].

   • Interpretation: The core LP/MILP/QP numerical algorithms, matrix representation, presolver, and branch-and-cut tree must be custom C++/CUDA code [PS, INFERENCE]. External general-purpose linear algebra primitives (e.g., SuiteSparse or NVIDIA cuSPARSE/cuBLAS) may be used for low-level matrix routines, but solver orchestration must be native [INFERENCE, ASSUMPTION].
   • Implementation Implication: Requires writing custom data structures for Sparse Matrix Compressed Sparse Column/Row (CSC/CSR), custom Simplex/IPM/PDHG implementations, and custom Branch-and-Bound management [INFERENCE].
   • Confidence: [PS]

2. Requirement 2.2 (Initial Problem Class Support): Support Linear Programming (LP), Mixed-Integer Linear Programming (MILP), and Quadratic Programming (QP) [PS].

   • Interpretation: The solver must accept continuous, binary, integer, and quadratic objective/constraint formulations [PS].
   • Implementation Implication: Engine needs standard LP algorithms (Revised Simplex / Interior Point / PDHG), MILP tree search (Branch-and-Bound, Cutting Planes, Primal Heuristics), and QP extensions (active set or barrier for convex quadratic objectives) [INFERENCE, RESEARCHED].
   • Confidence: [PS]

3. Requirement 2.3 (Extensible Architecture): Design a modular solver architecture capable of future expansion to Mixed-Integer Quadratic Programming (MIQP), Nonlinear Programming (NLP), and Mixed-Integer Nonlinear Programming (MINLP) [PS].

   • Interpretation: Algorithmic interfaces must decouple problem representation, linear relaxations, cut generators, and local search routines [INFERENCE].
   • Implementation Implication: Object-oriented C++ core with clean abstraction layers for ProblemMatrix, RelaxationSolver, CutGenerator, and NodeSelector [INFERENCE].
   • Confidence: [PS]

4. Requirement 2.4 (Algorithmic Rigor): Implement core algorithms including Revised Simplex and Interior-Point Methods (IPM) for continuous optimization, combined with Branch-and-Bound, Branch-and-Cut, Cutting Planes, Presolve, Primal Heuristics, and advanced Node Selection for mixed-integer models [PS].

   • Interpretation: Full-spectrum solver pipeline incorporating preprocessing matrix reductions, continuous relaxations, tree search, and cut generation [PS, INFERENCE].
   • Implementation Implication: Must build presolve reductions (row/col singletons, bound propagation, dual fixing), Gomory mixed-integer cuts, knapsack cover cuts, and heuristics (Feasibility Pump, RINS) [INFERENCE, RESEARCHED].
   • Confidence: [PS]

5. Requirement 2.5 (GPU & Multi-Core Acceleration): Exploit sparse matrix techniques, efficient numerical linear algebra, multi-core CPU parallelization, and GPU acceleration where measurable benefits are demonstrated [PS].

   • Interpretation: Memory bandwidth-intensive operations (e.g., Sparse Matrix-Vector Multiplications SpMV, parallel primal-dual gradient iterations, parallel primal heuristics) should be offloaded to CUDA kernels [INFERENCE, RESEARCHED].
   • Implementation Implication: Implement CUDA SpMV and parallel vector updates for first-order LP methods (e.g., PDHG/cuPDLP paradigms) and multi-threaded CPU Branch-and-Bound for tree management [INFERENCE, RESEARCHED].
   • Confidence: [PS]

6. Requirement 2.6 (Industrial Benchmark Standards): Demonstrate solution quality and computational performance against recognised benchmark sets including MIPLIB, Netlib LP, Mittelmann benchmark sets, and QPLIB [PS].

   • Interpretation: Performance must be objectively evaluated against state-of-the-art commercial (CPLEX/Gurobi) or open-source (HiGHS) solvers on standard MPS/LP benchmark files [PS, RESEARCHED].
   • Implementation Implication: Implement standard MPS/LP parser and automated benchmark evaluation scripts computing shifted geometric mean solution times and optimality gaps [INFERENCE, RESEARCHED].
   • Confidence: [PS]

7. Requirement 2.7 (Numerical Stability & Industrial Scale): Consistently deliver optimal/near-optimal solutions for models with thousands to millions of variables/constraints, including highly degenerate models, ill-conditioned matrices, and weak LP relaxations [PS].

   • Interpretation: High tolerance for floating-point issues; must incorporate scaling (Ruiz/Equilibration), perturbation techniques, and iterative refinement [INFERENCE, RESEARCHED].
   • Implementation Implication: Exact quad-precision or iterative refinement passes for ill-conditioned basis matrices; robust pivoting rules in Simplex [INFERENCE].
   • Confidence: [PS]

8. Requirement 2.8 (Target Industrial Use Cases): Focus application scope on refinery scheduling, crude blending, process optimization, production planning, supply chain management, and power system dispatch [PS].

   • Interpretation: Domain-specific modeling examples from refinery operations (e.g., pooling problems, crude blending MILP approximations) must be included [PS, INFERENCE].
   • Implementation Implication: Develop open-source synthetic case studies representing MRPL crude oil distillation, blending, and multi-period distribution scheduling [INFERENCE].
   • Confidence: [PS]

9. Requirement 2.9 (CLI/API Priority Over GUI): Provide a robust optimization engine with a basic C++/Python API or Command-Line Interface (CLI); a polished GUI is explicitly not required [PS].

   • Interpretation: UI design efforts should be zero; energy must be directed 100% to backend algorithms, linear algebra, and performance [PS, INFERENCE].
   • Implementation Implication: C++ static/dynamic library, C-API, Python bindings (pybind11), and a standalone CLI executable accepting .mps and .lp files [INFERENCE].
   • Confidence: [PS]

3. Stakeholders & User Needs

4. Requirements Traceability

5. Constraints & Environment Realities

1. Hardware & Compute Heterogeneity:

   • Indian PSU server environments range from legacy multi-core x86 CPUs to workstation GPUs (e.g., NVIDIA RTX 4090, A100, H100) and emerging indigenous accelerators (e.g., C-DAC PARAM Rudra nodes) [INFERENCE, KNOWN].
   • Constraint: System must run reliably on CPU-only environments (fallback mode) and dynamically detect/enable GPU acceleration when CUDA capabilities are present [INFERENCE].

2. Air-Gapped Operational Environments:

   • Refinery control rooms and defense installations operate in strictly air-gapped, offline networks without cloud access [PS, INFERENCE].
   • Constraint: Zero external runtime API or cloud license check dependencies. The solver dynamic library must execute completely offline [INFERENCE].

3. Numerical Precision & Ill-Conditioning:

   • Refinery pooling and crude blending involve non-linear property blending approximated by MILPs, producing constraint matrices with coefficients spanning several orders of magnitude ($10^{-6}$ to $10^{7}$), causing severe numerical instability in naive solvers [PS, RESEARCHED].
   • Constraint: Double-precision (f64) floating-point arithmetic is mandatory; critical basis factorizations require numerical pivoting and quadrupled precision (f128 or double-double) fallback passes [INFERENCE, RESEARCHED].

4. Sovereignty & Open Source Intellectual Property:

   • Explicit mandate: "It shall not be built upon any existing open source solver library" [PS].
   • Constraint: Code audit strictly forbids pulling in SCIP, HiGHS, CBC, GLPK, or Cbc source code [PS]. Algorithmic techniques must be coded from textbook and academic literature primitives [PS, INFERENCE].

6. Research Questions

1. GPU Acceleration Feasibility in Linear Programming:

   • Question: Why have traditional Simplex methods struggled on GPUs, and why are first-order methods (like Restarted PDHG) or parallel interior-point matrix updates now winning on GPU architectures? [RESEARCHED]
   • Findings: Simplex relies on sequential basis changes (tableau updates), creating low arithmetic intensity unsuitable for massively parallel SIMD GPU architectures [RESEARCHED]. Restarted PDHG transforms LP into matrix-vector multiplications (SpMV), achieving up to 100x speedups on GPUs for large LPs [RESEARCHED].

2. Presolve Impact on GPU Operations:

   • Question: Does presolving remain critical when using ultra-fast GPU LP algorithms? [RESEARCHED]
   • Findings: Yes. Recent research shows presolving reduces matrix condition numbers and eliminates redundant rows, preventing GPU first-order methods from stalling on ill-conditioned bounds [RESEARCHED].

3. GPU Role in Mixed-Integer Programming (MILP):

   • Question: Can the entire Branch-and-Bound tree fit onto a GPU, or is a hybrid CPU-GPU model superior? [RESEARCHED]
   • Findings: Branch-and-Bound tree management involves complex pointer manipulation and branch decisions best suited for CPU cores [RESEARCHED]. GPUs excel at root-node LP relaxations, parallel primal heuristics (Feasibility Pump, Probing), and large sub-MIP solutions [RESEARCHED].

4. Numerical Stability Strategies for Refinery LPs:

   • Question: How do CPLEX and Gurobi prevent numerical breakdown on ill-conditioned refinery models? [RESEARCHED]
   • Findings: Through aggressive Ruiz matrix equilibration, dual presolve, Markowitz tolerance pivoting in LU factorizations, and iterative refinement [RESEARCHED].

7. Data Requirements & Sources

Categorization Breakdown

• A. Data Explicitly Mentioned: MIPLIB, Netlib LP, Mittelmann benchmark instances, QPLIB, representative refinery scheduling/crude blending models [PS].
• B. Data Required by Inference: Synthetic MPS generators for stress-testing scale (1M+ variables) [INFERENCE].
• C. Data That Must Be Collected: Publicly available MPS files downloaded into local test harness [RESEARCHED].
• D. Data That Can Be Synthetically Generated: Refinery crude blending LP/MILP matrices using Python open literature models [INFERENCE].
• E. Data That Still Needs Validation: Proprietary MRPL blend recipes and exact constraint bounds [NEEDS VALIDATION].

8. Existing Solutions & Gap Analysis

Key Strategic Gap

Existing options force Indian public sectors to choose between expensive, closed-source foreign commercial solvers (CPLEX/Gurobi) or CPU-bound open-source engines (HiGHS/CBC) that lack native GPU parallelization and strategic customization [PS, INFERENCE]. No indigenous Indian solver core exists that combines GPU-accelerated linear algebra with robust MILP branch-and-cut algorithms built from scratch [PS, INFERENCE].

9. Candidate Solution Approaches

Approach 1: CPU-Centric Multi-Threaded Solver Built from Scratch

• Mechanism: Implement C++20 Revised Dual Simplex and Barrier Interior Point Method (IPM) using SuiteSparse/Eigen for sparse Cholesky CPU factorizations, integrated with a multi-threaded CPU Branch-and-Cut tree search [INFERENCE].
• Data Requirements: Standard MPS/LP files [PS].
• Architecture: Pure C++ multi-threaded architecture utilizing OpenMP/std::thread for parallel node evaluations [INFERENCE].
• Evaluation:
  • Problem Fit: Good for small-to-medium LPs and standard MILPs [INFERENCE].
  • Accuracy Potential: Very High (Simplex provides exact basic solutions) [RESEARCHED].
  • Complexity: Medium [INFERENCE].
  • Explainability: Excellent [INFERENCE].
  • Cost: Low hardware cost (standard CPU servers) [INFERENCE].
  • Scalability: Poor for million-variable LP relaxations [RESEARCHED].
  • Hackathon Feasibility: High [INFERENCE].
  • Production Feasibility: Medium (lags commercial solvers on huge models) [PS, RESEARCHED].

Approach 2: Pure First-Order GPU LP Solver (cuPDLP-Style)

• Mechanism: Implement a GPU-native LP solver using Primal-Dual Hybrid Gradient (PDHG) with restarted step sizes and diagonal matrix scaling, entirely executing on CUDA kernels (cuSPARSE / custom CUDA) [RESEARCHED].
• Data Requirements: Standard MPS/LP files converted to GPU CSR format [INFERENCE].
• Architecture: Monolithic CUDA engine where matrix-vector operations (SpMV) happen 100% on GPU memory [RESEARCHED].
• Evaluation:
  • Problem Fit: Outstanding for massive continuous LPs (million+ variables) [RESEARCHED].
  • Accuracy Potential: Moderate (first-order methods converge to $10^{-4} - 10^{-6}$ precision, requiring crossover for exact basic solution) [RESEARCHED].
  • Complexity: High (CUDA kernel tuning, matrix scaling) [INFERENCE].
  • Explainability: Moderate [INFERENCE].
  • Cost: Requires CUDA-capable NVIDIA GPUs [INFERENCE].
  • Scalability: Extremely High for LP [RESEARCHED].
  • Hackathon Feasibility: Moderate [INFERENCE].
  • Production Feasibility: Moderate (needs CPU crossover for MILP branching) [RESEARCHED].

Approach 3: Hybrid Architecture (Recommended) — CPU Branch-and-Cut Manager + GPU First-Order LP Relaxation Engine & Parallel GPU Primal Heuristics

• Mechanism: A modular solver core where CPU handles Preprocessing/Presolve, Branch-and-Bound Tree Management, and Cutting Plane generation, while GPU offloads massive LP Relaxations (via Restarted PDHG) and GPU-accelerated Primal Heuristics (Feasibility Pump, Probing) [RESEARCHED, INFERENCE]. Includes an exact CPU Dual Simplex fallback for basis identification (Crossover) [RESEARCHED].
• Data Requirements: Standard MPS/LP/QP files [PS].
• Architecture: Heterogeneous C++/CUDA system with asynchronous CPU-GPU memory streams and dynamic hardware detection [INFERENCE].
• Evaluation:
  • Problem Fit: Perfect alignment with all explicit requirements (LP/MILP/QP, GPU acceleration, numerical stability) [PS, INFERENCE].
  • Accuracy Potential: Exceptional (Combines GPU speed with CPU exact basis crossover) [RESEARCHED].
  • Complexity: High (requires robust hybrid integration) [INFERENCE].
  • Explainability: High [INFERENCE].
  • Cost: Low-to-Medium (runs on standard workstation with single GPU) [INFERENCE].
  • Scalability: Industrial-scale (million+ variables) [PS, RESEARCHED].
  • Hackathon Feasibility: Highly feasible for MVP with core LP/MILP modules [INFERENCE].
  • Production Feasibility: Excellent [INFERENCE].

10. Recommended Approach & Why

Selection

Approach 3: Heterogeneous Hybrid Solver Architecture is selected [INFERENCE].

Justification

1. Why Approach 1 was rejected as standalone: Pure CPU solvers cannot bridge the computational performance gap on million-variable continuous relaxations without hardware acceleration [PS, RESEARCHED]. Relying solely on CPU Simplex fails the requirement to explore GPU acceleration where measurable benefits exist [PS].
2. Why Approach 2 was rejected as standalone: Pure first-order GPU LP solvers struggle to deliver exact corner-point basic solutions needed for MILP node branching and cut generation without a simplex crossover mechanism [RESEARCHED]. Furthermore, Branch-and-Bound tree logic is inherently dynamic and inefficient when forced into pure GPU SIMD execution [RESEARCHED].
3. Why Approach 3 Wins: Approach 3 leverages the distinct strengths of both hardware architectures: GPUs handle massive parallel matrix-vector products (SpMV) in first-order LP algorithms and parallel primal heuristics, while CPUs manage complex pointer-heavy Branch-and-Bound trees, cutting plane generation, and exact simplex basis factorizations [RESEARCHED, INFERENCE]. This satisfies all requirements of SIH26119 while providing a scalable, sovereign solution [PS, INFERENCE].

11. Technical Architecture

Layered Architecture Diagram

+-----------------------------------------------------------------------------------+
|                            APPLICATION / USER LAYER                               |
|   +----------------------------------+     +----------------------------------+   |
|   |   Command-Line Interface (CLI)   |     |    Python API (pybind11)         |   |
|   +----------------------------------+     +----------------------------------+   |
+-----------------------------------------------------------------------------------+
                                         |
                                         v
+-----------------------------------------------------------------------------------+
|                         INGESTION & PARSING LAYER                                 |
|   +----------------------------------+     +----------------------------------+   |
|   |    MPS Parser (Fixed/Free)       |     |     LP / QP Format Reader        |   |
|   +----------------------------------+     +----------------------------------+   |
+-----------------------------------------------------------------------------------+
                                         |
                                         v
+-----------------------------------------------------------------------------------+
|                        PREPROCESSING & PRESET LAYER                               |
|   +----------------------------------+     +----------------------------------+   |
|   | Matrix Scaling (Ruiz/Eq)         |     | Presolver (Row/Col Reductions)   |   |
|   +----------------------------------+     +----------------------------------+   |
+-----------------------------------------------------------------------------------+
                                         |
                                         v
+-----------------------------------------------------------------------------------+
|                       SOLVER CORE ORCHESTRATOR (C++)                              |
|   +---------------------------------------------------------------------------+   |
|   |               Branch-and-Cut Manager (CPU Multi-threaded)                |   |
|   |  - Node Selector (Best-Bound/DFS)    - Cut Generator (Gomory/Knapsack)   |   |
|   +---------------------------------------------------------------------------+   |
+-----------------------------------------------------------------------------------+
                       /                                   \
                      /                                     \
                     v                                       v
+-----------------------------------------+   +-------------------------------------+
|        GPU ACCELERATED ENGINE           |   |       CPU NUMERICAL ENGINE          |
|  +-----------------------------------+  |   |  +-------------------------------+  |
|  | Restarted PDHG LP Solver          |  |   |  | Dual Revised Simplex          |  |
|  |  - Custom CUDA SpMV Kernels       |  |   |  |  - LU Factorization (Markowitz)  |  |
|  |  - Parallel Step-Size Updates     |  |   |  +-------------------------------+  |
|  +-----------------------------------+  |   |  +-------------------------------+  |
|  | Parallel GPU Primal Heuristics    |  |   |  | Crossover & Exact Basis Identifier| |
|  |  - Parallel Feasibility Pump      |  |   |  +-------------------------------+  |
|  +-----------------------------------+  |   +-------------------------------------+
+-----------------------------------------+
                                         |
                                         v
+-----------------------------------------------------------------------------------+
|                         POSTSOLVING & DUAL MAPPING                                |
|   +----------------------------------+     +----------------------------------+   |
|   |   Un-presolve Variable Mapper    |     |   Optimality Certificate Check   |   |
|   +----------------------------------+     +----------------------------------+   |
+-----------------------------------------------------------------------------------+

Detailed Data-Flow Narrative

1. Ingestion: The user passes an .mps or .lp file via CLI or Python bindings [PS, INFERENCE]. The C++ parser reads the file into an in-memory sparse matrix structure (ProblemModel) [INFERENCE].
2. Presolve & Scaling: The model passes through the presolver to eliminate redundant constraints, fix singleton variables, and propagate bounds [RESEARCHED]. The resulting reduced matrix is normalized using Ruiz equilibration scaling to ensure numerical stability [RESEARCHED].
3. Problem Dispatch:
   • For Continuous LPs: The scaled sparse matrix (CSC/CSR format) is copied to GPU device memory [RESEARCHED]. The GPU Restarted PDHG solver executes thousands of parallel primal-dual matrix-vector multiplications per second until primal/dual residuals reach tolerance ($10^{-6}$) [RESEARCHED]. If an exact basic solution is requested, the candidate solution is transferred to CPU Dual Simplex for rapid Crossover basis identification [RESEARCHED].
   • For MILPs: The CPU Branch-and-Cut manager initializes the root node [INFERENCE]. The LP relaxation is solved via GPU PDHG or CPU Simplex [RESEARCHED]. Generated cuts (Gomory fractional cuts, cover cuts) are added to tighten the relaxation [INFERENCE]. Simultaneously, GPU parallel primal heuristics run in background CUDA streams to quickly find valid integer feasible solutions [RESEARCHED]. Branching decisions (strong branching / pseudocost) spawn child nodes managed in a prioritized CPU queue [INFERENCE].
4. Postsolve: Optimal variable values and dual multipliers are un-scaled, mapped back through presolve reductions to original variable indices, and written to a .sol output file or returned to the API caller [INFERENCE].

12. Technology Stack

13. AI/ML Justification

Strategic AI Analysis

While classical mathematical optimization algorithms (Simplex, IPM, Branch-and-Bound) are deterministic and exact, Machine Learning (ML) can accelerate non-critical heuristic search decisions within the solver pipeline [RESEARCHED]. Core numerical linear algebra decisions (such as basis inversions, presolve reductions, and feasibility proofs) must NOT use AI/ML to preserve 100% mathematical rigor and guarantee solution validity [PS, INFERENCE].

Evaluated AI/ML Components

Where AI Should NOT Be Used

• Presolve Matrix Reductions: Rule-based logical reductions must be exact; ML predictions here risk introducing infeasibility or changing the optimal solution space [INFERENCE].
• Basis Pivoting & Dual Simplex: Simplex pivot selections must adhere strictly to Dantzig or Steepest Edge pricing rules to guarantee dual feasibility and termination [INFERENCE].
• Optimality Gap & Certificate Verification: Optimality proofs ($c^T x = b^T y$) must be calculated via exact double-precision floating-point linear algebra [INFERENCE].

14. Data Architecture & Offline/Low-Network Design

Data Schema (Internal Solver Memory)

The solver core represents sparse linear programs in memory using a C++ structure optimized for cache locality and CUDA transfers:

struct CompressedSparseMatrix {
    int num_rows;
    int num_cols;
    int num_nonzeros;
    std::vector<int> col_pointers;     // Size: num_cols + 1
    std::vector<int> row_indices;      // Size: num_nonzeros
    std::vector<double> values;        // Size: num_nonzeros
};

struct OptimizationProblem {
    std::string problem_name;
    int num_vars;
    int num_constraints;
    std::vector<double> objective_coeffs;
    std::vector<double> lower_bounds;
    std::vector<double> upper_bounds;
    std::vector<char> constraint_senses; // 'L' (<=), 'E' (=), 'G' (>=)
    std::vector<double> rhs_values;
    CompressedSparseMatrix constraint_matrix;
    std::vector<char> variable_types;    // 'C' (Continuous), 'B' (Binary), 'I' (Integer)
    // QP Support
    CompressedSparseMatrix quadratic_objective_matrix; // Q matrix for 0.5 * x^T Q x
};

Offline & Air-Gapped Operation

• Zero Cloud Runtime: The compiled solver exists as a self-contained executable binary (indigenous_solver_cli) and a static/shared dynamic library (libindigenous_solver.so) [INFERENCE].
• Local File I/O: Reads .mps or .lp files directly from local storage; outputs .sol files containing variable assignments, objective values, and solver status certificates (OPTIMAL, INFEASIBLE, UNBOUNDED) [INFERENCE].

Low-Memory & Bandwidth Optimization

• Unified Memory Management: Uses CUDA Managed Memory (cudaMallocManaged) or pinned host memory (cudaHostAlloc) to enable asynchronous streams, overlapping CPU branch tree processing with GPU matrix-vector computations [RESEARCHED].
• Matrix Compression: Store sparse matrices in Compressed Sparse Row (CSR) / Column (CSC) formats, reducing memory footprint by up to 95% compared to dense arrays [RESEARCHED].

15. Security, Privacy & Governance

1. Refinery Intellectual Property & Proprietary Formulas:

   • Risk: Refinery constraint matrices (e.g., MRPL crude assay proportions and blend margins) contain highly sensitive commercial trade secrets [PS, INFERENCE].
   • Governance: The solver runs 100% locally on MRPL's secure on-premise infrastructure [INFERENCE]. No model data, constraint names, or numerical matrices leave local system memory [INFERENCE].

2. Supply Chain & Code Sovereign Security:

   • Risk: Foreign dependencies or closed-source binaries may introduce hidden telemetry, backdoors, or vulnerability points [PS, INFERENCE].
   • Governance: Built completely from open mathematical algorithms in clean C++/CUDA [PS]. Zero dependency on external binary blobs or foreign solver libraries [PS]. Full codebase is auditable by Indian cybersecurity authorities (CERT-In / STQC) [INFERENCE].

3. Numerical Liability & False Results:

   • Risk: Floating-point truncation errors in LP relaxations could lead to infeasible refinery production plans, causing operational shutdowns [PS, INFERENCE].
   • Governance: Incorporate an independent Solution Checker Module that verifies every returned solution vector against original, un-presolved constraints using double-precision residual verification ($|Ax - b|_\infty \le 10^{-6}$) [RESEARCHED].

16. MVP Scope (Hackathon Build)

+-----------------------------------------------------------------------------------+
|                            HACKATHON MVP BUILD SCOPE                              |
+-----------------------------------------------------------------------------------+
|  MUST BUILD (Core Value Proposition)                                              |
|  - C++ Parsing Engine for Standard MPS Files (Fixed & Free format).               |
|  - C++ Sparse Matrix Data Structures (CSC/CSR) with Ruiz Equilibration Scaling.   |
|  - GPU-Accelerated LP Solver using CUDA Restarted PDHG (cuPDLP style).            |
|  - CPU Dual Revised Simplex Solver for exact basic solutions & Crossover.         |
|  - Basic Presolver (Row/Column singletons, fixed variables, bound propagation).   |
|  - Basic CPU Branch-and-Bound Engine for Binary/Integer Variables (MILP).         |
|  - Standard CLI Executable accepting `.mps` and returning `.sol` output.          |
|  - Automated Evaluation Benchmark Harness comparing against MIPLIB / Netlib LP.   |
+-----------------------------------------------------------------------------------+
|  SHOULD BUILD (High Priority Enhancements)                                        |
|  - Gomory Fractional Cutting Plane Generator.                                     |
|  - GPU-Accelerated Feasibility Pump Primal Heuristic.                             |
|  - Python API Bindings via `pybind11`.                                            |
|  - Convex Quadratic Programming (QP) support via Active Set / Barrier Method.     |
+-----------------------------------------------------------------------------------+
|  NICE TO HAVE (Time Permitting)                                                   |
|  - Knapsack Cover Cut & Clique Cut Generators.                                    |
|  - ML-guided pseudocost branching selector.                                       |
+-----------------------------------------------------------------------------------+
|  DO NOT BUILD DURING HACKATHON (Explicitly Out of Scope)                          |
|  - Graphical User Interface (GUI) [PS explicitly states GUI is not required].    |
|  - Non-linear (NLP) or Mixed-Integer Non-linear (MINLP) Non-Convex Solvers [PS].   |
|  - Distributed Multi-Node MPI Cluster Orchestrators [INFERENCE].                  |
+-----------------------------------------------------------------------------------+

17. Live Demo Simulation Plan

To convince SIH judges during the final evaluation without relying on inaccessible live refinery SCADA connections:

1. Benchmark Suite Execution Live:

   • Run the compiled indigenous_solver_cli live against selected official Netlib LP and MIPLIB 2017 benchmark MPS files in front of judges [PS, RESEARCHED].
   • Display real-time execution logs showing presolve reductions, GPU CUDA memory allocation, PDHG residual convergence curves, and Branch-and-Bound node progress [INFERENCE].

2. Refinery Crude Blending Case Study Demonstration:

   • Execute a representative synthetic MRPL crude oil blending MILP problem (generated from open literature refinery pooling models) [PS, RESEARCHED].
   • Demonstrate how the solver calculates optimal crude blend ratios that maximize gross margin subject to Reid Vapor Pressure (RVP), sulfur, and octane constraints [INFERENCE].

3. GPU Acceleration vs CPU Baseline Comparison:

   • Provide a togglable CLI flag (--use-gpu vs --cpu-only) [INFERENCE].
   • Benchmark a 500,000-variable LP model live, demonstrating a dramatic (e.g., 10x–50x) speedup when offloading sparse linear algebra iterations to CUDA [RESEARCHED].

4. Comparative Performance Dashboard:

   • Generate a side-by-side terminal / HTML summary comparing Indigenous-Solver performance against HiGHS (open-source benchmark) on solution time and objective value accuracy [RESEARCHED].

18. Implementation Roadmap

Phased Roadmap to 30 September 2026

Phases & Milestones Target: 30 September 2026
-----------------------------------------------------------------------------------
Phase 1: Architecture & Linear Algebra Core (Months 1-2 | Oct - Nov 2025)
  - Set up C++20 / CUDA CMake repository and GTest harness.
  - Implement MPS/LP file parser and internal Sparse CSR/CSC matrix structures.
  - Build Ruiz matrix equilibration scaling and basic Presolver module.

Phase 2: Continuous Solver Engines - LP & QP (Months 3-5 | Dec 2025 - Feb 2026)
  - Develop CUDA-based Restarted PDHG solver for massive continuous LPs.
  - Implement CPU Dual Revised Simplex with LU factorization for exact basis crossover.
  - Build Convex Quadratic Programming (QP) solver engine.
  - Validate on Netlib LP and QPLIB benchmark sets.

Phase 3: MILP Branch-and-Cut Engine (Months 6-8 | Mar - May 2026)
  - Implement CPU multi-threaded Branch-and-Bound tree manager.
  - Integrate Gomory fractional cut generator and knapsack cover cuts.
  - Implement GPU-accelerated Feasibility Pump primal heuristic.
  - Validate on MIPLIB 2017 Benchmark Instances.

Phase 4: Optimization, Refinery Case Studies & API (Months 9-10 | Jun - Jul 2026)
  - Build C++/Python API (`pybind11`).
  - Develop synthetic MRPL refinery crude blending and scheduling test models.
  - Perform CUDA kernel tuning and memory pipeline optimizations.

Phase 5: Benchmarking, Validation & SIH Final Dossier (Months 11-12 | Aug - Sep 2026)
  - Execute full Mittelmann LP/MILP benchmark evaluation suite.
  - Conduct numerical stability stress testing on ill-conditioned models.
  - Package standalone CLI executable, Python wheels, and documentation.
  - Final SIH Demonstration readiness (30 September 2026) [PS].

19. Testing & Validation Plan

1. Functional Correctness Testing:

   • Unit Tests: GTest suite covering matrix conversions (CSC to CSR), presolve reductions, and CUDA SpMV kernel outputs against reference double-precision calculations [INFERENCE].
   • Feasibility Verification: Verify that returned variable vectors $x^$ satisfy $L \le x^ \le U$ and $B_L \le A x^* \le B_U$ within absolute tolerance $\epsilon = 10^{-6}$ [RESEARCHED].

2. Numerical Stability & Stress Testing:

   • Test against ill-conditioned matrices (e.g., Netlib PILOT series or Mittelmann hard LP instances) [RESEARCHED].
   • Verify that Ruiz scaling prevents floating-point overflow/underflow and that iterative refinement recovers accuracy when condition numbers exceed $10^{10}$ [RESEARCHED].

3. Performance & Scalability Benchmarking:

   • Measure Shifted Geometric Mean (SGM) solve time on 240 MIPLIB 2017 benchmark instances [RESEARCHED].
   • Target: Solve $>80%$ of standard benchmark LPs within 60 seconds and achieve objective values matching CPLEX/HiGHS within $0.01%$ relative optimality gap [RESEARCHED].

4. False Positive / Infeasibility Testing:

   • Test infeasible Netlib instances (e.g., BGPRTR8); verify the solver correctly flags INFEASIBLE and produces dual infeasibility certificates [RESEARCHED].

20. Risk Register

21. Cost & Scalability

Hackathon Phase Scope & Cost

• Infrastructure Cost: ₹0 additional software cost [INFERENCE]. Developed on standard student laptops / university workstations equipped with a single NVIDIA GPU (e.g., RTX 3060 / 4090) [INFERENCE].
• Software Dependencies: 100% open-source tooling (GCC/Clang, CUDA Toolkit, CMake, Python, GoogleTest) [INFERENCE].

Enterprise Production Deployment Scope & Cost

• Deployment Architecture: Distributed headless Docker container instances running on MRPL enterprise on-premise GPU server clusters (e.g., NVIDIA A100 / H100 or C-DAC PARAM Rudra nodes) [INFERENCE].
• Licensing Cost Savings: Standard commercial solvers (CPLEX/Gurobi) cost $10,000 - $30,000+ per server socket annually [KNOWN]. A sovereign indigenous solver eliminates recurring licensing costs across all Indian PSUs, saving millions of dollars nationally [PS, INFERENCE].
• Scalability: Capable of solving models with millions of variables by leveraging GPU memory bandwidth (up to 2 TB/s on modern GPUs) for sparse matrix operations [RESEARCHED].

22. Differentiation

23. Future Scope

1. MINLP & Non-Linear Solver Extensions: Extend modular interface to handle non-linear refinery pooling equations directly via Mixed-Integer Nonlinear Programming (MINLP) and Sequential Quadratic Programming (SQP) [PS].
2. Multi-GPU & Distributed Cluster Execution: Scaling the CUDA PDHG matrix-vector kernel across multi-GPU nodes using NVIDIA NCCL and MPI for multi-million constraint national power grid optimization [RESEARCHED].
3. Indigenous Hardware Portability: Port CUDA kernels to SYCL/HIP to support indigenous Indian computing hardware platforms (e.g., C-DAC PARAM Rudra and Shakti processor clusters) [INFERENCE].

24. Assumptions & Open Items Log

Consolidated Assumptions

1. [ASSUMPTION]: External low-level CUDA linear algebra primitives (cuSPARSE / cuBLAS) are permissible for matrix-vector multiplication as long as all solver algorithms (Presolve, PDHG, Simplex, Branch-and-Bound, Cuts) are written natively from scratch [PS, INFERENCE].
2. [ASSUMPTION]: The primary development and benchmarking hardware will be x86_64 Linux workstations equipped with NVIDIA CUDA-capable GPUs (Compute Capability 7.5+) [INFERENCE].
3. [ASSUMPTION]: Publicly available benchmark libraries (MIPLIB 2017, Netlib LP, Mittelmann, QPLIB) serve as sufficient proxy test suites for industrial refinery LPs during the hackathon phase [PS, RESEARCHED].

Consolidated Open Items & Validation Log

1. [NEEDS VALIDATION]: Exact numerical tolerances and constraint structures of MRPL's internal, proprietary refinery LP models (to be validated with MRPL domain engineers during SIH mentoring rounds) [PS, INFERENCE].
2. [NEEDS VALIDATION]: Performance upper bound of CUDA Restarted PDHG on highly degenerate QP models compared to interior-point barrier methods [RESEARCHED].

Final Recommendation

The team should proceed with building the Indigenous GPU-Accelerated Optimization Solver Core following Approach 3 (Heterogeneous Hybrid Architecture) [INFERENCE]. By combining a CUDA-accelerated Restarted PDHG solver for continuous LP relaxations with a custom C++ multi-threaded Branch-and-Cut manager and Dual Simplex Crossover, the solution directly fulfills all explicit requirements of SIH26119, delivers proven GPU speedups on industrial models, and establishes a sovereign mathematical foundation for Indian industry [PS, RESEARCHED, INFERENCE].

Recommended Stack

• Core Engine: C++20 [INFERENCE]
• GPU Computing: NVIDIA CUDA Toolkit 12.x (cuSPARSE) [RESEARCHED]
• CPU Parallelism: OpenMP [INFERENCE]
• API & Bindings: pybind11 (Python) & C-API [INFERENCE]
• Build & Test: CMake, GoogleTest, Benchmark scripts [INFERENCE]

Biggest Dependency

Availability of a CUDA-capable NVIDIA GPU development environment and standard MPS benchmark files (MIPLIB 2017 / Netlib LP) [RESEARCHED].

Biggest Risk

Numerical stalling or slow convergence of first-order GPU LP methods on highly ill-conditioned or degenerate industrial constraint matrices [RESEARCHED].

Biggest Technical Challenge

Implementing a numerically stable C++ Dual Revised Simplex with LU factorization and Markowitz pivoting from scratch to perform exact basis Crossover after GPU PDHG LP solves [RESEARCHED].

First 5 Actions

1. Initialize C++20 / CUDA CMake project repository with GoogleTest harness [INFERENCE].
2. Write custom C++ MPS File Parser supporting standard Fixed and Free MPS formats [INFERENCE].
3. Implement in-memory Compressed Sparse Column (CSC) / Row (CSR) matrix data structures [INFERENCE].
4. Develop custom CUDA matrix-vector multiplication (SpMV) kernel and test against cuSPARSE [RESEARCHED].
5. Build basic Ruiz matrix equilibration scaling and verify numerical reduction on Netlib afiro.mps [RESEARCHED].

Validation Before Coding

Validate that the CUDA development environment is correctly configured (nvcc --version) and verify that standard MPS parser unit tests pass against 5 sample Netlib LP instances (afiro, 25fv47, stocfor1, blend, share2b) [RESEARCHED].

Buildability Score /100

88/100: Highly buildable for a 4–6 student team with strong computational mathematics, C++, and CUDA skills. The modular separation allows parallel development of parser, presolver, GPU engine, and CPU tree search [INFERENCE].

Confidence

High: Supported by extensive recent research (e.g., cuPDLP, ScaleOPT) demonstrating the efficacy of GPU first-order methods for LP relaxations, backed by established mathematical solver literature [RESEARCHED].

Research Sources