lpsolve-不可行的解决方案，但我有示例1 [英] lpsolve - unfeasible solution, but I have example of 1

问题描述

我正在尝试在LPSolve IDE中解决此问题:

/* Objective function */
min: x + y;

/* Variable bounds */
r_1: 2x = 2y;
r_2: x + y = 1.11 x y;
r_3: x >= 1;
r_4: y >= 1;

但是我得到的答复是:

Model name:  'LPSolver' - run #1
Objective:   Minimize(R0)

SUBMITTED
Model size:        4 constraints,       2 variables,            5 non-zeros.
Sets:                                   0 GUB,                  0 SOS.

Using DUAL simplex for phase 1 and PRIMAL simplex for phase 2.
The primal and dual simplex pricing strategy set to 'Devex'.

The model is INFEASIBLE
lp_solve unsuccessful after 2 iter and a last best value of 1e+030

当x=1.801801802和y=1.801801802是这里的可能解决方案时，怎么会发生这种情况?

解决方案

如何找到解决方案

让我们做一些数学运算.

您的问题是:

min x+y
s.t. 2x = 2y
     x + y = 1.11 x y
     x >= 1
     y >= 1

第一个约束2x = 2y可以简化为x=y.现在，我们替换整个问题:

min 2*x
s.t. 2*x = 1.11 x^2
     x >= 1

然后重新排列:

min 2*x
s.t. 1.11 x^2-2*x=0
     x >= 1

从几何中我们知道1.11 x^2-2*x产生向上开口的抛物线，其最小值小于零.因此，恰好有两点.这些由二次方程式给出:200/111和0.

其中只有一个满足第二个约束:200/111.

为什么我的求解器找不到此约束

最简单的方法是说这是因为x^2项(替换前的x*y是非线性的).但这远不止于此.非线性问题只要凸就可以容易解决. 凸问题是其约束形成单个连续空间的问题，这样，在两个之间绘制的任何线空间中的点保持在空间边界之内.

您的问题不是凸面的.约束1.11 x^2-2*x=0定义了无限个点.这些点中的任何两个点都不能通过直线连接，因为该直线是弯曲的，所以该直线位于约束定义的空间中.如果约束改为1.11 x^2-2*x<=0，则该空间将是凸形的，因为所有点都可以与保留在其内部的直线相连.

非凸问题是称为 NP-Hard 的更广泛问题的一部分.这意味着没有(也许不可能)有解决问题的简便方法.我们必须要聪明.

可以处理混合整数编程(MIP/MILP)的解决方案可以解决许多有效地凸出问题，遗传算法等其他技术也可以.但是，在幕后，这些技术全都依靠美化的猜测和检查.

所以您的求解器会失败，因为问题是非凸性的，并且您的求解器既不够聪明，不足以使用MIP来猜测和检查其求解的方式，也不够聪明，无法使用二次方程式.

那我该如何解决问题?

在这种特定情况下，我们能够使用数学快速找到解决方案，因为尽管问题不是凸的，但它是一类特殊情况的一部分.数学家的深入思考为我们提供了一种处理此类的简单方法.

但是考虑一下该问题的一些概括:

(a) a x^3+b x^2+c x+d=0
(b) a x^4+b x^3+c x^2+d x+e =0
(c) a x^5+b x^4+c x^3+d x^2+e x+f=0

(a)具有三个必须检查的潜在解决方案(确切的解决方案是 tricky >)，(b)具有四个( trickier )，和(c)有五个. (a)和(b)的公式比二次公式复杂得多，并且数学家已经证明存在

因此，我们用来解决问题的技术不能很好地推广.这就是生活在非凸和NP-hard领域的意义，也是资助数学，计算机科学和相关领域研究的一个很好的理由.

I'm trying to solve this in LPSolve IDE:

/* Objective function */
min: x + y;

/* Variable bounds */
r_1: 2x = 2y;
r_2: x + y = 1.11 x y;
r_3: x >= 1;
r_4: y >= 1;

but the response I get is:

Model name:  'LPSolver' - run #1
Objective:   Minimize(R0)

SUBMITTED
Model size:        4 constraints,       2 variables,            5 non-zeros.
Sets:                                   0 GUB,                  0 SOS.

Using DUAL simplex for phase 1 and PRIMAL simplex for phase 2.
The primal and dual simplex pricing strategy set to 'Devex'.

The model is INFEASIBLE
lp_solve unsuccessful after 2 iter and a last best value of 1e+030

How come this can happen when x=1.801801802 and y=1.801801802 are possible solutions here?

解决方案

How To Find The Solution

Let's do some math.

Your problem is:

min x+y
s.t. 2x = 2y
     x + y = 1.11 x y
     x >= 1
     y >= 1

The first constraint 2x = 2y can be simplified to x=y. We now substitute throughout the problem:

min 2*x
s.t. 2*x = 1.11 x^2
     x >= 1

And rearrange:

min 2*x
s.t. 1.11 x^2-2*x=0
     x >= 1

From geometry we know that 1.11 x^2-2*x makes an upward-opening parabola with a minimum less than zero. Therefore, there are exactly two points. These are given by the quadratic equation: 200/111 and 0.

Only one of these satisfies the second constraint: 200/111.

Why Can't I Find This Constraint With My Solver

The easy way out is to say it's because the x^2 term (x*y before the substitution is nonlinear). But it goes a little deeper than that. Nonlinear problems can be easy to solve as long as they are convex. A convex problem is one whose constraints form a single, contiguous space such that any line drawn between two points in the space stays within the boundaries of the space.

Your problem is not convex. The constraint 1.11 x^2-2*x=0 defines an infinite number of points. No two of these points can be connected by a straight line which stays in the space defined by the constraint because that space is curved. If the constraint were instead 1.11 x^2-2*x<=0 then the space would be convex because all points could be connected with straight lines that stay in its interior.

Nonconvex problems are part of a broader class of problems called NP-Hard. This means that there is not (and perhaps cannot) be any easy way of solving the problem. We have to be smart.

Solvers that can handle mixed-integer programming (MIP/MILP) can solve many non-convex problems efficiently, as can other techniques such as genetic algorithms. But, beneath the hood, these techniques all rely on glorified guess-and-check.

So your solver fails because the problem is nonconvex and your solver is neither smart enough to use MIP to guess-and-check its way to a solution nor smart enough to use the quadratic equation.

How Then Can I Solve The Problem?

In this particular instance, we are able to use mathematics to quickly find a solution because, although the problem is nonconvex, it is part of a class of special cases. Deep thinking by mathematicians has given us a simple way of handling this class.

But consider a few generalizations of the problem:

(a) a x^3+b x^2+c x+d=0
(b) a x^4+b x^3+c x^2+d x+e =0
(c) a x^5+b x^4+c x^3+d x^2+e x+f=0

(a) has three potential solutions which must be checked (exact solutions are tricky), (b) has four (trickier), and (c) has five. The formulas for (a) and (b) are much more complex than the quadratic formula and mathematicians have shown that there is no formula for (c) that can be expressed using "elementary operations". Instead, we have to resort to glorified guess-and-check.

So the techniques we used to solve your problem don't generalize very well. This is what it means to live in the realm of the nonconvex and NP-hard, and it's a good reason to fund research in mathematics, computer science, and related fields.

这篇关于lpsolve-不可行的解决方案，但我有示例1的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！