# Bug dans plusieurs solveurs de programmation linéaire en nombres entiers

Rémi Garcia, Anna Lambert

► To cite this version:

Rémi Garcia, Anna Lambert. Bug dans plusieurs solveurs de programmation linéaire en nombres entiers. ROADEF 2026 - 27ème édition du congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision, Feb 2026, Tours, France. hal-05450053

HAL Id: hal-05450053

https://hal.science/hal-05450053v1

Submitted on 9 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Bug dans plusieurs solveurs de
programmation linéaire en nombres entiers

Rémi Garcia¹ Anna Lambert²,³

¹ Université de Rennes, IRISA, Inria, France remi.garcia@irisa.fr

² Nantes Université, École Centrale Nantes, CNRS, LS2N, UMR 6004, 44000 Nantes, France

³ Institute for Quantitative and Computational Biosciences (IQCB), Johannes Gutenberg-University Mainz, Mainz, Germany lamberta@uni-mainz.de

Mots-clés : optimisation, PLNE, solveurs, bugs

# 1 Utilisation des solveurs et bugs potentiels

La programmation linéaire en nombre entiers (PLNE) est de plus en plus utilisée au-delà de la communauté de « Recherche Opérationnelle ». Des chercheurs et chercheuses en conception matérielle [1] ou en biologie [2] se sont notamment emparé-e-s de ces outils pour leurs applications. Les solveurs de PLNE sont ainsi de plus en plus souvent utilisés comme des boîtes noires, sans connaissances particulières quant à leur fonctionnement interne ou de leurs nombreux paramètres.

Avec cet investissement des outils de la communauté par des communautés extérieures, vient la nécessité de rendre d'autant plus robuste et facile d'utilisation ces solveurs. Cependant, malgré leur complexité rendant les erreurs de plus en plus probables, il n'y a pas, à notre connaissance, de vérification des solutions avant d'être retournées par les solveurs. Ainsi, dans leur fonctionnement « par défaut », cette absence de vérification entraîne la transmission d'un certain nombre de bugs évitables jusque dans les sorties du solveur.

Afin d'automatiser leur détection et leur résolution, réfléchir en amont à définir les bugs que les utilisateurs et utilisatrices pourraient rencontrer nous a semblé important. Nous proposons de réfléchir à une liste de bugs possibles, et donc à anticiper, dans les sorties de solveurs :

- Une solution sous-optimale pourrait être associée à un drapeau « solution optimale »;

- Un drapeau « problème infaisable » pourrait être retourné pour un problème qui comporte pourtant des solutions ;

- Une solution infaisable pourrait être retournée pour un problème qui ne comporte aucune solution valide ;

- Une solution infaisable pourrait être retournée pour un problème qui comporte une ou plusieurs solutions valides.

De fait, dans cette liste, nous excluons les bugs détectés par le solveur car les utilisateurs et utilisatrices seraient alors averti-e-s de l'incident. Dans l'idéal, aucun des bugs énumérés ici ne devrait arriver jusqu'à la sortie du solveur.

# 2 Un exemple de bug rencontré avec CarveMe

La modélisation métabolique vise à prédire le comportement du métabolisme cellulaire en s'appuyant sur des méthodes d'optimisation mathématique. Elle représente le métabolisme sous forme de réseaux réactionnels complexes, traduits en contraintes stœchiométriques et thermodynamiques. L'obtention même de ce réseau métabolique est difficile et CarveMe est un outil répondant à ce problème [2]. Il s'agit de passer d'un génome fourni en entrée à un réseau métabolique associé.

Partant d'un vaste modèle métabolique universel bactérien, issu de la fusion et de la curation de modèles existants, l'outil simplifie ce modèle pour éliminer les réactions absentes, produisant ainsi un modèle métabolique propre à l'organisme cible. Ce processus repose sur un PLNE. Lorsque nous avons utilisé CarveMe afin de construire un modèle métabolique de la bactérie
<table><caption>TAB. 1 – Résultats d'optimisation pour plusieurs résolutions de la même instance. TollInt indique la valeur du paramètre de tolérance numérique (*integrality tolerance*). La valeur de la fonction objective est dans ObjVal et l'erreur rapportée par CheckSolve est dans la colonne Check. Dans la colonne DivCst est également indiqué si les contraintes ont été subdivisées.</caption><thead><tr><th>Solveur</th><th>TollInt</th><th>DivCst</th><th>#Variables</th><th>#Contraintes</th><th>ObjVal</th><th>OptFlag</th><th>Check</th></tr></thead><tbody><tr><td>CPLEX</td><td>10<sup>-5</sup></td><td>✗</td><td>11811</td><td>43928</td><td>1165.4</td><td>✓</td><td>9 × 10<sup>-3</sup></td></tr><tr><td>CPLEX</td><td>0.0</td><td>✗</td><td>11811</td><td>43928</td><td>1000.4</td><td>✗</td><td>3 × 10<sup>-11</sup></td></tr><tr><td>CPLEX</td><td>0.0</td><td>✓</td><td>35179</td><td>67296</td><td>1141.7</td><td>✗</td><td>9 × 10<sup>-7</sup></td></tr><tr><td>Gurobi</td><td>10<sup>-5</sup></td><td>✗</td><td>11811</td><td>43928</td><td>1158.1</td><td>✓</td><td>1 × 10<sup>-2</sup></td></tr><tr><td>Gurobi</td><td>10<sup>-9</sup></td><td>✗</td><td>11811</td><td>43928</td><td>1001.6</td><td>✓</td><td>6 × 10<sup>-11</sup></td></tr><tr><td>Gurobi</td><td>10<sup>-9</sup></td><td>✓</td><td>35179</td><td>67296</td><td>1141.7</td><td>✓</td><td>2 × 10<sup>-11</sup></td></tr><tr><td>SCIP</td><td>10<sup>-6</sup></td><td>✗</td><td>11811</td><td>43928</td><td>1007.6</td><td>✗</td><td>1 × 10<sup>-3</sup></td></tr><tr><td>SCIP</td><td>10<sup>-9</sup></td><td>✗</td><td>11811</td><td>43928</td><td>995.7</td><td>✗</td><td>5 × 10<sup>-11</sup></td></tr><tr><td>SCIP</td><td>10<sup>-9</sup></td><td>✓</td><td>35179</td><td>67296</td><td>1140.7</td><td>✗</td><td>6 × 10<sup>-12</sup></td></tr></tbody></table>

A. *oryzae*, nous avons constaté que CPLEX, Gurobi et SCIP renvoyaient tous des solutions dont la valeur de la fonction objectif variait. En particulier, CPLEX indique un gap à l'optimal négatif. Nous avons donc vérifié les solutions avec notre outil CheckSolve<fnref n="1" /> et constaté qu'aucune des solutions proposées par les solveurs ne satisfait les contraintes.

## 3 Nos tentatives (infructueuses) pour le contourner

À partir de CarveMe, nous avons extrait le fichier de modèle .1p utilisé pour construire un réseau métabolique à partir du génome de A. *oryzae*. Nous l'avons alors passé à CPLEX, Gurobi et SCIP en modifiant le paramètre de tolérance numérique ou en découpant les contraintes en sous-contraintes impliquant moins de variables. L'ensemble des résultats d'optimisation, avec une limite de temps de 600 secondes, se trouve dans la table 1.

Un premier bug est immédiatement visible en raison des contradictions quant au drapeau d'optimalité qui, pour un même solveur, est levé pour des valeurs de la fonction objectif sensiblement différentes. Une analyse des solutions fournies nous permet de constater que les contraintes non satisfaites impliquent toujours des variables continues. Cependant, sur les milliers de contraintes, seules 1394 d'entre elles n'impliquent que des variables discrètes : déterminer si les erreurs numériques sont imputables aux variables continues ou non n'est donc pas un processus évident. À cela s'ajoute le fait que les coefficients utilisés pour les variables discrètes ne sont eux-mêmes pas discrets : l'analyse est d'autant plus laborieuse et le modèle généré par CarveMe est, par construction, difficile à traiter pour des solveurs.

Des expérimentations restent à mener, nous avons notamment prévu d'analyser plus précisément le modèle généré pour potentiellement discrétiser les coefficients associés aux variables discrètes. Nous réfléchissons également à une façon de "corriger" les variables continues pour satisfaire les contraintes tout en s'assurant que ces corrections n'impactent elles-mêmes pas d'autres contraintes. Finalement, nous devons aussi mener davantage de tests avec SCIP et SoPlex afin d'obtenir une solution de référence satisfaisant réellement les contraintes.

## Références

[1] Martin Kumm and Peter Zipf. Pipelined compressor tree optimization using integer linear programming. In *FPL*. IEEE, September 2014.

[2] Daniel Machado, Sergej Andrejev, Melanie Tramontano, and Kiran Raosaheb Patil. Fast automated reconstruction of genome-scale metabolic models for microbial species and communities. *Nucleic Acids Research*, 46(15):7542-7553, June 2018.

<footnote n="1">1. https://github.com/remi-garcia/CheckSolve</footnote>