2

我是 LPSolve 和工具包的新手。我正在尝试使用 LPSolve IDE 拼接 4 个图像 1024x1024 瓷砖。为了简化任务，我只使用瓷砖的 x 坐标。

    -------------------------------
   | Tile1         |Tile2          |
   |               |               |
   |               |               |
   |               |               |
   --------------------------------
   | Tile3         | Tile4         |
   |               |               |
   |               |               |
   |               |               |
   --------------------------------

如果我按以下方式定义关系

   min: +d1 +d3 +d4 +d6;

   -x1 +x2 -1024 +d1 <=0.1;
   -x1 +x2 -1024 +d1 >=-0.1;
   -x1 +x3 +1    +d2 <=0.1;
   -x1 +x3 +1    +d2 >=-0.1;
   -x2 +x4       +d3 <=0.1;
   -x2 +x4       +d3 >=-0.1;
   -x3 +x4 -1024 +d4 <=0.1;
   -x3 +x4 -1024 +d4 >=-0.1;
   x1=1024;
   x2=2048;
   x3=1023;
   x4=2047;

LPsolve 产生正确的结果

   d1=0
   d2=0
   d3=0.900000000000091
   d4=0
   x1=1024
   x2=2048
   x3=1023
   x4=2047

如果我将模型更改为以下，即将 Tile4 移动一个像素

   min: +d1 +d2 +d3 +d4;

   -x1 +x2 -1024 +d1 <=0.1;
   -x1 +x2 -1024 +d1 >=-0.1;
   -x1 +x3 +1    +d2 <=0.1;
   -x1 +x3 +1    +d2 >=-0.1;
   -x2 +x4       +d3 <=0.1;
   -x2 +x4       +d3 >=-0.1;
   -x3 +x4 -1024 +1 +d4 <=0.1;
   -x3 +x4 -1024 +1 +d4 >=-0.1;
   x1=1024;
   x2=2048;
   x3=1023;
   x4=2047;

LPSolve 以“模型不可行”响应，而我认为响应应该是

 d1=1
   d2=0
   d3=0.900000000000091
   d4=1

我究竟做错了什么？

4

1 回答 1

0

您遇到了扩展问题。lpsolve有很多。

如果你做一个小的改变，你可以自己看到：我在最后两个约束中替换了 x3 和 x4 的值：

 min: +d1 +d3 +d4 +d2;

   -x1 +x2 - 1024 +d1 <=0.1;
   -x1 +x2 - 1024 +d1 >=-0.1;
   -x1 +x3 +1    +d2 <=0.1;
   -x1 +x3 +1    +d2 >=-0.1;
   -x2 +x4      +d3 <=0.1;
   -x2 +x4       +d3 >=-0.1;
   -1023 + 2047  -1024 + 1 + d4 <= 0.1;
   -1023 +  x4   -1024 + 1 + d4 >=-0.1;
   x1=1024;
   x2=2048;
   x3=1023;
   x4=2047;

您收到此警告/错误：

initialize_solution: Invalid rebounding; variable 10 at refact 0, iter 0
check_solution: Variable   d4 =                  0 is above its upper bound               -0.9

Seriously low accuracy found ||*|| = 0.9 (rel. error 0.473684)
lp_solve failed

然而，当我尝试替换自己时：

 min: +d1 +d3 +d4 +d2;

   -x1 +x2 - 1024 +d1 <=0.1;
   -x1 +x2 - 1024 +d1 >=-0.1;
   -x1 +x3 +1    +d2 <=0.1;
   -x1 +x3 +1    +d2 >=-0.1;
   -x2 +x4      +d3 <=0.1;
   -x2 +x4       +d3 >=-0.1;
//   -1023 + 2047  -1024 + 1 + d4 <= 0.1;
//   -1023 +  x4   -1024 + 1 + d4 >=-0.1;
  d4 <= 0.1;
  d4 >-0.1;
   x1=1024;
   x2=2048;
   x3=1023;
   x4=2047;

我们得到了一个解决方案，并且没有不可行：

Actual values of the variables:
d1                              0
d3                            0.9
d4                           -0.1
d2                              0
x1                           1024
x2                           2048
x3                           1023
x4                           2047

这个链接告诉你发生了什么。

从那里的最后一行引用：

结论。您应该始终进行某种缩放。它从您设计模型时开始。额外的缩放可以通过 lp_solve 的缩放选项之一来完成。

希望有帮助。

于 2014-05-23T19:25:21.167 回答