c++ - 如果没有目标函数，如何检查约束是否可行？

Question

我的教授给了我一个二元线性规划问题，但这个问题与我以前解决的优化问题略有不同(即这可能不是最大化或最小化目标函数。)

问题如下，给定矩阵 M，对于条目 m_ij != 0，有对应的 x_ijk 变量。条目 m_ij = 0 可以忽略。

x_ijk不是0就是1，我想对每个m_ij尝试5个x_ijk变量(即x_ij1、x_ij2、x_ij3、x_ij4、x_ij5，其中一个为1，其他为0)就足够了满足一些条件(一组不等式)。

更简单地说，这是检查包含每个 m_ij 的 5 个 x_ijk 变量的约束集是否是有效(或可行)约束。

我已经解决了一些优化问题，但我从来没有解决过没有目标函数的问题。

我应该在这里设置什么作为我的目标函数？0？什么都没有？

我可能正在使用 lp_solve 或 CPLEX。

预先感谢您的建议!

Answer 1

没错，你可以设置一个任意的常数值作为目标函数。

我尝试过的大多数求解器都允许空目标函数。只需将其从您的模型中删除即可。

根据您使用的求解器和 API，您可能必须将目标中所有变量的系数设置为零。

别担心，它必须起作用。

---

回应您的评论:是的，与 LP 求解器(例如 CPLEX)相比，约束编程工具在可行性问题上可以提供更好的性能。我玩过 IBM ILOG CPLEX CP Optimizer几个月前，它对学术用户免费。 LP 求解器和 CP 求解器都无法解决我的问题。不要指望约束规划会出现奇迹。

请记住，在最坏的情况下，解决约束程序所需的时间会随着问题的规模呈指数增长。迟早，您的问题很可能无法使用任何一种工具解决。

仅供引用:最后，约束规划求解器将调用 LP 求解器(例如 CPLEX)。

我的建议是:尝试您已有的工具/使用对您来说更自然的问题表述。检查该工具是否可以解决您的问题。仅当工具失败并且您无法改进模型时才切换工具。