【运筹优化】拉格朗日松弛 次梯度算法求解整数规划问题 + 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。

相关文章

网页解析 lxml 库--实战

网页解析 lxml 库--实战

lxml库使用流程 lxml 是 Python 的第三方解析库，完全使用 Python 语言编写，它对 XPath表达式提供了良好的支 持，因此能够了高效地解析 HTML/XML 文档。本节讲解如何通过 lxml 库解析 HTML 文档。 pip install lxml lxm| 库提供了一个 etree 模块，该模块专门用来解析 HTML/XML 文档，下面来介绍一下 lxml 库
阅读更多...
Vue3 的 shallowRef 和 shallowReactive：优化性能

Vue3 的 shallowRef 和 shallowReactive：优化性能

大家对 Vue3 的 ref 和 reactive 都很熟悉，那么对 shallowRef 和 shallowReactive 是否了解呢？ 在编程和数据结构中，“shallow”（浅层）通常指对数据结构的最外层进行操作，而不递归地处理其内部或嵌套的数据。这种处理方式关注的是数据结构的第一层属性或元素，而忽略更深层次的嵌套内容。 1. 浅层与深层的对比 1.1 浅层（Shallow） 定义
阅读更多...
JVM 的类初始化机制

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时，有没有考虑过 JVM 是如何把静态的字节码（byte code）转化为运行时对象的呢，这个问题看似简单，但清楚的同学相信也不会太多，这篇文章首先介绍 JVM 类初始化的机制，然后给出几个易出错的实例来分析，帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段，分别是：loading 、Linking、initialization
阅读更多...
Spring Security 基于表达式的权限控制

Spring Security 基于表达式的权限控制

前言 spring security 3.0已经可以使用spring el表达式来控制授权，允许在表达式中使用复杂的布尔逻辑来控制访问的权限。 常见的表达式 Spring Security可用表达式对象的基类是SecurityExpressionRoot。 表达式描述hasRole([role])用户拥有制定的角色时返回true （Spring security默认会带有ROLE_前缀）,去
阅读更多...
浅析Spring Security认证过程

浅析Spring Security认证过程

类图 为了方便理解Spring Security认证流程，特意画了如下的类图，包含相关的核心认证类 概述 核心验证器 AuthenticationManager 该对象提供了认证方法的入口，接收一个Authentiaton对象作为参数; public interface AuthenticationManager {Authentication authenticate(Authenti
阅读更多...
Spring Security--Architecture Overview

Spring Security--Architecture Overview

1 核心组件 这一节主要介绍一些在Spring Security中常见且核心的Java类，它们之间的依赖，构建起了整个框架。想要理解整个架构，最起码得对这些类眼熟。 1.1 SecurityContextHolder SecurityContextHolder用于存储安全上下文（security context）的信息。当前操作的用户是谁，该用户是否已经被认证，他拥有哪些角色权限…这些都被保
阅读更多...
Spring Security基于数据库验证流程详解

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明（认真看哦） AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证，则会调用 #attemptAuthentica
阅读更多...
Spring Security 从入门到进阶系列教程

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门（一）：登录与退出》 《Spring-Security-入门（二）：基于数据库验证》 《Spring-Security-入门（三）：密码加密》 《Spring-Security-入门（四）：自定义-Filter》 《Spring-Security-入门（五）：在 Sprin
阅读更多...
Java架构师知识体认识

Java架构师知识体认识

源码分析 常用设计模式 Proxy代理模式Factory工厂模式Singleton单例模式Delegate委派模式Strategy策略模式Prototype原型模式Template模板模式 Spring5 beans 接口实例化代理Bean操作 Context Ioc容器设计原理及高级特性Aop设计原理Factorybean与Beanfactory Transaction 声明式事物
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2