Mosek Fusion超时后如何获取整数规划的最优可行解？

问题描述 #

我有一个整数优化问题，计划使用Mosek-Fusion求解。由于求解耗时可能过长，我设置了10秒的超时时间。程序会在10秒后停止，但我如何获取截止到超时前Mosek找到的最优可行解？

当程序正常终止时，我可以通过x.level()获取解，但超时情况下会报错。

最小可复现示例 #

设置1秒超时的代码如下：

from mosek.fusion import *
import mosek.fusion.pythonic
import numpy as np
import sys

if __name__ == '__main__':
  M = Model()
  A = np.array(np.random.randint(-1,2, size = (128,256)), dtype = np.float64)
  x = M.variable("x", 256, Domain.binary())
  b = np.array(np.random.randint(0,20, size = (128)), dtype = np.float64)
  c = np.random.random(size = 256)

  M.constraint(A @ x <= b)
  M.objective(ObjectiveSense.Maximize, x.T @ c)
  M.setSolverParam("optimizerMaxTime", 1)
  M.setLogHandler(sys.stdout)
  M.solve()
  print(x.level())

运行后抛出错误：

SolutionError: Solution status is Feasible but Optimal is expected. Reason: Accessing integer solution whose problem status is PrimalFeasible.

补充说明：我需要迭代地向问题中添加约束，且无需重新运行求解器，因此切换到cvxpy并非可行选项。

解决方案 #

当Mosek因为超时终止时，默认的x.level()方法会因为未达到最优解而抛出异常。要获取求解过程中找到的可行解，需按以下步骤操作：

1. 检查求解状态：通过Model.getPrimalSolutionStatus()获取原始解的状态，确认是否存在可行解。
2. 指定获取可行解：使用Variable.level(SolutionType.Feasible)来获取求解器在超时前找到的最优可行解（针对MIP问题，求解器会记录搜索过程中找到的最佳可行解）。

修改后的完整代码：

from mosek.fusion import *
import mosek.fusion.pythonic
import numpy as np
import sys

if __name__ == '__main__':
  M = Model()
  A = np.array(np.random.randint(-1,2, size = (128,256)), dtype = np.float64)
  x = M.variable("x", 256, Domain.binary())
  b = np.array(np.random.randint(0,20, size = (128)), dtype = np.float64)
  c = np.random.random(size = 256)

  M.constraint(A @ x <= b)
  M.objective(ObjectiveSense.Maximize, x.T @ c)
  M.setSolverParam("optimizerMaxTime", 1)
  M.setLogHandler(sys.stdout)
  
  M.solve()

  # 检查原始解状态
  primal_status = M.getPrimalSolutionStatus()
  if primal_status in [SolutionStatus.Feasible, SolutionStatus.Optimal]:
      # 获取可行解
      sol = x.level(SolutionType.Feasible)
      print("可行解：", sol)
  else:
      print("未找到可行解")

关键说明 #

• SolutionType.Feasible适用于超时、迭代中断等未达到最优的场景，能正确返回求解过程中记录的最佳可行整数解。
• 该方法完全兼容后续迭代添加约束的需求，添加新约束后直接调用M.solve()即可继续求解，无需重新初始化模型。

内容的提问来源于stack exchange，提问作者Hennich