最小三角剖分（续）
前面发过一个关于这个问题的帖子，沉了。最近我又有了新的进展，将问题转化成了规划问题。但是看起来这个规划问题求解困难，因此再次向各位朋友求教。其实问题看起来很简单，就是在类似下图这样一个图上，
需要求它如下的一个子图
这是一个优化问题，是因为我想得到一个较小的子图（所使用三角形最少，或点最少）。
注意图的边界（较粗的边）是可以用现有算法计算得到的，就是求这个边界形成的多边形的一个三角剖分。
这个问题在无线网络中有着重要的应用，是我现在所做工作的前一部分。
最近我思考后将此问题建模为了一个规划问题，举一个简单的例子，如下图
在图中我给边都赋予了编号。按照这个编号，可以将所有三角形表示如下（注意计算所有三角形是可以在多项式时间内完成的）
注意每个三角形是有方向的，每条边也都有方向。B是指边界。
如T1，由边1，5，6构成，其方向为a1 -> a2 -> a5，因此边a1a5对应的值为-1.
于是问题转化为下面优化问题：
如果加上6个逆序的triangle，问题也可以构建为0-1规划如下
当然这也可以看成求线性方程组和最小的一组解的问题。
我需要求这个问题的精确解或近似解，总之不能用求解器或是简单的单纯形法求解。例如可以用主对偶方法等求近似解。同时能有求最优解和近似解的方法就更好了。
不知道论坛上有没有规划问题的专家。
请大家提供一些求解的思路，非常感谢。
如果有很擅长求解此类问题的朋友，可以联系我作为文章的共同作者。我的邮箱是:baixinbs@163.com
页:
[1]