跳转到主要内容

Gurobi计算IIS MIP问题如何?

回答
Ramy穆罕默德
Gurobi-versary
第一个评论
第一个问题

你好,

请,我有问题如何Gurobi计算的IIS MIP模型。

正如本文中提到:Gurobi如何计算不可行的IIS模型?——Gurobi支持门户。本文方法计算IIS是基于:

ORSA杂志上计算
2卷,1号,1990年,DOI: 10.1287 / ijoc.2.1.61
确定最低限度不可行子系统的不平等
约翰格里森,詹妮弗·瑞恩

格里森和瑞安使用变体Farkas 'Lemma获得一个多面体,每个顶点对应于IIS。从我的理解,这种方法适用于LP问题,我认为这是有可能找到所有iis不可行的LP问题如果我们发现另一种多面体的顶点。

我的问题:

-为什么Gurobi不返回所有iis LP问题?

瑞安- Gurobi使用格里森和的方法,为LP,计算IIS MIP(不可行模型和整数变量)?

非常感谢你的时间和考虑

问候

Ramy

博士生

1

评论

5个评论

日期票
  • 官方的评论
    看门人尤里Zinchenko
    Gurobi员工Gurobi员工

    你好Ramy,

    谢谢你的关心!:)

    1。LP,计算所有三世的基于双,正如你所说,相当于列举各自的双重多面体的顶点,这可能是一个巨大的计算任务。你可以谷歌顶点枚举算法或包。AFAIK有一些,但不是很多,主要是由于这种顶点通常数量的增长组合,可能是巨大的。

    2。MIP,没有选择dualize(至少在某些compute-reasonable意义上,可以这么说)。相反,可以在很大程度上依赖于各种各样的“过滤器”,例如,删除过滤器,添加过滤器,等。这个术语指的是选择一个约束和试图从模型中删除它,看看结果被仍不可行(删除过滤器),或从一个空集,试图添加一些约束,希望生成一个不可行的子集系统(一个过滤器),等下罩,Gurobi使用的组合,但总体形势与MIP /计算密集型复杂得多,比一个能做什么LP。

    希望这个有帮助。

  • Ramy穆罕默德
    Gurobi-versary
    第一个评论
    第一个问题

    你好,看门人尤里,

    非常感谢你的回答。它是非常有用的。感谢。

    请,我有另一个问题:

    如果Guroubi计算IIS使用过滤算法,这意味着我们可以尝试多个IIS通过模型中的约束条件,对吗?我试着这样做但Guroubi computIIS方法总是返回相同的IIS不论约束的秩序。做Guroubi约束在应用滤波算法之前订单吗?

    我实现了一个滤波算法来隔离IIS和我能够得到不同的IIS通过洗牌的约束模型。我想知道,我可以做同样的使用Guroubi computeIIS吗?它返回IIS快得多。

    我使用的方法从以下文章:

    Guieu、奥利弗和约翰·w·这个。“不可行分析整数和整数线性规划。”通知杂志上计算11.1 (1999):63 - 77。

    再次感谢你的时间和考虑。

    问候

    Ramy

    0
  • 看门人尤里Zinchenko
    Gurobi员工Gurobi员工

    >如果Guroubi计算IIS使用过滤算法,这意味着我们可以尝试多个IIS通过模型中的约束条件,对吗?我试着这样做但Guroubi computIIS方法总是返回相同的IIS不论约束的秩序。做Guroubi约束在应用滤波算法之前订单吗?

    精确!你也可以尝试改变种子参数,这可能改变IIS轨迹。就其价值而言,我试图找到约翰这个幻灯片当我写第一个回答,他广泛使用“过滤器”术语,和幻灯片是伟大的,但由于某种原因无法找到它。

    希望这有助于

    1
  • Ramy穆罕默德
    Gurobi-versary
    第一个评论
    第一个问题

    你好,看门人尤里,

    再次感谢你的回复。它是非常有用的。

    这是你正在寻找的幻灯片:https://www.sce.carleton.ca/faculty/chinneck/docs/CPAIOR07InfeasibilityTutorial.pdf

    这是一个教程演示这个教授。这是在2007年的这个会议:

    第四国际会议集成人工智能和技术约束组合优化问题的编程(CP-AI-OR ' 07年)5月23日,2007 -布鲁塞尔,比利时
    顺便说一句,这个教授是在同一个部门,我做我的博士:在卡尔顿大学系统和计算机工程。
    问候
    Ramy
    0
  • 看门人尤里Zinchenko
    Gurobi员工Gurobi员工

    高兴听到这是有帮助的。

    保持好,Ramy,请说“你好”约翰如果你遇到他,他可能还记得Yuriy PDF在麦克马斯特,这个访问教授。

    的问候。

    0

请登录留下你的评论。

没有找到你正在寻找什么?

新职位