在MATLAB上迭代使用bintprog [英] Iterative use of bintprog on MATLAB

问题描述

我们有一个问题表述，如此链接所示.

We have a problem formulation as shown in this link.

考虑到第一次调用bintprog给出的解决方案x，在某些后期处理后仍不能充分解决物理问题，是否可以召回bintprog并排除先前的解决方案x?

Considering that the first call of bintprog gives a solution x that after some post processing does not adequately addresses the physical problem, is it possible to recall bintprog and exclude the prior solution x?

推荐答案

您需要削减工作量.

假设您找到了一个解决方案\ hat {x}，然后您认为该解决方案是不可行的(通过某种后期处理).让x和\ hat {x}被i索引.

Suppose you find a solution \hat{x} that you then decide is infeasible (through some sort of post-processing). Let x and \hat{x} be indexed by i.

您可以添加以下形式的约束:

You can add a constraint of the following form:

\sum_{i : \hat{x}_i = 0} x_i + \sum_{i : \hat{x} = 1} (1-x_i) \geq 1

此约束是不好的例子:解决方案必须与\ hat {x}至少相差一个索引i，否则将不可行.如果您的变量不是二进制变量，那么无价商品可能会更加复杂.

This constraint is an example of a no-good cut: the solution must differ from \hat{x} by at least one index i, otherwise it is infeasible. If your variables are not binary no-goods can be a little more complex.

您可以通过将约束作为一行附加到约束矩阵并使用bintprog()函数重新求解，来向解决方案中添加无效的东西.我将它留给您，以便您以MATLAB表示法重写它.

You can add a no-good to your solution by appending the constraint as a row to your constraint matrix and re-solving with the bintprog() function. I'll leave it to you to you rewrite it in the MATLAB notation.

您没有说后处理的功能，但是如果后处理可以从您的解决方案\ hat {x}中推断出其他解决方案也是不可行的，那就更好了，并且您可以添加多个解决方案每次迭代行.这是基于逻辑的Benders分解的一种形式，其他不可行解决方案的推理称为求解推理对偶(与解决线性规划对偶的标准Benders分解相反). 有关基于逻辑的Benders分解的更多信息，该词的作者是约翰·胡克(John Hooker)， CMU.

You didn't say what your post-processing does, but it would be even better if the post-processing could infer from your solution \hat{x} that other solutions are also infeasible, and you can add more than one row per iteration. This is a form of logic-based Benders decomposition, and the inference of other infeasible solutions is called solving an inference dual (as opposed to standard Benders decomposition, where you're solving the linear programming dual). More on logic based Benders decomposition from the man who coined the term, John Hooker of CMU.

很抱歉格式化.我需要走，但是以后我会想出一种更好地显示方程式的方法.

Sorry for the formatting. I need to go but I'll figure out a way to display equations more nicely later.

这篇关于在MATLAB上迭代使用bintprog的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！