工具与工具版本

使用power point 2019+或office 365，不要使用WPS以避免与office混用的格式错误。

使用2019+版本的原因是部分功能（例如，平滑切换）在此版本加入，另外使用旧版本的Office（可能）有潜在的兼容性问题。

制作原则

• 最小化外部依赖： 能在 ppt 内部实现的 不要用外部软件（mathtype公式，简单画图，简单调色等）
• 尽可能复用：复用对象，避免新建对象导致字体、对齐不一致等格式问题 ，一次实现，多次复制使用
• 简单实现：能通过简单方法实现的效果，不要使用复杂方法

命名与文件版本

PPT命名规则为 项目名_版本号_月份(英大写)_日期_修改人_修改内容概述

例如：新朔_0.0.1_APR_18_YRF_新建文档

其中，版本号使用语义化版本（Semantic Versioning）

1. 主版本号：当你做了不兼容的修改（例如，换模板等颠覆性操作，与别人修改的版本再也无法兼容）
2. 次版本号：当你做了向下兼容的功能性新增（例如，新增某个章节）
3. 修订号：当你做了向下兼容的问题修正（例如，修改了错别字）

不要在任何时刻定义final版本，避免出现final-final-final版。

应当有唯一一人负责版本合并，作为主分支

日志

每页ppt应该有从新建、修改、删除的详细日志

谁在什么时候做了什么修改，放在ppt图框外面的一个文本框内

2025.01.01 YRF 新建此页

2025.01.02 YRF 修改公式的动画

2025.01.05 YRF 新增切换样式

2025.01.05 SJY 因演讲超时弃用此页

删除

任何制作出来的页，在弃用时不应删除（不知何时会再次启用），应放置到所有页的末尾，并在日志中标明弃用及原因

字体

尽量不要将无衬线字体和有衬线字体混合排版，常用字体：

• 无衬线字体
  • 微软雅黑
  • Arial
  • 黑体
  • 等线
  • …
• 有衬线字体
  • 宋体
  • Times new Roman
  • …

插图

ppt插图尽量高清，低分辨率图片可用AI方法放大修复，例如 upscayl或bigjpg 等。

配色

ppt配色应围绕主题色进行修改，建议建立取色卡。

尽量不要使用亮度、饱和度过高的红色、绿色、黄色等。

不建议同一页面使用过多颜色搭配，建议使用同色系颜色进行搭配。

动画

动画应简洁、美观、丝滑、快速（不宜过长等待）。动画应当辅助核心内容，而不是为了制作动画而制作。

文件管理

保留可编辑的素材、源图、公式等，避免二次制作。

风格

扁平风格不要与写实或立体风格混用

背景

背景可以为白色，也可添加背景色，但不要使用带纹理的背景。

注意：若背景不为白色，则不要使用白色块（原因：丑，像补丁）

公式

公式尽量使用ppt自带公式编辑器，不要插入图片，不用使用mathtype（可能无法编辑）

表格

表格要简洁，小数的小数点对齐且保留相同位数，整数统一右对齐

地图

使用地图一定要小心敏感地区：台湾、藏南、香港是我国领土的一部分。

在线协作

微软office 365与onedrive目前有在线协作的功能，可作为主分支进行合并以及最后的共同校验。

杂项

善用锁定和组合，善用内部文字左右居中对齐、对象排列

考虑去除句尾的句号

以往都是用Python调用Gurobi进行数学规划建模，最近开始涉及C的编程。由于不想使用C和python联合编程（也许是C调用一个Python解释器？总之，没这样去做），所以直接用C调用Gurobi了。
由于我用的是mac，因此VScode + Cmake是最佳的组合，本文主要记录的是Cmake文件应该如何编写。(Windows系统请不要参考这个教程，不能保证正确性)

首先，这是Gurobi官方的链接：
https://support.gurobi.com/hc/en-us/articles/360039499751-How-do-I-use-CMake-to-build-Gurobi-C-C-projects

按照官方的链接，在Gurobi正确安装的情况下， mip1_c++.cpp亲测可以运行。如果发现，上述的教程不能通过Cmake编译，且原因是找不到Gurobi，那大概率是Gurobi的环境变量设置的有问题了，需要修改环境变量到指定的路径，
这里放上macos的.zshrc设置。

1
2

export GUROBI_LICENSE_FILE=/Users/yurunfeng/gurobi.lic
export GUROBI_HOME=/Library/gurobi1103/macos_universal2

配置好环境变量，编译应该就没问题了。

在自己的项目中，把FindGUROBI.cmake文件直接放在工程目录中， CmakeLists.txt 需要自己更改。FindGUROBI.cmake也可根据需要进行更改，
比如以下这个例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

# CmakeLists.txt 
# 这只是一个例子，如果不知道是什么意思的话，不要直接抄，肯定是运行不了的
cmake_minimum_required(VERSION 3.29)
cmake_policy(SET CMP0167 NEW)
enable_language(CXX)

# set(CMAKE_OSX_ARCHITECTURES "arm64")
# set(GUROBI_INCLUDE_DIRS "/Library/gurobi1103/macos_universal2/include")  
# set(GUROBI_CXX_LIBRARY "/Library/gurobi1103/macos_universal2/lib/libgurobi_c++.a") 
set(CMAKE_PREFIX_PATH "/Users/yurunfeng/vcpkg/installed/arm64-osx/share")
set(CMAKE_BUILD_TYPE "Debug")
set(CMAKE_EXPORT_COMPILE_COMMANDS 1)
set(CMAKE_CXX_STANDARD 20)
set(CMAKE_CXX_STANDARD_REQUIRED True)
set(CXXFLAGS -D_GNU_SOURCE True)

project(FWPSP)

list(APPEND CMAKE_MODULE_PATH ${PROJECT_SOURCE_DIR})

find_package(nlohmann_json CONFIG REQUIRED) # json 
find_package(Boost REQUIRED COMPONENTS program_options stacktrace_basic stacktrace_noop system)
find_package(Boost REQUIRED COMPONENTS log log_setup thread filesystem system date_time regex)
find_package(GUROBI REQUIRED)

include_directories(${GUROBI_INCLUDE_DIRS})
include_directories(${Boost_INCLUDE_DIRS})

set(sources 
  src/main.cpp
  src/alg_config.cpp
  src/log_config.cpp
  src/ip_model.cpp
  src/data_loader.cpp
  src/cbs_node.cpp
  src/cbs.cpp
  src/node_manager.cpp
)

add_executable(${CMAKE_PROJECT_NAME} ${sources})

target_include_directories(FWPSP PRIVATE ${CMAKE_SOURCE_DIR}/inc)
target_link_libraries(${CMAKE_PROJECT_NAME} 
        nlohmann_json::nlohmann_json 
        ${Boost_LIBRARIES}
        ${GUROBI_LIBRARY}
        optimized ${GUROBI_CXX_LIBRARY}
        debug ${GUROBI_CXX_LIBRARY}
)

if(${CMAKE_SOURCE_DIR} STREQUAL ${CMAKE_CURRENT_SOURCE_DIR})
  include(FeatureSummary)
  feature_summary(WHAT ALL)
endif()

总之，重点在于如何告诉Cmake链接到Gurobi，如果某个环节错了的话，那就检查这个环节的问题，Cmake不熟悉也只能多学习Cmake了（因为我也不熟悉啊🥹）。
此外，如果Gurobi的环境变量没设置也没关系，上述的CmakeLists.txt被注释的部分就是设置Gurobi的路径(macos)：

1
2

set(GUROBI_INCLUDE_DIRS "/Library/gurobi1103/macos_universal2/include")  
set(GUROBI_CXX_LIBRARY "/Library/gurobi1103/macos_universal2/lib/libgurobi_c++.a") 

在使用Latex写作时，经常遇到数学优化模型的排版问题。在一般情况下，我希望写一个具有最小化\最大化的目标公式，
约束、以及“subject to: ”或者“s.t.: ”这样的约束前缀。
完成这样的任务涉及到一些Latex公式对齐的问题, 经过测试，以下两个实现方式效果最佳。

公式独立标号

先放源码：

1
2
3
4
5

\begin{align}
  & \min Cx \label{eq:obj} \\
  \mbox{subject to: } \quad & Ax = b \label{eq:constr} \\
  & x \ge 0
\end{align}

编译结果如下：

公式共用一个编号（适合多个模型的情况）

1
2
3
4
5
6
7
8
9
10

\begin{subequations}
\label{eq:optim}
\begin{align}
    \underset{X}{\text{minimize}}
        & \quad \mathrm{trace}(X)   \label{eq:cost}\\
    \text{subject to} 
        & \quad X_{ij} = M_{ij}\,, \; (i,j) \in \Omega\,, \label{eq:const1}\\
        & \quad X \succeq 0 \,. \label{eq:const2}
\end{align}
\end{subequations}

编译结果如下：

前几天刷到一个公众号上的推文，关于CVRP的两索引的建模，其中有一个约束是条件约束。
之前我遇到条件约束都是手工转成线性约束，然后输入gurobi中，一方面是锻炼自己线性化的能力，另一方面是懒的翻手册查找方法。
然后发现Gurobi是真好用，内置了条件约束的添加方法。

条件约束的广义形式见文章末尾的参考来源，这里只是举一个例子, 如下：

$$x_{ij} = 1 \rightarrow u_i + q_i = u_j, \quad i,j \in A, j \ne 0, i \ne 0$$

上面的约束表明只有在$x_{ij} = 1$的情况下，$u_i + q_i = u_j$才成立，其中$x,u$是决策变量。
Gurobi添加的约束如下（python）：

1

m.addConstrs((X[i,j] == 1) >> (Y[i] + demand[j] == Y[j]) for i,j in A if i!=1 and j!= 1)

方法不止这一种，上述的是重载的形式，原来的形式应该使用addGenConstrIndicator这个方法，详见参考链接。

参考文章：
https://gurobi.com/documentation/current/refman/py_model_agc_indicator.html

最近在写一个论文，审稿人让我增加一部分的实验内容，验证我启发式的性能。我选择和Gurobi进行对比。
然后在我和Gurobi进行对比的过程中，发现某几个算例的启发式结果竟然比Gurobi的下界（gap=0）还低。
按道理来说，对于一个最小化的问题，上界是不可能比下界还低的，因此我怀疑是我的启发式算法有bug，最开始我是不相信Gurobi会有问题的。

复杂的验证过程以及漫长的Debug中，我发现自己的算法好像并没有什么问题，而且只有一两个算例出现了上述的情况。
接着我发现如果我减少FeasibilityTol和OptimalityTol这两个参数（至最小值10e-9）以提升数值精度，那么情况有会有所改善，但是启发式的结果依旧比下界还低。

然后，我使用了一个常见的方法，强制决策变量等于启发式的解，把启发式的结果制作成约束添加进模型中，再求解发现Gurobi的结果竟然和我的启发式一致了，且gap等于0。这就出现了悖论：

• 在那几个特殊的算例中（增加额外的约束gap=0，不增加约束也是gap=0），最小化问题增加额外的约束竟然使最优目标值更小了。

这让我觉得太离谱了，增加额外约束最好的情况下也只能是和原问题的最优目标值一致。
然后和Gurobi社区的工作人员拉扯了一个月，终于搞清楚了，Gurobi承认有bug，并且只能在下个版本修复了。

在此附上原帖子链接，纪念一下第一次为一个求解器厂商提出实质性bug。

https://support.gurobi.com/hc/en-us/community/posts/27254595262993-Add-additional-constraints-but-the-objective-decreased-in-minimize-problem

声明：

• 原文之前发表在本人的CSDN上，现搬运到博客里。
• 本文的目的是记录和分享学到的知识。作者已尽一切努力确保本文内容的准确性。作者在此声明不承担因本文中的错误或遗漏造成的任何损失所带来的责任，无论这些错误或遗漏是意外、疏忽或其他原因导致的。
• 转载请备注来源，欢迎点赞、收藏或指出本文不足。
• 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
• 本文链接：https://blog.csdn.net/weixin_45746917/article/details/125524606

本文由作者用心整理，希望对您有所帮助。如果您入门或困扰于该问题，请您静下心来阅读，准备纸笔推导，一定会有所收获。所有例子和引证均带有来源，可点超链接深入了解。

概述

  拉格朗日松弛是一种求解整数规划的、基于优化的启发式算法。该算法能提供较为优质的解，可证明解的质量（可得到优化上下界），但不保证最优性。拉格朗日松弛的应用十分广泛，例如无容量限制的设施选址问题（该问题为NP-hard问题）。
  拉格朗日松弛算法可追溯到Everett 1963年，Fisher 1973使用了该算法求解了调度问题。注意，该算法并不是拉格朗日提出的，是借鉴了拉格朗日乘子法的一些启示，由(Geoffrion 1974)命名。

• 松弛方法对于一个优化问题十分重要，因为这种方法为最优值提供了“上下界限”。

• 松弛就是把一个问题的约束变弱，这样可行域就大了，也能方便求解了。

• 最小化问题中，松弛问题的最优值是下界。最大化问题是上界。

• 松弛技术的精髓就是设计一个容易求解的松弛问题并得到一个优质的“界”。

链接: Everett 1963

链接: Fisher 1973

从拉格朗日乘子法开始

  微积分中，一类问题是求解一个函数的极大值或者极小值。当这个函数受限于另一个函数的时候，问题求解将变得困难。详见同济版《高等数学 下》（高等教育出版社）多元函数的极值及其求法——条件极值 拉格朗日乘数法。

维基百科的一个例子

  参见维基百科。
  求函数$f(x,y)$的极值，且要求满足条件$g(x,y)=c$。
  这里简单描述一下原理和证明过程，详细证明参见引用来源。假设$f(x,y)$的取值为$d_n$，注意$d_n$是随$x$和$y$的值变化的。只有$f(x,y)=d_n$和$g(x,y)=c$相切时，同时沿着有$f(x,y)=d_n$和$g(x,y)=c$的方向前进，在这种情况下，会出现极值。
  由于二者是相切关系，那么二者的梯度满足如下关系：（切线、法线、梯度的关系）

$$\nabla f(x,y) = -\lambda \nabla (g(x,y)-c)$$

于是，有

$$\nabla[f(x,y) + \lambda (g(x,y)-c)]=0\\$$

  这样，如果求出了$\lambda$的值，带到$F(x,y,\lambda)=f(x,y) + \lambda(g(x,y)-c)$中，就能求出无约束条件下的极值和对应的极值点。$F(x,y,\lambda)$和$f(x,y)$在极值点处相等。极值点处，$\nabla F(x,y,\lambda)=0$，且$\frac{\partial F}{\partial \lambda}=g(x,y)-c$，$g(x,y)-c=0$​，所以极值点处有$F(x,y,\lambda)=f(x,y)$。

同济版第7版《高等数学 下》的例子

  第九章p117给出了更详细的证明，这里直接给出结论：要找$z=f(x,y)$在附加条件$\phi (x,y)=0$下的可能极值点，可做拉格朗日函数:

$$L(x,y) = f(x,y) + \lambda \phi(x,y)$$

其中$\lambda$为参数，然后求$L$对$x,y,\lambda$的一阶偏导，并令其为0，将这个三个等式联立。方程组求解得到的解$(x,y)$就是$f(x,y)$可能的极值点。

整数规划拉格朗日松弛

问题构建

  给定一个待求解的整数规划问题（$P$）：

$$\begin{aligned} Z=& \min c x \\ \text { s.t. } & A x=b \\ & D x \leq e \\ & x \geq 0 \text { and integral } \end{aligned} \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\left(\mathrm{P}\right)$$

  我们松弛其整数约束，得到$LP$问题：

$$\begin{aligned} Z=& \min c x \\ \text { s.t. } & A x=b \\ & D x \leq e \\ & x \geq 0 \end{aligned} \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\left(\mathrm{LP}\right)$$

  我们松弛第一个等于约束，得到一个松弛后的拉格朗日问题（$LR_u$）,其中$u=\{u_1,u_2,...u_m\}$是拉格朗日乘子。

$$\begin{aligned} Z_D(u)=& \min c x + u(Ax-b) \\ \text { s.t. } & D x \leq e \\ & x \geq 0 \text { and integral } \end{aligned} \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\left(\mathrm{LR_u}\right)$$

  设$x^*$是$P$问题的最优解，此时，有：

$$Z_D(u)= {\rm{min}}\,cx + u(Ax-b)\le cx^*+u(Ax^*-b) = cx^* = Z$$

  这说明，$Z_D(u)$的值一定小于等于$Z$的值。不等号的来源是松弛，因为$LR_u$比$P$的约束更少，所以$LR_u$的最优解一定小于等于把$x^*$直接带入$LR_u$得到的目标函数值。由于在$P$中，$Ax^* =b$，所以$cx^*+u(Ax^*-b) = cx^* = Z$。
  如果$Ax=b$的约束变成了$Ax\le b$，则需要求$u\ge 0$，如果$Ax=b$的约束变成了$Ax\ge b$，则需要求$u\le 0$。
  总之，不管怎么样，$Z_D(u)\le Z$在一定条件下成立，即$Z_D(u)$小于等于原问题的最优目标函数值。

乘子$u$取值

拉格朗日对偶问题${D}$

   首先，应明确在$u$的特定取值下，$Z_D(u)$可以等于$Z$。此时，这个问题就变成了跟$u$相关的问题。如何给$u$取值，使得$Z_D(u)$尽可能取最大值以接近$Z$的问题，称作拉格朗日对偶问题$D$，即：

$$Z_D = \max _u Z_D(u) \tag{D}$$

该问题的决策变量是$u$，目标函数是最大化$Z_D(u)$的值。也就是说，求解原问题$P$的最小化目标函数值$Z$已经转换成求解拉格朗日对偶问题$D$的目标函数值$Z_D(u)$了。

   那么问题来了，拉格朗日对偶问题的形式很抽象，我们如何具象描述它呢？

拉格朗日对偶重构问题$\bar{D}$

   假设拉格朗日松弛$LR_u$的可行解集$X=\{x|Dx\le e ,x\ge 0 \text{ and integer}\}$是有限集，则我们可以令$X=\{x^t,t=1,...,T\}$。

这样，问题$D$可重构为$\bar{D}$：

$$\begin{aligned} Z_D&=\quad {\rm{max}}\,w\\ \text{s.t.}\quad w &\le cx^t + u(Ax^t-b),t=1,...,T\\ \end{aligned} \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\left(\mathrm{\bar{D}}\right)$$

问：为什么可以这样重构?

*答：令$w=Z_D(u)$，问题$D$想求$Z_D(u)$关于$u$的最大值，所以$\bar{D}$的目标函数是求最大值。$Z_D(u)$是最小化$c x + u(Ax-b)$，那么$Z_D(u)$一定小于等于$LR_u$的任意一个可行解$x^t$带入该表达式的值，即

$$\min c x + u(Ax-b) = Z_D(u) = w \le cx^t + u(Ax^t-b)$$

当$x^t$是$LR_u$问题的最优解时等号成立。*

拉格朗日对偶重构问题的线性规划对偶$\bar{P}$

  这时，再求$\bar{D}$的线性规划对偶$\bar{P}$

$$\begin{aligned} Z_{D}=& \min \sum_{t=1}^{T} \lambda_{t} c x^{t} \\ \text { s.t. } & \sum_{t=1}^{T} \lambda_{t} A x^{t}=b \\ & \sum_{t=1}^{T} \lambda_{t}=1 \\ & \lambda_{t} \geq 0, t=1, \ldots, T \end{aligned} \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\left(\mathrm{\bar{P}}\right)$$

  对偶推导：从$\bar{P}$向$\bar{D}$推导，把$b$分解成凸组合；从$\bar{D}$向$\bar{P}$推导，把$w$看成$1w+0u$，其中$w$和$u$是无约束的决策变量。

  虽然$\bar{P}$和$LP$不是等价问题，即$\bar{P}$并不是原问题$P$的线性松弛版本，但是当$\lambda_t$是整数（0或1）时，$\bar{P}$等价于$P$。理由如下：$x^t$是$LR_u$的可行解，一定满足约束$Dx\le e$。既然满足了这个约束，在所有的可行解中，也肯定存在一个$x^t$满足$Ax^t=b$，那么令对应的$\lambda _t$等于1即可。（满足条件a的所有解中，一定有一个解同时满足a和b，子集关系）

拉格朗日对偶重构问题$\bar{D}$的意义

  问题$\bar{D}$表明，$Z_D(u)$是一系列线性函数的下限值。为了方便理解，假设$x$的变量数只有一个，$T=4$表示对于问题$LR_u$仅有4个可行解。那么，$Z_D(u)$随$u$变化的图像如图所示：

  在这个图中，$x^t$是已知的，是常数，那么得到了四个关于$u$的线性函数。取这些函数在$u$不同取值的最小值，即为函数$Z_D(u)$，如图中加粗线条所示。

  我们发现，$Z_D(u)$是连续的，是凹函数（参照国际定义）。这样找最大值就很简单，比如，我们使用爬山算法，但是我们不能求导，因为最优点处不可导。

  既然不可导，那就用次梯度法。

次梯度法

次梯度概念

   满足如下公式的 $y$ 值为 $Z_D(u)$ 在 $\bar{u}$ 处的次梯度。

$$y(u-\bar{u}) \ge Z_D(u) - Z_D(u), \forall u$$

次梯度性质

• 向量$Ax^t-b$在$x^t$求解 $LR_u$ 对应位置的次梯度。其余的次梯度都是这些“基础”次梯度的凸组合。
• 当且仅当$u^*$和$\lambda^*$是可行的且满足互补松弛定理时，$u^*$是$\bar{D}$的最优解且$\lambda^*$是$\bar{P}$的最优解，这等价于当且仅当$Z_D(u)$ 在 $u^*$ 处的次梯度为0时，$u^*$是$D$的最优解。（说白了就是$Z_D(u)$取到了关于$u$的最大值）

次梯度法更新乘子

   给定一个初始的乘子值 $u^0$，后续乘子第$k$次迭代的值为$u^k$，迭代公式如下：

$$u^{k+1} = u^{k} + t_k(Ax^k-b)$$

其中$x^k$是$(LR_{u^k})$的最优解，$t_k$是一个正数，称为迭代步长。

Goffin (1977)表明：

当$t_k→0$且$\sum_{i=0}^kt_i=0$时，$Z_D(u^k)→Z_D$。

   常用的迭代步长公式为：

$$t_k = \frac{\lambda_k(Z^*-Z_D(u^k))} {||Ax^k-b||^2}$$

其中，$\lambda_k$是一个$(0,2]$之间的标量，$Z^*$是$Z_D$的上界，且使用启发式修改为$P$的可行解。通常，$\lambda_k$的初始值设置为2，当一定迭代次数后，$Z_D(u)$的值仍未增加，$\lambda_k$的值减半。

   注意，这是一个经验性的方法，并不一定能满足最优收敛。

总结

上述的内容只是一个方法论，我们想求解一个问题，还是面临很多的困难的。具体的问题需要具体的分析，包含但不限于松弛哪个约束、获取上界的启发式方法、算法参数的调整等。具体的例子，可参考本人的硕士毕设（在github仓库中）使用拉格朗日松弛求解了一个选址问题。

在读研一的时候第一次接触到子回路消除这个概念，今天特意写一下相关的内容，也算是一个心得与总结，以及一些我对于子回路消除的认知与理解。本文将从一个简单的TSP问题开始讲起，提出模型与消除方法，并使用求解器Gurobi实现各种子回路消除方法。

什么是子回路？

子回路是一个在TSP中和VRP中常见的现象，体现为一辆车走了两个或多个闭环路径。如果不知道VRP和TSP相关的问题与模型，建议补习相关内容。比如下面这张图的TSP问题。正常情况下，一个TSP问题的可行解应该如右图所示，即一辆车遍历所有节点。而左图中，很明显每个点被遍历了，但是竟然出现了两辆车。这显然不符合对于TSP问题的假设。然而在这种情况下（左图），两个回路竟然在数学公式上使用了同一辆车。这就是一个典型的子回路现象。

为什么出现子回路

简单来说，子回路的出现就是我们缺少一部分约束，导致没有完全地刻画问题中车辆的行为。我们知道车辆路径问题（vehicle routing problem, VRP）是旅行商问题（traveling salesman problem, TSP）问题的一个更加困难的版本，与其用一个VRP的例子作为教程，不如使用更为简单的TSP作为上手的开始。因为TSP过于经典，就不再过多赘述。简单来说就是如何以最短的距离不重复地走完地图上所有的城市并且回到出发点，其(不完整的)数学模型如下：

$$\min \sum_{i\in N} \sum_{j\in N} c_{ij}x_{ij} \tag{1}$$

$$\sum_{i\in N} x_{ij} = \sum_{i\in N} x_{ji} = 1, \forall j \in N \tag{2}$$

$$x_{ij} \in \{0,1\}, \forall i \in N, j\in N \tag{3}$$

上述公式使用了常见的符号集合，$N$是节点集合，$c_{ij}$是弧长。公式(2)表示每个点的入度等于出度，即流平衡。
公式(3)是0-1决策变量。

我们观察上面的图的左侧子图，每个点的入度也确实等于出度。也就是说上述的模型是不完整的，我们没有消除子回路的约束。

消除子回路

如上所述，我们需要增加一些约束，这些约束帮助我们消除子回路。这些约束都相当精彩，在领悟其中的原理之后拍手叫绝。

DFJ方法

Dantzig-Fulkerson-Johnson 简称 DFJ 方法是消除子回路的经典方法，公式如下：

$$\sum_{i\in S} \sum_{j \notin S} x_{ij} \ge 1, \forall S \subset N, S \ne \emptyset$$

DFJ约束规定一个节点集合$N$的非空子集$S$，要求连接$S$外面的点和在$S$内部的点的弧的数量大于等于1。换句话说，对于任意一个$N$的子集$S$，一定有一条弧离开$S$。反之，如果存在一个子集$S$，没有一条弧能够离开$S$，那就说明$S$存在子回路。

DFJ约束很简单也很直观，但是问题是约束的数量不是多项式级的，我们不太可能把一个大规模问题的所有的约束枚举出来。

MTZ方法

Miller, Tucker, and Zemlin 简称 MTZ 方法也是消除子回路的经典方法，公式如下：

$$t_i-t_j+1\leq M(1-x_{ij}), \forall i,j\in N,i\neq j$$

$$0 \le t_i \le |N|-1, \forall i\in N$$

MTZ方法引入了一个新的变量，这个变量没有任何物理意义。MTZ公式可以这样理解：
首先，如果两个点$i,j$之间存在一个弧$(i,j)$，那么两个点之间将会产生一个前后关系$i$先被访问，$j$后被访问。这个前后关系我们先假设为时间，也就是说访问$i$的时间一定比访问$j$的时间小。或者我们假设一个计数器，每经过一个点计数器增加一个单位。这个量（计数器、时间）并不存在于定义的TSP问题的物理含义中，可以解释成任意一种能够被人理解的东西（时间、计数器、容量变化…）。现在，我们用额外的决策变量代表每个点被访问的前后顺序，然后让这些值相互关联起来，就能产生前后顺序进而消除子回路。

这个额外的决策变量就是$t_i, \forall i \in N$，那么按照我们上述的计数器假设，如果点$j$在$i$之后被访问（$x_{ij}=1$），那么一定有$t_j \ge t_i + 1$。如果这种关系（点$j$在$i$之后被访问）不存在，那么$t_j \ge t_i + 1$的关系也不存在了，即$t_j$和$t_i$随意取值。我们就得到$t_i-t_j+1\leq M$，其中$M$是一个足够大的数。这样就得到了上述的$t_i-t_j+1\leq M(1-x_{ij}), \forall i,j\in N,i\neq j$的基础原理，$M$最小取值为$|N|$。

如果存在一个子回路，那$t_i$的关系是不可能成立的，因为会无限绕圈，使得$t_i$和$t_j$的关系总是不能被满足。

其他方法

在介绍了上述的两个经典的方法之后，以下是一个综述文章，介绍了各种TSP子回路消除方法。感兴趣自己看，这里就不复现了。

A comparative analysis of several asymmetric traveling salesman problem formulations,
Computers & Operations Research, 2009

Gurobi 实现MTZ和DFJ子回路消除

上述介绍中已经提到DFJ方法的约束个数是有限的，但是指数级的。我们不太可能用求解器把所有子回路的情况都考虑进去。首先声明这是一个简单的代码，用了20分钟写的简单例子，没有面向对象。

那么 talk is cheap, show me your code。

1
2
3
4
5

import gurobipy as gp
import math
import random
import re
from itertools import combinations

extract_numbers()从[a,b]这样的方括号中提取a和b这两个数字，并返回一个list，用于从变量名中提取索引。

1
2
3
4
5
6
7

def extract_numbers(s):  # 使用正则表达式匹配方括号中的两个数字
    match = re.search(r"\[(\d+),(\d+)\]", s)
    if match:
        # 提取匹配到的数字并转换为整数
        return [int(match.group(1)), int(match.group(2))]
    else:
        return None

get_tour()函数从一个字典edges中获得一个回路。字典edges的一个键值对是一条弧，键是起点，值是终点。
例如edges={1:2, 3:4, 2:3, 4:1}，则得到tour=[1,2,3,4]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

def get_tour(edges: dict):
    tour = []  # 一个回路
    while True:
        if len(tour) == 0:  # 空的回路
            if 0 in edges:  # 包含起点，则以起点开始
                tour.append(0)
                tour.append(edges[0])
                del edges[0]
            else:  # 不包含起点，则以第一个点开始
                tmp = list(edges.keys())
                tour.append(tmp[0])
                tour.append(edges[tmp[0]])
                del edges[tmp[0]]
        else:
            tmp = edges.get(tour[-1])
            if tmp == None:
                break  # 产生了一个回路
            else:
                tour.append(tmp)
                del edges[tour[-2]]
    return edges, tour[:-1]

mycallback函数为DFJ的约束添加过程，由于这样的约束数量很多无法一次添加，那么使用callback函数进行添加。
在MIPSOL处（mip solution）如果发现了一个带子回路的解，则添加针对这个回路的DFJ约束。注意，我们假设TSP的起点一定不在子回路里面，也就是只有不带起点的回路才是子回路。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

def mycallback(model, where):
    if where == gp.GRB.Callback.MIPSOL:
        # 解析获得的解
        var_val = model.cbGetSolution(model._var)

        edges = {}  # TSP 决定走的边
        for i in range(len(var_val)):
            if var_val[i] > 0.5:
                tmp = extract_numbers(model._var[i].VarName)
                edges.update({tmp[0]: tmp[1]})

        # 在edges搜索一个子回路，要求起点一定不在子回路里面
        flag_subtour = False
        edges, tour = get_tour(edges)
        if len(tour) < model._node_num:  # 一定存在子回路
            flag_subtour = True

        # 针对这个子回路添加 DFJ约束
        if flag_subtour:
            edges, tour = get_tour(edges)  # 可能有多个subtour，获得一个子回路即可
            assert len(tour) < model._node_num
            # 加约束
            pairs = [(i, j) for i in tour for j in tour if i != j]
            lexp = 0
            for p in pairs:
                lexp += model.getVarByName("x[" + str(p[0]) + "," + str(p[1]) + "]")
            model.cbLazy(lexp <= len(tour) - 1)

使用DFJ方法的模型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

def solve_tsp_dfj(nodes, distances):
    # TSP 求解
    model = gp.Model()
    x = model.addVars(
        distances.keys(), obj=distances, vtype=gp.GRB.BINARY, name="x"
    )  # 变量

    model.addConstrs(gp.quicksum(x[i, j] for j in nodes if i != j) == 1 for i in nodes)
    model.addConstrs(gp.quicksum(x[j, i] for j in nodes if i != j) == 1 for i in nodes)

    model.update()
    model._var = model.getVars()
    model._node_num = len(nodes)

    # 使用LazyConstraints声明
    model.Params.LazyConstraints = 1
    model.optimize(mycallback)

    if model.Status == gp.GRB.OPTIMAL:
        edges = {}  # 被选中的边
        for i in range(len(model._var)):
            if model._var[i].X > 0.5:
                tmp = extract_numbers(model._var[i].VarName)
                edges.update({tmp[0]: tmp[1]})
        edges, tour = get_tour(edges)
        print(tour)
        print(f"路径中点的个数：{len(tour)}")
        print(f"路径长度：{model.ObjVal}")

使用MTZ方法的模型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

def solve_tsp_mtz(nodes, distances):
    # TSP 求解
    model = gp.Model()
    x = model.addVars(
        distances.keys(), obj=distances, vtype=gp.GRB.BINARY, name="x"
    )  # 变量
    t = model.addVars((i for i in nodes), vtype=gp.GRB.CONTINUOUS, name='t')

    model.addConstrs(gp.quicksum(x[i, j] for j in nodes if i != j) == 1 for i in nodes)
    model.addConstrs(gp.quicksum(x[j, i] for j in nodes if i != j) == 1 for i in nodes)
    # model.addConstr(t[0] == 0)
    node_without_starts = copy.deepcopy(nodes)
    node_without_starts.remove(0)
    model.addConstrs(
        t[i] - t[j] + 1 <= len(nodes) * (1 - x[(i, j)])
        for i in node_without_starts
        for j in node_without_starts
        if i != j
    )

    model.update()
    model._node_num = len(nodes)

    model.optimize()

    if model.Status == gp.GRB.OPTIMAL:
        edges = {}  # 被选中的边
        for i in nodes:
            for j in nodes:
                if i != j:
                    if model.getVarByName("x[" + str(i) + "," + str(j) + "]").X > 0.5:
                        edges.update({i:j})
        edges, tour = get_tour(edges)
        print(tour)
        print(f"路径中点的个数：{len(tour)}")
        print(f"路径长度：{model.ObjVal}")

主程序生成一个50个点的TSP问题，同一个问题使用两种方法求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

if __name__ == "__main__":
    npoints = int(50)
    seed = int(41372890)

    # 创建一个随机的TSP算例
    random.seed(seed)
    nodes = list(range(npoints))
    points = [(random.randint(0, 100), random.randint(0, 100)) for i in nodes]

    # 欧式距离
    distances = {
        (i, j): math.sqrt(sum((points[i][k] - points[j][k]) ** 2 for k in range(2)))
        for i, j in combinations(nodes, 2)
    }

    for i, j in combinations(nodes, 2):
        distances.update({(j, i): distances[(i, j)]})

    # 算法求解
    solve_tsp_dfj(nodes, distances)
    solve_tsp_mtz(nodes, distances)

LaTex是科研写作中常见的排版工具。爱思唯尔期刊提供了Latex模板，使用该模板可简化在投稿过程中关于稿件的排版过程，在编译过后就能得到期刊认可的排版格式。

不少期刊都已经采用了“Your paper your way”的投稿方式，即根据作者的喜好的排版方式提交稿件，在接收后排版成期刊的要求的格式即可，但也提供了Latex模板。
关于爱思唯尔期刊的Latex模板，详见https://www.elsevier.com/researcher/author/policies-and-guidelines/latex-instructions

尽管内容大于形式，红楼梦手抄一万遍也是经典，我的博客打印出来也只是我的博客，
但我们使用Latex模板将给审稿人表达一种专业且认真的态度，也可以简化写作、排版、公式输入及编号、交叉引用的流程。

请注意：阅读本文需要一定Latex使用经验，且本文只针对爱思唯尔期刊Latex模板elsarticle有效。

1. 使用的宏包介绍

1
2
3

% \usepackage[numbers]{natbib}
% \usepackage[authoryear,longnamesfirst]{natbib}
\usepackage[authoryear]{natbib}

该宏包是elsarticle自带的引用格式的宏包，一般我选择使用第三个[authoryear]参数。

1

\usepackage{lineno}

lineno是行号宏包，投稿时如需加行号则使用此宏包。
然而，该宏包对于模板的双列布局可用，但是支持性一般。
此外不推荐使用双列模板，除非没有长公式或者长图、长表等等，
elsarticle的双列模板虽然好看，但是给排版（尤其是跨列图、表、公式）带来诸多困难。

1

\usepackage{threeparttable} 

threeparttable可以实现表格以及表格下方的注释，十分好用。

1

\usepackage[ruled,linesnumbered]{algorithm2e} 

algorithm2e是算法伪代码的常用宏包。

1

\usepackage{subcaption}

subcaption 可以实现子图

1

\usepackage[nameinlink,capitalize]{cleveref} 

cleveref 实现交叉引用带label名字，比如Section 1, 而不是使用\ref仅引用一个数字。
该宏包最好放在所有宏包命令的最后

1

\usepackage{pdflscape} % 单页横置

pdflscape是某页横置的包，支持pdf旋转，比landscape更好一些。
landscape编译出来后，pdf内容是横置的，但是页面仍是竖置，而pdflscape的页面也是横置的。

1

\usepackage{midpage} % 页面垂直居中内容

midpage配合pdflscape使用，可以使用横置的内容位于页面的垂直方向的中心（垂直居中）。
再配合横向居中\centering使用，就是页面的正中心。

1

\usepackage{afterpage} % 减少横向排版某页前后的空白页

afterpage配合pdflscape使用，可避免pdflscape使用前后文章出现大面积空白（因为pdflscape在哪里使用就在哪里分页）。

2. 实践例子

Minimal Working Example (MWE) 是Latex是一个精简到最小长度的.tex文件。是一个可以运行的，最简短的tex文件。
以下例子均基于MWE或者elsarticle的cas-sc-sample.tex文件进行展示。
文本填充使用了lipsum宏包生成随机文本

行号 lineno

展示行号使用了lineno宏包，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

\documentclass[a4paper,fleqn]{cas-sc}

\usepackage{lipsum}
\usepackage{lineno}

\begin{document}
\let\WriteBookmarks\relax
\def\floatpagepagefraction{1}
\def\textpagefraction{.001}

\title [mode = title]{This is a title}                      
\author[1]{Name}[]

\begin{abstract}
  Null.
\end{abstract}

\begin{keywords}
  Null
\end{keywords}

\maketitle

\linenumbers
\section{Introduction}
\lipsum[1]

\end{document}

\linenumbers命令放在节标题前面就可以生成行号了，结果如下：

表格注释threeparttable

在表格展示结果的过程中总会有需要在表格下方注释的情况，使用threeparttable宏包可满足该需求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

\documentclass[a4paper,fleqn]{cas-sc}

\usepackage{lipsum}
\usepackage{threeparttable}

\begin{document}
\let\WriteBookmarks\relax
\def\floatpagepagefraction{1}
\def\textpagefraction{.001}

\title [mode = title]{This is a title}                      
\author[1]{Name}[]

\begin{abstract}
  Null.
\end{abstract}

\begin{keywords}
  Null
\end{keywords}

\maketitle

\section{Introduction}
\lipsum[1]

\begin{table}[width=0.4\textwidth, pos=thb]
\scriptsize
\tabcolsep=2.5pt
\renewcommand\arraystretch{1.5}
\centering
\caption{Table notes}
\label{tb:review}%
\begin{threeparttable}
  \begin{tabular*}{\tblwidth}{lcclccl}
    \toprule
    Ref. & \multicolumn{2}{c}{Omnichannel concept} & \multicolumn{2}{l}{Customer} & \multicolumn{1}{l}{Store}  \\
    \midrule
    O\tnote{a} & F  & S & M  & P & S  & L,C   \\
    C & R  & S & M\tnote{*}  & C & H  & L,R   \\
    O & R  & S & M  & C & H  & L,R\tnote{$\dagger$} \\
    \bottomrule
  \end{tabular*}%

  \begin{tablenotes}
    \scriptsize
    \item[a] table note a 
    \item[*] asterisk
    \item[$\dagger$] dagger
  \end{tablenotes}
\end{threeparttable}
\end{table}

\end{document}

这会生成一个带有注释的表格。

伪代码

请参考Overleaf的伪代码包，写的非常详细。
https://www.overleaf.com/learn/latex/Algorithms

子图 subcaption

使用子图，只需要引用subcaption宏包即可，子图换行使用\\即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

\documentclass[a4paper,fleqn]{cas-sc}

\usepackage{lipsum}
\usepackage{subcaption}

\begin{document}
\let\WriteBookmarks\relax
\def\floatpagepagefraction{1}
\def\textpagefraction{.001}

\title [mode = title]{This is a title}                      
\author[1]{Name}[]

\begin{abstract}
  Null.
\end{abstract}

\begin{keywords}
  Null
\end{keywords}

\maketitle

\section{Introduction}
\lipsum[1]

\begin{figure}[pos = htb]
  \centering
  \begin{subfigure}{0.3\textwidth}
    \includegraphics[width=\textwidth]{figs/cas-grabs.pdf}
    \caption{subfigure 1}
    \label{subfig:routes}
  \end{subfigure}
  \hfill
  \begin{subfigure}{0.3\textwidth}
    \includegraphics[width=\textwidth]{figs/cas-grabs.pdf}
    \caption{subfigure 2}
    \label{subfig:cycle}
  \end{subfigure}
  \hfill
  \begin{subfigure}{0.3\textwidth}
    \includegraphics[width=\textwidth]{figs/cas-grabs.pdf}
    \caption{subfigure 3}
    \label{subfig:aggregate}
  \end{subfigure}
  \\
  \begin{subfigure}{0.3\textwidth}
    \includegraphics[width=\textwidth]{figs/cas-grabs.pdf}
    \caption{subfigure 4}
    \label{subfig:assign}
  \end{subfigure}
  \hspace{0.15\textwidth}
  \begin{subfigure}{0.3\textwidth}
    \includegraphics[width=\textwidth]{figs/cas-grabs.pdf}
    \caption{subfigure 5}
    \label{subfig:newroute}
  \end{subfigure}
  \caption{\label{fig:aggr} Subfigures}
\end{figure}

\end{document}

这会生成一个两行子图，第一行有3张，第二行有2张。

交叉引用 cleveref

交叉引用是Latex一个重要的功能，自带的\ref功能只能引用数字，生成出来的效果并不好看，比如“Section 1.1 ”, 而不是期刊常见的“Section 1.1 ”。使用cleveref宏包解决这个问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

\documentclass[a4paper,fleqn]{cas-sc}

\usepackage{lipsum}
\usepackage{subcaption}
\usepackage[nameinlink,capitalize]{cleveref}


\begin{document}
\let\WriteBookmarks\relax
\def\floatpagepagefraction{1}
\def\textpagefraction{.001}

\title [mode = title]{This is a title}                      
\author[1]{Name}[]

\begin{abstract}
  Null.
\end{abstract}

\begin{keywords}
  Null
\end{keywords}

\maketitle

\section{Introduction}
\Cref{subfig:assign} is in \Cref{fig:aggr}. 

\begin{figure}[pos = htb]
  \centering
  \begin{subfigure}{0.3\textwidth}
    \includegraphics[width=\textwidth]{figs/cas-grabs.pdf}
    \caption{subfigure 1}
    \label{subfig:routes}
  \end{subfigure}
  \hfill
  \begin{subfigure}{0.3\textwidth}
    \includegraphics[width=\textwidth]{figs/cas-grabs.pdf}
    \caption{subfigure 2}
    \label{subfig:cycle}
  \end{subfigure}
  \hfill
  \begin{subfigure}{0.3\textwidth}
    \includegraphics[width=\textwidth]{figs/cas-grabs.pdf}
    \caption{subfigure 3}
    \label{subfig:aggregate}
  \end{subfigure}
  \\
  \begin{subfigure}{0.3\textwidth}
    \includegraphics[width=\textwidth]{figs/cas-grabs.pdf}
    \caption{subfigure 4}
    \label{subfig:assign}
  \end{subfigure}
  \hspace{0.15\textwidth}
  \begin{subfigure}{0.3\textwidth}
    \includegraphics[width=\textwidth]{figs/cas-grabs.pdf}
    \caption{subfigure 5}
    \label{subfig:newroute}
  \end{subfigure}
  \caption{\label{fig:aggr} Subfigures}
\end{figure}

\end{document}

这会生成一个带引用类型的交叉引用格式。

横置某页 pdflscape midpage afterpage

横置一个pdf页码可以解决某个表格或者图太长的问题，使用pdflscape可以将某一页横置，以放下这些图表。
基础使用方法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

\documentclass[a4paper,fleqn]{cas-sc}

\usepackage{lipsum}
\usepackage{subcaption}
\usepackage{pdflscape} 
\usepackage[nameinlink,capitalize]{cleveref}

\begin{document}
\let\WriteBookmarks\relax
\def\floatpagepagefraction{1}
\def\textpagefraction{.001}

\title [mode = title]{This is a title}                      
\author[1]{Name}[]

\begin{abstract}
  Null.
\end{abstract}

\begin{keywords}
  Null
\end{keywords}

\maketitle

\section{Introduction}
\Cref{subfig:assign} is in \Cref{fig:aggr}. 

\begin{landscape}
  \begin{figure}[pos = htb]
    \centering
    \begin{subfigure}{0.3\textwidth}
      \includegraphics[width=\textwidth]{figs/cas-grabs.pdf}
      \caption{subfigure 1}
      \label{subfig:routes}
    \end{subfigure}
    \hfill
    \begin{subfigure}{0.3\textwidth}
      \includegraphics[width=\textwidth]{figs/cas-grabs.pdf}
      \caption{subfigure 2}
      \label{subfig:cycle}
    \end{subfigure}
    \hfill
    \begin{subfigure}{0.3\textwidth}
      \includegraphics[width=\textwidth]{figs/cas-grabs.pdf}
      \caption{subfigure 3}
      \label{subfig:aggregate}
    \end{subfigure}
    \\
    \begin{subfigure}{0.3\textwidth}
      \includegraphics[width=\textwidth]{figs/cas-grabs.pdf}
      \caption{subfigure 4}
      \label{subfig:assign}
    \end{subfigure}
    \hspace{0.15\textwidth}
    \begin{subfigure}{0.3\textwidth}
      \includegraphics[width=\textwidth]{figs/cas-grabs.pdf}
      \caption{subfigure 5}
      \label{subfig:newroute}
    \end{subfigure}
    \caption{\label{fig:aggr} Subfigures}
  \end{figure}
\end{landscape}
\end{document}

这会得到一个横置的页面,注意到这个页面是横置的，所有的内容在页面的上方，下一步是把这些图片垂直居中。

只需要在landscape和figure环境之间套一层midpage环境即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

\documentclass[a4paper,fleqn]{cas-sc}

\usepackage{lipsum}
\usepackage{subcaption}
\usepackage{pdflscape} 
\usepackage{midpage}

\begin{document}

\begin{landscape}
  \begin{midpage}
    \begin{figure}[pos = htb]
      ... 图表代码
    \end{figure}
  \end{midpage}
\end{landscape}

\end{document}

得到居中的插图：

但是，横置页前后的文字会因为横置页突然打断，出现大面积空白。这时还需要afterpage宏包，使得横置页平滑插入到文字中，用\afterpage{}命令把landscape环境包裹起来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

\documentclass[a4paper,fleqn]{cas-sc}

\usepackage{lipsum}
\usepackage{subcaption}
\usepackage{pdflscape} 
\usepackage{midpage}

\begin{document}
\afterpage{
  \begin{landscape}
    \begin{midpage}
      \begin{figure}[pos = htb]
        ... 图表代码
      \end{figure}
    \end{midpage}
  \end{landscape}
}
\end{document}

生成的效果如图，可见横置页丝滑插入段落中，没有产生大面积空白

禁止分页

使用\nopagebreak表示禁止在此处断页。

此外，还可以使用

1
2
3
4
5
6
7
8
9
10
11

\usepackage{parskip}
\AddToHook{env/samepage/begin}{%
\AddToHook{para/before}{\nopagebreak}%
\AddToHook{para/after}{\nopagebreak}%
}

\begin{samepage}
在一页的第一段

在一页的第二段
\end{samepage}

另两个段落出现在同一页。

公式间距微调

参考这篇文章https://tex.stackexchange.com/questions/74353/what-commands-are-there-for-horizontal-spacing
下面的源代码将在字母ab之间产生不同大小的横向间距。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

\documentclass{article}

\usepackage[margin=1in]{geometry}% Just for this example
\setlength{\parindent}{0pt}% Just for this example

\begin{document}

There are a number of horizontal spacing macros for LaTeX:

\begin{tabular}{lp{5cm}}
  \verb|a\,b|                     & a\,b \quad $a\, b$ \\
  \verb|a\thinspace b|            & a\thinspace b \quad $a\thinspace b$ \\
  \verb|a\!b|                     & a\!b \quad $a\!b$ \\
  \verb|a\negthinspace b|         & a\negthinspace b \quad $a\negthinspace b$ \\
  \verb|a\:b|                     & a\:b \quad $a\:b$ \\
  \verb|a\>b|                     & a\>b \quad $a\>b$ \\
  \verb|a\medspace b|             & a\medspace b \quad $a\medspace b$ \\
  \verb|a\negmedspace b|          & a\negmedspace b \quad $a\negmedspace b$ \\
  \verb|a\;b|                     & a\;b \quad $a\;b$ \\
  \verb|a\thickspace b|           & a\thickspace b \quad $a\thickspace b$ \\
  \verb|a\negthickspace b|        & a\negthickspace b \quad $a\negthickspace b$ \\
  \verb|$a\mkern\thinmuskip b$|   & $a\mkern\thinmuskip b$ (similar to \verb|\,|) \\
  \verb|$a\mkern-\thinmuskip b$|  & $a\mkern-\thinmuskip b$ (similar to \verb|\!|) \\
  \verb|$a\mkern\medmuskip b$|    & $a\mkern\medmuskip b$ (similar to \verb|\:| or \verb|\>|) \\
  \verb|$a\mkern-\medmuskip b$|   & $a\mkern-\medmuskip b$ (similar to \verb|\negmedspace|) \\
  \verb|$a\mkern\thickmuskip b$|  & $a\mkern\thickmuskip b$ (similar to \verb|\;|) \\
  \verb|$a\mkern-\thickmuskip b$| & $a\mkern-\thickmuskip b$ (similar to \verb|\negthickspace|) \\
  \verb|a\enspace b|              & a\enspace b \\
  \verb|$a\enspace b$|            & $a\enspace b$ \\
  \verb|a\quad b|                 & a\quad b \\
  \verb|$a\quad b$|               & $a\quad b$ \\
  \verb|a\qquad b|                & a\qquad b \\
  \verb|$a\qquad b$|              & $a\qquad b$ \\
  \verb|a\hskip 1em b|            & a\hskip 1em b \\
  \verb|$a\hskip 1em b$|          & $a\hskip 1em b$ \\
  \verb|a\kern 1pc b|             & a\kern 1pc b \\
  \verb|$a\kern 1pc b$|           & $a\kern 1pc b$ \\
  \verb|$a\mkern 17mu b$|         & $a\mkern 17mu b$ \\
  \verb|a\hspace{35pt}b|          & a\hspace{35pt}b \\
  \verb|$a\hspace{35pt}b$|        & $a\hspace{35pt}b$ \\
  \verb|axyzb|                    & axyzb \\
  \verb|a\hphantom{xyz}b|         & a\hphantom{xyz}b (or just \verb|\phantom|) \\
  \verb|$axyzb$|                  & $axyzb$ \\
  \verb|$a\hphantom{xyz}b$|       & $a\hphantom{xyz}b$ (or just \verb|\phantom|) \\
  \verb|a b|                      & a b \\
  \verb|$a b$|                    & $a b$ \\
  \verb|a\space b|                & a\space b \\
  \verb|$a\space b$|              & $a\space b$ \\
  \verb|a\ b|                     & a\ b \\
  \verb|$a\ b$|                   & $a\ b$ \\
  \verb|a{ }b|                    & a{ }b \\
  \verb|$a{ }b$|                  & $a{ }b$ \\
  \verb|a~b|                      & a~b \\
  \verb|$a~b$|                    & $a~b$ \\
  \verb|a\hfill b|                & a\hfill b \\
  \verb|$a\hfill b$|              & $a\hfill b$
\end{tabular}

\end{document}

其中，可以在公式环境内部调整间距。

1
2
3
4
5
6

\begin{equation}
\thinmuskip=3mu
\medmuskip=4mu plus 2mu minus 4mu
\thickmuskip=5mu plus 5mu
a + b = c
\end{equation}

最后，align环境调整行距，只需在\\之后加[行距]即可。

1
2
3
4

\begin{align*}
    f(x)=x^{2}-2x+1\\[10pt]
    f(x)=(x-1)^{2}
\end{align*} 

前言：在运筹论文中，总会出现一些Proposition, Theorem, 等类似的模型相关术语，
理解这些术语的内涵有助于揣测作者写作的着重点，更有助于理解文章的内容。

术语、含义

个人理解

上述的术语在应用类型的运筹文章中，比较常见的有Definition、Theorem、Proposition、Lemma、Proof。
通常在模型或问题提出后，为了增加文章的理论深度，提出一些关于模型的有意思的、略带深度的性质，并提供证明Proof。
个人觉得Theorem是一个严肃的内容，其定义是“已经被证明的正确的内容“，但是在文章中证明出来了，
就算的上是”已经被证明“了。

Lemma、Proposition、Theorem的边界并不是清晰的，所以怎么用都行。
但是重要性的排序个人认为是：Theorem > Proposition > Lemma。

Remark一般在证明最后，强调一下和其他人的不同，或者强调有意义的事情。

记录在学校的一次matlab课上的技术分享。

前言：本次分享的主要内容是介绍一些我个人Matlab开发常用的经验总结，
目的是让大家了解到matlab的优缺点、独特性、技巧，以及用什么方法解决什么问题。
Matlab是一个复杂的工具，并不是我凭借一己之力可以完全说清楚的。
大部分各种理工科离不开这一工具，而各个学科之间隔行如隔山，
我只是把自己经常使用的经验进行总结，和各位共同分享。

假设：今天不会涉及编程思想（函数式、面向对象等），主要是向大家分享如何用好这一工具。
假设各位已经掌握matlab的基本语法，并且自己也会写一些代码了。

代码优化

同样是跑代码，为什么我要等很久？

我们不得不承认，Matlab这种解释型语言比编译型语言要慢（代码在运行时会被一行一行地解释执行），
这并不代表Matlab代码不能变得高效。

预分配内存

在进行循环语句时，应当先声明变量所需空间的大小，再进行循环，避免每次循环向数组中增加数字。

不推荐写法

1
2
3
4
5
6

tic
for i = 1:1000
	mat(i,i) = i;
end
toc
% 历时 0.115061 秒。

推荐写法

1
2
3
4
5
6
7

tic
mat_2 = zeros(1000); % 先把数组的大小声明，在内存中开辟一块空间
for i = 1:1000
	mat_2(i,i) = i;
end
toc
% 历时 0.005585 秒。

为什么出现这样的差异？

反复调整数组的大小将导致花费额外的时间找到更大的、连续的内存空间。

所有类型的变量都需要这样做吗？

不一定，cell类型则不需要，但是放在cell中的数据类型可能需要。
cell数组内存不连续，但是每个cell要求连续内存。
（部分情况下cell在编译成mex文件时，同样需要初始化内存）

参考链接：

https://ww2.mathworks.cn/help/matlab/matlab_prog/preallocating-arrays.html

https://ww2.mathworks.cn/help/matlab/matlab_prog/techniques-for-improving-performance.html

https://ww2.mathworks.cn/help/matlab/matlab_prog/avoid-unnecessary-copies-of-data.html

https://ww2.mathworks.cn/help/matlab/matlab_prog/strategies-for-efficient-use-of-memory.html

向量化

官方定义：

修正基于循环且面向标量的代码以使用 MATLAB 矩阵和向量运算的过程称为向量化。

简单来说，就是替代for循环做一些简单操作，以提高运行速度、可读性、正确性。即，算法流程控制for循环，简单操作向量化。
向量化是matlab的一个重要特点，这在其他语言很少出现
向量化的语句通常有底层的支持，利用到了CPU指令集进行优化，因此速度较快，
而for循环遍历慢的原因是matlab为解释性语言需要一行一行执行。

求1至10000的每个数的正弦的和

循环写法：

1
2
3
4
5
6
7
8
9

tic
all_sum = 0;
for i = 1:1e4
	all_sum = all_sum + sin(i);
end
disp(['all_sum: ', num2str(all_sum)])
toc
% all_sum: 1.6339
% 历时 0.038938 秒。

向量化写法：

1
2
3
4
5
6

tic
all_sum = sum(sin(1:1e4));
disp(['all_sum: ', num2str(all_sum)])
toc
% all_sum: 1.6339
% 历时 0.008211 秒。

为什么all_sum这么小？

隐式扩展，求每个人每科成绩与平均值的差距

1
2
3
4
5
6
7
8
9

% 每个人有三门课，
%    数 语  外
A = [97 89 84; 
     95 82 92; 
     64 80 99;
     76 77 67;
     88 59 74; 
     78 66 87; 
     55 93 85];		% 每一列是一个人

循环写法

1
2
3
4
5

mA = mean(A);			% 求每列的平均值
B = zeros(size(A));		% 记录每个人每门课的差距
for n = 1:size(A,2)		% 对每一列进行操作
    B(:,n) = A(:,n) - mA(n);
end

向量化写法

1

devA = A - mean(A)

注意，在向量化写法中，mean(A)的结果是1x3大小的。即使 A 是一个 7×3 矩阵，mean(A) 是一个 1×3 向量，MATLAB 也会隐式扩展该向量，就好像其大小与矩阵相同一样，并且该运算将作为正常的按元素减法运算来执行。（广播操作）

逻辑索引，线性索引，下标索引

介绍三种索引方式的区别

一个矩阵A ，寻找这个矩阵中大于500的数字的行列数

循环方法（单个循环，获得线性索引，双层循环，获得行列数）

1
2
3
4
5
6
7
8
9
10
11
12
13