跳到主要导航 跳到搜索 跳到主要内容

Enhancing presolve in mixed integer programming by combining probing and dual fixing

  • Zhao Wei Wang
  • , Wei Kun Chen*
  • , Yu Hong Dai
  • *此作品的通讯作者
  • CAS - Academy of Mathematics and System Sciences
  • University of Chinese Academy of Sciences
  • Beijing Institute of Technology

科研成果: 期刊稿件 › 文章 › 同行评审

摘要

Probing and dual fixing are two powerful presolve techniques in mixed integer programming (MIP) solvers. Probing tentatively sets some binary variables to 0 or 1, applies linear constraint based domain propagation techniques to derive better variable bounds, and extracts useful information such as stronger variable implications and better global variable bounds. Dual fixing attempts to fix variables to lower or upper bounds while ensuring that at least one optimal solution is retained, as long as the problem was feasible. In this paper, we investigate how to combine the two approaches in MIP solvers to achieve a better performance. In particular, we first embed dual fixing into the probing framework, deriving more useful variables’ implications for enhancing the capability of probing. Then, we develop an improved dual fixing technique where more variable fixings can be applied, and use the probing framework to detect the reductions. Computational results on the MIPLIB 2017 benchmark instances demonstrate the potential of the two proposed techniques in combining probing and dual fixing on the open-source MIP solver HiGHS.

源语言英语
期刊Mathematical Programming Computation
DOI
出版状态已接受/待刊 - 2026
已对外发布是

学术指纹

探究 'Enhancing presolve in mixed integer programming by combining probing and dual fixing' 的科研主题。它们共同构成独一无二的学术指纹。

引用此