专栏首页数据魔术师干货 | JAVA调用cplex求解一个TSP模型详解

干货 | JAVA调用cplex求解一个TSP模型详解

前面我们已经搭建好cplex的java环境了,详情可以看干货 | cplex介绍、下载和安装以及java环境配置和API简单说明,相信大家已经跃跃欲试,想动手写几个模型了。

今天就来拿一个TSP的问题模型来给大家演示一下吧~

01 TSP建模

关于TSP建模,就不多解释了。以及什么是TSP问题,也不要问我了。直接贴一个现成的模型出来吧。

模型中:

V为集合中所含图的顶点。

约束(1-1)和(1-2)意味着对每个点而言,仅有一条边进和一条边出;

约束(1-3)则保证了解没有任何子回路。

于是,满足约束(1-1)、(1-2)和(1-3)的解构成了一条Hamilton回路。

02 程序框架

整个程序框架如图,app下是调用cplex的主要package。

其中:

在app包中:

App.java:程序入口,cplex调用建模求解过程。

ConstraintFactory.java:控制子环约束的。

FileManager.java:读取instance数据的。

在graph包中,定义了一些求解过程所需要的数据结构。

在graphics包中,将求解过程以图像形式动态的呈现出来。

input是算例,包含部分标准TSP算例和随机生成的规模为100-9000的算例。

images为graphics包在求解过程中保存下来的图像。

03 求解过程

先给大家看看程序流程图:

具体求解过程如下:

1. 定义一个模型

IloCplex model = new IloCplex();

2. 定义决策变量,boolVar可以返回一个0-1的bool类型决策变量。

// define variables
IloIntVar[][] x = new IloIntVar[data.size()][data.size()];
for (int i = 0; i < x.length; i++) {
    for (int j = 0; j < x.length; j++) {
        x[i][j] = model.boolVar("X[" + i + ", " + j + "]");
    }
}

3. 添加约束1-1,addTerm将1*x[i][j]添加进表达式r里面,最终r的取值是里面所有的元素之和,也就是1*x[i][1]+1*x[i][2]+...+1*x[i][n]。

// one has only a city to go, and should
for (int i = 0; i < x.length; i++) {
    IloLinearIntExpr r = model.linearIntExpr();
    for (int j = 0; j < x.length; j++) {
//                      if (i == j)
//                          continue;
        r.addTerm(1, x[i][j]);
    }
    model.addEq(r, 1);
}

4. 添加约束1-2,原理同上一条。

// one can only arrive to one city at a time, and should
for (int j = 0; j < x.length; j++) {
    IloLinearIntExpr r = model.linearIntExpr();
    for (int i = 0; i < x.length; i++) {
//                      if (i == j)
//                          continue;
        r.addTerm(1, x[i][j]);
    }
    model.addEq(r, 1);
}

5. 添加约束1-3,子环约束处理有点复杂,这个也是本文重点,小编来着重给大家讲讲。注意这个约束是和下面的manager.recycle(false)判断息息相关的。

constraintFactory.cycleRestrictions(model, x, stack);约束不能产生子环stack(stack是一个栈的数据结构,里面存了构成子环的各个边)。

而后面的manager.recycle(false),判断本次迭代cplex求解的最终解存不存在子环,如果存在,那么将子环添加进 stacks (注意这和stack不同,stacks保存的是各个子环。),在下一轮迭代中会约束该子环的产生。

如果不存在子环,显然已经是最优解。

// add cycle restrictions
for (Stack<Edge> stack : stacks) {
//                  stack.forEach((edge) -> System.out.println(edge.getFrom() + "->" + edge.getTo()));
    constraintFactory.cycleRestrictions(model, x, stack);
}

子环约束处理代码如下:

    public void cycleRestrictions(IloCplex model, IloIntVar[][] x, Stack<Edge> combindeds) throws IloException {
        IloLinearIntExpr r = model.linearIntExpr();
        for (Edge edge : combindeds) {
            r.addTerm(1, x[edge.getFrom()][edge.getTo()]);
        }
        model.addLe(r, combindeds.size() - 1);
    }

对于每个任意节点集合combindeds,只需要combindeds里面的边数小于combindeds的节点数,就能避免产生子环。

6. 添加目标函数,z的表达式同上。

// one should complete the tour within the smallest distance possible
IloLinearNumExpr z = model.linearNumExpr();
for (int i = 0; i < x.length; i++) {
    for (int j = 0; j < x.length; j++) {
        if (i == j)
            continue;
        z.addTerm(distance[i][j], x[i][j]);
    }
}

7. 确定目标是最小化目标。

model.addMinimize(z);

8. 开始求解。

if (model.solve()) {

    // get tour
    for (int i = 0; i < x.length; i++) {
        for (int j = 0; j < x.length; j++) {
            if (model.getValue(x[i][j]) >= 0.5) {
                tour.add(new Edge(i, j));
            }
        }
    }

    // repaint tour
} else {
    System.err.println("Boi, u sick!");
    System.exit(1);
}

注意,cplex在求解过程中会产生小数解的,虽然决策变量x[i][j]定义成了0-1变量,但是由于精度问题有可能会产生x[i][j]=0.00001或者x[i][j]=0.999999或者x[i][j]=0或者x[i][j]=1这样的数值。

model.getValue(x[i][j]) >= 0.5这个判断就是为了解决这种误差而产生的问题,当然你也可以定义成model.getValue(x[i][j]) >= 0.9、model.getValue(x[i][j]) >= 0.8、model.getValue(x[i][j]) >= 0.7等等都行。最终目的只是为了筛选那些x[i][j]=0.999999的边而已。

最终还是要进行一个判断,该判断是和上面的子环约束息息相关的:

boolean done= manager.recycle(false);
           if (done) {
               break;
           }

manager.recycle(false)判断的是求解的结果各边是否能构成一个Hamilton回路,因为整个程序是写在一个死循环里面不断迭代的:

while (true) {
      try {
          模型求解
          boolean done= manager.recycle(false);
           if (done) {
               break;
           }
      }

如果能构成一个Hamilton回路,break跳出死循环。如果不行,那么会把出现的子环更新进stacks,进行下一次迭代,重新调用cplex,在新的子环约束下,再把模型给求解一次。

然后讲讲怎么判断的,取决于参数all有两种判断方式:

1) all == true, 判断是tour是否只有一个环,如果是,那么满足Hamilton回路。

2) all == false, 找看看有没有子环。如果环的size == tour的size,那么该环满足Hamilton回路。

public boolean recycle(boolean all) {
    Stack<Edge> cycle = new Stack<Edge>();

    HashSet<Integer> visited = new HashSet<Integer>();

    int count = 0;

    if (all) {
        // all cycles
        while (visited.size() != tour.size()) {
            count++;
            for (Edge edge : this.tour) {
                if (!visited.contains(edge.getFrom())) {
                    visited.add(edge.getFrom());
                    Stack<Edge> tmp = new Stack<Edge>();
                    tmp.add(edge);
                    while (tmp.peek().getTo() != edge.getFrom()) {
                        Edge toPush = null;
                        for (Edge walk : this.tour) {
                            if (walk.getFrom() == tmp.peek().getTo()) {
                                visited.add(walk.getFrom());
                                toPush = walk;
                                break;
                            }
                        }
                        tmp.add(toPush);
                    }
                    this.stacks.add(tmp);
                    break;
                }
            }
        }
        return (count == 1);
    } else {
        // smallest cycle
        //System.out.println("tour size = "+tour.size());
        for (Edge edge : this.tour) {
            if (!visited.contains(edge.getFrom())) {
                visited.add(edge.getFrom());
                Stack<Edge> tmp = new Stack<Edge>();
                tmp.add(edge);
                while (tmp.peek().getTo() != edge.getFrom()) {
                    Edge toPush = null;
                    for (Edge walk : this.tour) {
                        if (walk.getFrom() == tmp.peek().getTo()) {
                            toPush = walk;
                            break;
                        }
                    }

                    if (toPush == null) {
                        for (int i = 0; i < this.stacks.size(); i++) {
                            Stack<Edge> toRelief = this.stacks.get(i);
                            if (toRelief.contains(tmp.peek()) || toRelief.contains(edge)) {
                                this.stacks.remove(toRelief);
                            }
                        }
                        break;
                    }
                    visited.add(toPush.getFrom());
                    tmp.push(toPush);
                }

                if (cycle.size() == 0 || tmp.size() < cycle.size()) {
                    cycle.clear();
                    cycle.addAll(tmp);
                }
            }
        }
        stacks.add(cycle);
        return cycle.size() == tour.size() ? true : false;
    }
}

代码来源GitHub,小编修正了部分代码。期待后期进一步精简和修改,大家下载下来后用eclipse导入,设置好cplex环境以后。

在App.java里面,右键Run As->Run configurations...:

找到App,在Arguments窗口,找到Program arguments:

输入参数说明:

--instancePath+空格+路径,注意用英文双引号括起来,表示算例文件的路径。

--maximumRead+空格+数字,表示算例大小,也就是需要读取多少个城市的数据。

--imagePath+空格+路径,表示所需要保存的图片路径,注意路径最后加两条斜杠\\。

--index+空格+数字,表示需要在图上标红的城市。

示例:

--instancePath "F:\19-java_code\CplexTSP\input\bier127.csv" --maximumRead 127 --imagePath "F:\19-java_code\CplexTSP\images\\" --index 0

然后为了防止在求解过程中内存给爆掉了,我们还需设置一个参数,在VM arguments里面输入【-Xms512m -Xmx2048m】不包括【】哦:

然后就可以愉快的run了。

附上运行结果:

动态图片展示【图片会动的哦,大家盯着看久一点!】:

下一期我们将会带来一些有趣的基于TSP算例的分析,敬请期待吧。

然后在文末打个小小的广告,小编的公众号【程序猿声】大家可以关注一下哦!

本文分享自微信公众号 - 数据魔术师(data-magician),作者:邓发珩

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-07-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 最短路问题与标号算法(label correcting algorithm)研究(3)

    本章将围绕Label Correcting Algorithms展开。首先,3.1小节介绍了最短路径最优性条件,这些条件允许我们评估一组距离标签是否达到最优,以...

    用户1621951
  • 从小白到年薪10万+,优秀的数据分析能力如何速成?

    用户1621951
  • “猜你喜欢”的背后揭秘——我偷偷知道你喜欢什么哟

    话说,最近的瓜实在有点多,从我科校友李雨桐怒锤某男、陈羽凡吸毒被捕、蒋劲夫家暴的三连瓜,到不知知网翟博士,再到邓紫棋解约蜂鸟、王思聪花千芳隔空互怼。

    用户1621951
  • 修正重发【CPLEX教程03】JAVA调用cplex求解一个TSP模型详解

    前面我们已经搭建好cplex的java环境了,详情可以看干货 | cplex介绍、下载和安装以及java环境配置和API简单说明,相信大家已经跃跃欲试,想动手写...

    短短的路走走停停
  • msf出现Database not connected等问题【已解决】

         kali启动msf后,出现Module database cache not built yet, using slow search,或是Datab...

    逆向小白
  • 茅明睿:开放,众包与规划改革[36页PPT]

    大数据文摘
  • Python第十六课:循环

    同If语句一样,循环语句也是编程语言的一个必备基本单元。一般而言,Python有两种方式可以实现循环语句,一种是for另一种便是while,我们先从稍微简单一点...

    HuangWeiAI
  • IOS数组为空的处理

    rectinajh
  • 千亿级金融场景下,基于Pulsar的云原生消息队列有怎样的表现?

    腾讯计费是孵化于支撑腾讯内部业务千亿级营收的互联网计费平台,其核心是帮助用户与产品,安全、便捷的完成支付和收款,在交易过程中帮助产品盈收实现最大化。

    腾小云
  • 个人站长自动推送(实时)提交链接。

    当前没有用到定时器,可以自己添加, 自家添加完成之后,添加sitemap.txt, 把 urls.txt 更换掉就可以。

    Wyc

扫码关注云+社区

领取腾讯云代金券