Scholarlink

<p>We present a unified framework of exact continuous formulations for a wide range of classical graph optimization problems, including the minimum (double) dominating set, vertex cover, maximum independent set, clique, <i>s</i>-plex, and max-cut, by leveraging the probabilistic method, and introduce several novel weighted extensions. The approach yields multilinear polynomial programs over the unit hypercube whose optimal values coincide with the corresponding combinatorial invariants. To assess practical performance, we conduct numerical experiments using a modern global solver (Gurobi) and five state-of-the-art local solvers (CONOPT, IPOPT, KNITRO, LOQO, SNOPT). We find that high-degree multilinear objectives can severely impede convergence, but that systematic degree reduction via Boole’s inequality drastically improves solution quality and robustness. The obtained results are promising and encourage a more detailed investigation of continuous formulations based on the probabilistic method in the context of solving discrete optimization problems.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Continuous formulations for combinatorial optimization problems based on the probabilistic method

  • 期刊论文

  • 发表日期：

    2026年5月29日

查看全文
  • Sergiy Butenko,
  • Miltiades Pardalos,
  • Ashwini Ravindran

摘要

We present a unified framework of exact continuous formulations for a wide range of classical graph optimization problems, including the minimum (double) dominating set, vertex cover, maximum independent set, clique, s-plex, and max-cut, by leveraging the probabilistic method, and introduce several novel weighted extensions. The approach yields multilinear polynomial programs over the unit hypercube whose optimal values coincide with the corresponding combinatorial invariants. To assess practical performance, we conduct numerical experiments using a modern global solver (Gurobi) and five state-of-the-art local solvers (CONOPT, IPOPT, KNITRO, LOQO, SNOPT). We find that high-degree multilinear objectives can severely impede convergence, but that systematic degree reduction via Boole’s inequality drastically improves solution quality and robustness. The obtained results are promising and encourage a more detailed investigation of continuous formulations based on the probabilistic method in the context of solving discrete optimization problems.