【运筹优化】拉格朗日松弛 次梯度算法求解整数规划问题 + Java调用Cplex实战

2023-10-12 22:20
文章标签 java 算法 实战 规划 问题 优化 调用 整数 拉格朗 求解 松弛 cplex 次梯度 运筹

本文主要是介绍【运筹优化】拉格朗日松弛 次梯度算法求解整数规划问题 + Java调用Cplex实战，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 一、拉格朗日松弛
  • 二、次梯度算法
  • 三、案例实战

一、拉格朗日松弛

当遇到一些很难求解的模型，但又不需要去求解它的精确解，只需要给出一个次优解或者解的上下界，这时便可以考虑采用松弛模型的方法加以求解。

对于一个整数规划问题，拉格朗日松弛放松模型中的部分约束。这些被松弛的约束并不是被完全去掉，而是利用拉格朗日乘子在目标函数上增加相应的惩罚项，对不满足这些约束条件的解进行惩罚。

拉格朗日松弛之所以受关注，是因为在大规模的组合优化问题中，若能在原问题中减少一些造成问题“难”的约束，则可使问题求解难度大大降低，有时甚至可以得到比线性松弛更好的上下界。

在这里插入图片描述
在这里插入图片描述

二、次梯度算法

由于拉格朗日对偶问题通常是分段线性的，这会导致其在某些段上不可导，所以没法使用常规的梯度下降法处理。于是引入次梯度（Subgradient）用于解决此类目标函数并不总是处处可导的问题。

次梯度算法的优势是比传统方法能够处理的问题范围更大，不足之处就是算法收敛速度慢。

在这里插入图片描述

在这里插入图片描述

三、案例实战

在这里插入图片描述
在这里插入图片描述

松弛之后的目标函数为

m a x : z = 16 x 1 + 10 x 2 + 4 x 4 + μ [ 10 − ( 8 x 1 + 2 x 2 + x 3 + 4 x 4 ) ] max :z=16x_1+10x_2+4x_4+\mu[10-(8x_1+2x_2+x_3+4x_4)] max:z=16x1​+10x2​+4x4​+μ[10−(8x1​+2x2​+x3​+4x4​)]

化简为

m a x : z = ( 16 − 8 μ ) x 1 + ( 10 − 2 μ ) x 2 + ( − μ ) x 3 + ( 4 − 4 μ ) x 4 + 10 μ max :z=(16-8\mu)x_1+(10-2\mu)x_2+(-\mu)x_3+(4-4\mu)x_4+10\mu max:z=(16−8μ)x1​+(10−2μ)x2​+(−μ)x3​+(4−4μ)x4​+10μ

由于每一次迭代时 μ \mu μ 是一个确定的常数，所以目标函数中的 10 μ 10\mu 10μ 可以在建模时省略

具体求解代码如下：

import ilog.concert.IloException;
import ilog.concert.IloIntVar;
import ilog.concert.IloLinearNumExpr;
import ilog.cplex.IloCplex;import java.util.Arrays;public class TestLR {// lambdastatic double lambda = 2d;// 最大迭代次数static int epochs = 100;// 上界最大未更新次数static int ubMaxNonImproveCnt = 3;// 最小步长static double minStep = 0.001;// 松弛问题模型static IloCplex relaxProblemModel;// 变量数组static IloIntVar[] intVars;// 最佳上下界static double bestLB = 0d;static double bestUB = 1e10;// 最佳拉格朗日乘数static double bestMu = 0d;// 最佳解static double[] bestX;// 运行主函数public static void run() throws IloException {//double mu = 0d;double step = 1d;int ubNonImproveCnt = 0;// 初始化松弛问题模型initRelaxModel();// 开始迭代for (int epoch = 0; epoch < epochs; epoch++) {System.out.println("----------------------------- Epoch-" + (epoch + 1) + " -----------------------------");System.out.println("mu: " + mu);System.out.println("lambda: " + lambda);// 根据mu，设置松弛问题模型目标函数setRelaxModelObjectiveBuMu(mu);if (relaxProblemModel.solve()) {// 获得当前上界（由于建模时没有考虑常数 10*mu，所以这里要加回来，得到松弛问题的真正目标值）double curUB = relaxProblemModel.getObjValue() + 10 * mu;// 更新上界if (curUB < bestUB) {bestUB = curUB;ubNonImproveCnt = 0;} else {ubNonImproveCnt++;}System.out.println("curUB: " + curUB);// 获取变量值double[] x = relaxProblemModel.getValues(intVars);// 计算次梯度double subGradient = (8 * x[0] + 2 * x[1] + x[2] + 4 * x[3]) - 10;double dist = Math.pow(subGradient, 2);// 迭迭代停止条件1if (dist <= 0.0) {System.out.println("Early stop: dist (" + dist + ") <= 0 !");break;}// 如果次梯度大于等于0，说明满足被松弛的约束，即可以作为原问题的可行解if (subGradient <= 0) {// 计算当前原问题的解值double obj = 16 * x[0] + 10 * x[1] + 4 * x[3];if (obj > bestLB) {// 更新下界bestLB = obj;bestMu = mu;bestX = x.clone();}}System.out.println("subGradient: " + subGradient);System.out.println("bestUB: " + bestUB);System.out.println("bestLB: " + bestLB);System.out.println("gap: " + String.format("%.2f", (bestUB - bestLB) * 100d / bestUB) + " %");// 迭代停止条件2if (bestLB >= bestUB - 1e-06) {System.out.println("Early stop: bestLB (" + bestLB + ") >= bestUB (" + bestUB + ") !");break;}// 上界未更新达到一定次数if (ubNonImproveCnt >= ubMaxNonImproveCnt) {lambda /= 2;ubNonImproveCnt = 0;}// 更新拉格朗日乘数mu = Math.max(0, mu + step * subGradient);// 更新步长step = lambda * (curUB - bestLB) / dist;// 迭代停止条件3if (step < minStep) {System.out.println("Early stop: step (" + step + ") is less than minStep (" + minStep + ") !");break;}} else {System.err.println("Lagrange relaxation problem has no solution!");}}}// 建立松弛问题模型private static void initRelaxModel() throws IloException {relaxProblemModel = new IloCplex();relaxProblemModel.setOut(null);// 声明4个整数变量intVars = relaxProblemModel.intVarArray(4, 0, 1);// 添加约束// 约束1：x1+x2<=1relaxProblemModel.addLe(relaxProblemModel.sum(intVars[0], intVars[1]), 1);// 约束2：x3+x4<=1relaxProblemModel.addLe(relaxProblemModel.sum(intVars[2], intVars[3]), 1);}// 根据mu，设置松弛问题模型的目标函数private static void setRelaxModelObjectiveBuMu(double mu) throws IloException {// 目标函数（省略了常数 10*mu）IloLinearNumExpr target = relaxProblemModel.linearNumExpr();target.addTerm(16 - 8 * mu, intVars[0]);target.addTerm(10 - 2 * mu, intVars[1]);target.addTerm(0 - mu, intVars[2]);target.addTerm(4 - 4 * mu, intVars[3]);if (relaxProblemModel.getObjective() == null) {relaxProblemModel.addMaximize(target);} else {relaxProblemModel.getObjective().setExpr(target);}}public static void main(String[] args) throws IloException {long s = System.currentTimeMillis();run();System.out.println("----------------------------- Solution -----------------------------");System.out.println("bestMu: " + bestMu);System.out.println("bestUB: " + bestUB);System.out.println("bestLB: " + bestLB);System.out.println("gap: " + String.format("%.2f", (bestUB - bestLB) * 100d / bestUB) + " %");System.out.println("bestX: " + Arrays.toString(bestX));System.out.println("Solve Time: " + (System.currentTimeMillis() - s) + " ms");}}

程序输出：

----------------------------- Epoch-1 -----------------------------
mu: 0.0
lambda: 2.0
curUB: 20.0
subGradient: 2.0
bestUB: 20.0
bestLB: 0.0
gap: 100.00 %
----------------------------- Epoch-2 -----------------------------
mu: 2.0
lambda: 2.0
curUB: 26.0
subGradient: -8.0
bestUB: 20.0
bestLB: 10.0
gap: 50.00 %
----------------------------- Epoch-3 -----------------------------
mu: 0.0
lambda: 2.0
curUB: 20.0
subGradient: 2.0
bestUB: 20.0
bestLB: 10.0
gap: 50.00 %
----------------------------- Epoch-4 -----------------------------
mu: 1.0
lambda: 2.0
curUB: 18.0
subGradient: 2.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-5 -----------------------------
mu: 11.0
lambda: 2.0
curUB: 110.0
subGradient: -10.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-6 -----------------------------
mu: 0.0
lambda: 2.0
curUB: 20.0
subGradient: 2.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-7 -----------------------------
mu: 4.0
lambda: 2.0
curUB: 42.0
subGradient: -8.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-8 -----------------------------
mu: 0.0
lambda: 1.0
curUB: 20.0
subGradient: 2.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-9 -----------------------------
mu: 1.0
lambda: 1.0
curUB: 18.0
subGradient: 2.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-10 -----------------------------
mu: 6.0
lambda: 1.0
curUB: 60.0
subGradient: -10.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-11 -----------------------------
mu: 0.0
lambda: 0.5
curUB: 20.0
subGradient: 2.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-12 -----------------------------
mu: 0.5
lambda: 0.5
curUB: 19.0
subGradient: 2.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-13 -----------------------------
mu: 3.0
lambda: 0.5
curUB: 34.0
subGradient: -8.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-14 -----------------------------
mu: 0.0
lambda: 0.25
curUB: 20.0
subGradient: 2.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-15 -----------------------------
mu: 0.1875
lambda: 0.25
curUB: 19.625
subGradient: 2.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-16 -----------------------------
mu: 1.4375
lambda: 0.25
curUB: 21.5
subGradient: -8.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-17 -----------------------------
mu: 0.0
lambda: 0.125
curUB: 20.0
subGradient: 2.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-18 -----------------------------
mu: 0.044921875
lambda: 0.125
curUB: 19.91015625
subGradient: 2.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-19 -----------------------------
mu: 0.669921875
lambda: 0.125
curUB: 18.66015625
subGradient: 2.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-20 -----------------------------
mu: 1.289306640625
lambda: 0.0625
curUB: 20.314453125
subGradient: -8.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-21 -----------------------------
mu: 0.206787109375
lambda: 0.0625
curUB: 19.58642578125
subGradient: 2.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-22 -----------------------------
mu: 0.22693252563476562
lambda: 0.0625
curUB: 19.54613494873047
subGradient: 2.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-23 -----------------------------
mu: 0.5265083312988281
lambda: 0.03125
curUB: 18.946983337402344
subGradient: 2.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-24 -----------------------------
mu: 0.6756666898727417
lambda: 0.03125
curUB: 18.648666620254517
subGradient: 2.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-25 -----------------------------
mu: 0.8154633045196533
lambda: 0.03125
curUB: 18.369073390960693
subGradient: 2.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-26 -----------------------------
mu: 0.9505987204611301
lambda: 0.015625
curUB: 18.09880255907774
subGradient: 2.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-27 -----------------------------
mu: 1.0159821063280106
lambda: 0.015625
curUB: 18.127856850624084
subGradient: -8.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-28 -----------------------------
mu: 0.7628945263568312
lambda: 0.015625
curUB: 18.474210947286338
subGradient: 2.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-29 -----------------------------
mu: 0.766863206459675
lambda: 0.0078125
curUB: 18.46627358708065
subGradient: 2.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-30 -----------------------------
mu: 0.7999655929725122
lambda: 0.0078125
curUB: 18.400068814054976
subGradient: 2.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-31 -----------------------------
mu: 0.833036974172046
lambda: 0.0078125
curUB: 18.333926051655908
subGradient: 2.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-32 -----------------------------
mu: 0.8658497429769483
lambda: 0.00390625
curUB: 18.268300514046103
subGradient: 2.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-33 -----------------------------
mu: 0.8821269422965887
lambda: 0.00390625
curUB: 18.235746115406823
subGradient: 2.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-34 -----------------------------
mu: 0.8982759667380851
lambda: 0.00390625
curUB: 18.20344806652383
subGradient: 2.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-35 -----------------------------
mu: 0.914361408369739
lambda: 0.001953125
curUB: 18.17127718326052
subGradient: 2.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-36 -----------------------------
mu: 0.9223725881222037
lambda: 0.001953125
curUB: 18.155254823755595
subGradient: 2.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-37 -----------------------------
mu: 0.9303523509964815
lambda: 0.001953125
curUB: 18.13929529800704
subGradient: 2.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-38 -----------------------------
mu: 0.9383164670353054
lambda: 9.765625E-4
curUB: 18.123367065929386
subGradient: 2.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-39 -----------------------------
mu: 0.9422907323175354
lambda: 9.765625E-4
curUB: 18.11541853536493
subGradient: 2.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
----------------------------- Epoch-40 -----------------------------
mu: 0.9462572201426962
lambda: 9.765625E-4
curUB: 18.107485559714608
subGradient: 2.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
Early stop: step (9.896832958635996E-4) is less than minStep (0.001) !
----------------------------- Solution -----------------------------
bestMu: 2.0
bestUB: 18.0
bestLB: 10.0
gap: 44.44 %
bestX: [0.0, 1.0, 0.0, 0.0]
Solve Time: 152 ms

分析：
从最终结果可以看到， bestLB 为10，也就是通过拉格朗日松弛&次梯度算法得到的最优可行解的目标值为10，这明显不是最优解（最优解应该是16， x 1 = 1 x_1=1 x1​=1，其余变量为0）
这是因为我们松弛了一个约束，所以通过拉格朗日松弛&次梯度算法得到的解不一定是最优解。但是当遇到一些很难求解的模型，但又不需要去求解它的精确解时，拉格朗日松弛&次梯度算法就可以派上用场了！

参考链接：

  • 【凸优化笔记5】-次梯度方法（Subgradient method）
  • 运筹学教学|快醒醒，你的熟人拉格朗日又来了！！
  • 拉格朗日松弛求解整数规划浅析（附Python代码实例）

这篇关于【运筹优化】拉格朗日松弛 次梯度算法求解整数规划问题 + Java调用Cplex实战的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/198826。

相关文章

Java的栈与队列实现代码解析

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念（Stack）栈的实现代码队列（Queue）模拟实现队列(双链表实现)循环队列（循环数组
阅读更多...
usb接口驱动异常问题常用解决方案

usb接口驱动异常问题常用解决方案

《usb接口驱动异常问题常用解决方案》当遇到USB接口驱动异常时，可以通过多种方法来解决，其中主要就包括重装USB控制器、禁用USB选择性暂停设置、更新或安装新的主板驱动等... usb接口驱动异常怎么办，USB接口驱动异常是常见问题，通常由驱动损坏、系统更新冲突、硬件故障或电源管理设置导致。以下是常用解决
阅读更多...
Java中Switch Case多个条件处理方法举例

Java中Switch Case多个条件处理方法举例

《Java中SwitchCase多个条件处理方法举例》Java中switch语句用于根据变量值执行不同代码块,适用于多个条件的处理,：本文主要介绍Java中SwitchCase多个条件处理的相... 目录前言基本语法处理多个条件示例1：合并相同代码的多个case示例2：通过字符串合并多个case进阶用法使用
阅读更多...
Java中的Lambda表达式及其应用小结

Java中的Lambda表达式及其应用小结

《Java中的Lambda表达式及其应用小结》Java中的Lambda表达式是一项极具创新性的特性,它使得Java代码更加简洁和高效,尤其是在集合操作和并行处理方面,：本文主要介绍Java中的La... 目录前言1. 什么是Lambda表达式？2. Lambda表达式的基本语法例子1：最简单的Lambda表
阅读更多...
Java中Scanner的用法示例小结

Java中Scanner的用法示例小结

《Java中Scanner的用法示例小结》有时候我们在编写代码的时候可能会使用输入和输出,那Java也有自己的输入和输出,今天我们来探究一下,对JavaScanner用法相关知识感兴趣的朋友一起看看吧... 目录前言一 输出二 输入Scanner的使用多组输入三 综合练习：猜数字游戏猜数字前言有时候我们在
阅读更多...
Mysql如何解决死锁问题

Mysql如何解决死锁问题

《Mysql如何解决死锁问题》：本文主要介绍Mysql如何解决死锁问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录【一】mysql中锁分类和加锁情况【1】按锁的粒度分类全局锁表级锁行级锁【2】按锁的模式分类【二】加锁方式的影响因素【三】Mysql的死锁情况【1
阅读更多...
Spring Security+JWT如何实现前后端分离权限控制

Spring Security+JWT如何实现前后端分离权限控制

《SpringSecurity+JWT如何实现前后端分离权限控制》本篇将手把手教你用SpringSecurity+JWT搭建一套完整的登录认证与权限控制体系,具有很好的参考价值,希望对大家... 目录Spring Security+JWT实现前后端分离权限控制实战一、为什么要用 JWT？二、JWT 基本结构
阅读更多...
java解析jwt中的payload的用法

java解析jwt中的payload的用法

《java解析jwt中的payload的用法》：本文主要介绍java解析jwt中的payload的用法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java解析jwt中的payload1. 使用 jjwt 库步骤 1：添加依赖步骤 2：解析 JWT2. 使用 N
阅读更多...
springboot项目如何开启https服务

springboot项目如何开启https服务

《springboot项目如何开启https服务》：本文主要介绍springboot项目如何开启https服务方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录springboot项目开启https服务1. 生成SSL证书密钥库使用keytool生成自签名证书将
阅读更多...
Java实现优雅日期处理的方案详解

Java实现优雅日期处理的方案详解

《Java实现优雅日期处理的方案详解》在我们的日常工作中,需要经常处理各种格式,各种类似的的日期或者时间,下面我们就来看看如何使用java处理这样的日期问题吧,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言一、日期的坑1.1 日期格式化陷阱1.2 时区转换二、优雅方案的进阶之路2.1 线程安全重构2
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2