{
  "abstract": "Arc flow formulations derived from dynamic programs have been used to solve many hard combinatorial optimization problems. They generally have strong linear relaxations, but they may contain a pseudo-polynomial or exponential number of arcs, making large instances difficult to solve directly. A classical heuristic approach to address this limitation is to solve a restricted model obtained by removing arcs based on reduced costs or problem-specific information. We propose Sparsity Refinement Anytime (SRA), a generic algorithm that iteratively solves restricted arc flow formulations while progressively adding arcs according to their scores. These scores are computed either from reduced costs alone or by a machine learning (ML) model whose features, including reduced costs, are derived solely from the arc flow formulation and its linear relaxation. The ML model is trained by imitation learning and combines two neural networks, one for arcs with null reduced costs and one for arcs with positive reduced costs, whose outputs are calibrated into a common score. To reduce the risk of infeasibility of highly restricted problems, SRA also includes a repair procedure. Experiments on the parallel machine total weighted tardiness scheduling problem and the cutting stock problem compare ML-guided and reduced-cost-guided SRA with the direct solution of the complete formulation. SRA improves on the direct solution within the same time limit, substantially for the scheduling problem. ML-guided SRA outperforms reduced-cost-guided SRA on all tested instance sizes, including sizes larger than those used for training.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": null,
  "author_total": 3,
  "authors": [
    {
      "name": "Fulin Yan"
    },
    {
      "name": "François Clautiaux"
    },
    {
      "name": "Aurélien Froger"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/8mjf75rh9nf71.bib",
  "cited_by": 0,
  "doi": null,
  "fulltext_url": null,
  "id": "8mjf75rh9nf71",
  "issns": [],
  "landing_url": "https://hal.science/hal-05836617v1",
  "language": "en",
  "licence": "CC-BY-NC-4.0",
  "licence_label": "CC BY-NC 4.0",
  "licence_source": "article",
  "licence_url": "https://creativecommons.org/licenses/by-nc/4.0/",
  "metadata_licence": null,
  "native_subjects": [
    [
      "hal",
      "0.info"
    ],
    [
      "hal",
      "0.math"
    ]
  ],
  "openalex": null,
  "pdf_url": "https://hal.science/hal-05836617/document",
  "pmcid": null,
  "pmid": null,
  "published": "2026-10-23",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/8mjf75rh9nf71.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:18:01Z",
      "native_id": "hal-05836617",
      "source": "hal",
      "url": "https://hal.science/hal-05836617v1"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "hal:0.math",
      "subfield": "general"
    }
  ],
  "title": "Generic Machine Learning-Based Sparsification for Arc Flow Formulation of Combinatorial Optimization Problems",
  "title_text": "Generic Machine Learning-Based Sparsification for Arc Flow Formulation of Combinatorial Optimization Problems",
  "type": "preprint",
  "updated_at": "2026-10-30T12:18:01Z",
  "url": "https://research.draconitic.com/paper/8mjf75rh9nf71",
  "venue": "HAL",
  "versions": []
}