OR-Writing Seminar

运筹优化论文写作

Li Y. — IJOC

Novel Formulations and Logic-Based Benders Decomposition for the Integrated Parallel Machine Scheduling and Location Problem

摘要

内容

• 离散并行机器调度和位置问题，包括将多台机器定位到一组候选位置，将来自不同位置的作业分配给找到的机器，并对分配的作业进行排序。目标是最小化所有作业的最大完成时间，即完工时间。

方法

• 提出了三个新的混合整数线性模型，其性能优于最先进的公式。针对实际规模的实例开发了一种新的基于逻辑的 Benders 分解算法，该算法将问题分为确定机器位置和机器作业分配的主问题和对每台机器上的作业进行排序的子问题。主问题是通过在单个搜索树上运行的分支切割过程来解决的。一旦找到主问题的现有解决方案，就可以解决子问题以生成动态添加到主问题的Cuts。首先提出通用的切割，并通过一些强化技术对其改进。根据子问题的最优性条件开发了两种最优性切割，并通过强化技术进行了改进。

选题与写作

选题

• 现实场景分析
  • 部署：Location
  • 分配：Assignment
  • 顺序：Scheduling
  • 目标：makespan
• 联系文献
  • 分析问题特点
    • 工件分布在不同位置或区域
    • 机器位置分散且待选择
  • 定位理论问题：选址调度问题（Scheduling and Location Problem）
  • 实际问题与论文问题的联系，日常需要大量的文献积累
• 调研文献
  • 识别出关键文献，经典的，最新的，需要精读
  • 文献综述的目的是掌握问题的研究进展，明确拟研究问题的研究意义
• 重点文献梳理
  • 关键文献要深入读，反复读，明确其研究问题、贡献、模型、算法细节
  • 重点关注其提出的未来研究方向
• 识别贡献
  • 对当前问题，文献尚未开展研究
  • 对当前问题，文献已有研究
  • 对同类或近似问题的研究不足以支持当前问题
  • 新问题（文献尚未开展研究）
  • 新模型（建模）
  • 新方法（算法设计）
  • 文献调研工作要充分，从相关文献开始，顺藤摸瓜，找到针对该问题的研究脉络。如：找到了重要文献A，要看A引用了哪些相关文献，以及哪些文献引用了A
  • 根据个人基础，选择合适的研究问题
    • 对于数学、计算机基础较好的同学，可尝试攻克经典问题
    • 两方面相对薄弱的同学，建议从问题创新角度出发，研究新问题然后遵循基本的新问题、新模型、新方法、新结果的研究思路
    • 生产-路径问题(Production-routing problem) (博士论文题目)
• 初始题目
  • 导师给定: 食品供应链
    • 半年阅读文献，从综述开始看，然后看综述中比较前沿的研究问题，然后关注到供应商管理库存vender managed inventory（VMI）这样一种模式，以及这种模式背后的库存路径问题（Inventory routing problem)
    • 开始阅读IRP相关文献，并注意到了IRP问题并未涉及生产环节，每阶段可用的商品量是给定的参数，阅读到考虑生产的PRP文献，就是生产批量问题和IRP问题的结合
    • PRP考虑食品特性的研究较少，如食品的易腐性，新鲜度等
  • 最终确定题目: 考虑食品质量的生产路径问题
  • 有想法后可多向老师汇报讨论，老师会根据经验进行判断，该主题是否值得做，未来做的题目的贡献点该如何体现

写作与投稿

写作

• 基本原则

  • 写作以简洁、逻辑通顺为主
  • 句子之间、段落之间的衔接
  • 不同部分之间的联系，注意前后呼应
  • 完整、系统的将研究动机、研究现状、研究内容、研究结果、研究结论展示出来

• Introduction

  • 五段式方法
    • 第一段：大背景，讲清楚研究问题在产业、行业、民生等方面的重要性
    • 第二段：新模式、新技术等带来的新特点，以及运营管理中面临的新问题
    • 第三段：新问题的研究进展，复杂特性、难点，亟待解决，现有文献无法有效覆盖
    • 第四段：本文要研究的内容，拟解决的问题，拟采用的方法，预计得到的结论
    • 第五段：整篇文章的安排

• Literature review

  • 引出与本文研究问题最相关的研究问题有哪些，比如本文研究A,相关问题为BCD讲清楚BCD的研究进展，以及与A的关系
  • A是如何拓展BCD的，BCD的研究缺乏对A的哪方面的考虑
  • BCD的研究结果，如何无法直接适用到A，因为A的哪方面的特性
  • 最后，总结梳理A的新颖之处，如何拓展BCD，A的研究结果如何更好的解决BCD
  • 文献的展示方式有很多种，比如按照时间、按照主题、按照应用的方法等，对于一般OR论文，建议按照研究同一问题的方法划分，比如精确算法，启发式方法(不同类型的启发式)，并注意梳理不同文献之间的逻辑关系，比如B针对X问题提出了一个什么方法，获得了X结果；C在B的基础上，进一步拓展了xxx，提出了xxx方法，并将结果改进xxx；D采用了与B和C不同的方法，并获得了xxx结果。

• Problem description and formulation

  • 问题的设定，参数，以及限制，要描述清楚，假设要交代清楚
  • 模型的参数尽可能用a,b,c,d,e,f,g，下标用h,i,j,k，变量用x,y,z,u,v，集合用Q,K,J,V,N等
  • 尽量不用多个字母表示参数和变量
  • 模型的约束尽可能按照一定逻辑展示，比如分配的和路径相关的，一次性展示完
  • 模型的解释要一对一，详细解释
  • 模型之后，要给出问题的复杂度(部分需要证明)，且可做适当分析，提出一些有效不等式以加强模型

• Solution method

  • 问题的分析，结构特性，属于哪一类问题
  • 该类问题的常用解决方法，最有效解决方法
  • 不同方法对这类问题的适用性，说明选用方法的动机和原因
  • 总-分的方式，展示提出的方法，注意各部分之间的连接
  • 一定要严格按照程序实现的逻辑写，避免出现和程序不一致的情况

• Computational experiments

  • 先交代实验的目的，环境，配置，参数设置等
  • 数据的生成 （要有依据）和选取，算例的描述
  • 结果的呈现（要有逻辑，能看出趋势），按照一定的规则分开展示
  • 灵敏度分析，要分析参数对问题的影响、对算法的影响
  • 算法性能分析，对方法的设计是否有效，所声明的贡献是否真的是贡献
  • 结果是基础，好的结果，写起来相对容易但往往结果不一定全好，比如我们质量上差不多，但时间快，这时候我们要强调求解效率高；解质量高，但时间长，这时候我们要强调对于这类问题，我们算法所用时间是可接受的，且在可接受时间内大幅度改进了当前解。

• Conclusion

  • 管理启示(Managerial implications)
  • 总结回顾本研究的问题、思路、方法、结果、结论
  • 重点讲结论，以及结论背后蕴含的管理意义
  • 指出文章研究的局限，以及未来可能研究的方向
  • 对未来研究，最好能给出一个脉络，比如从算法方面，可能可以从哪些方面进行突破
  • 全文几个地方要呼应，Introduction里面提出的问题，在文献综述部分，要强调现有研究无法支撑，文献综述识别的问题，在Introduction的研究内容中要明确指出。结论部分是文章的末尾，要明确说明本文是如何解决了Introduction中提出的问题的，如何弥补了文献综述中识别处的空白。

投稿

• 期刊选择
  • 首先自己评估论文的贡献，符合哪类期刊
  • 看引用的文献都发表在什么期刊
  • 选择同行认可度高的期刊
  • 其他因素: 学校列表、期刊投稿周期等
  • 语言的润色、查重
  • 不同期刊的写作风格可能不一样，需要根据期刊调整写作
  • 多征求合作者的意见，老师的意见，避免自己无目标的尝试，降低试错成本
• 论文修改！！！
  • 认真对待审稿人的每一个问题
  • 尽量吸纳审稿人的意见，大部分情况下，审稿人提出的意见是具有一定的参考价值的
  • 对于一些算法的尝试，可以通过部分算例验证
  • 很多时候，审稿人没看懂，可能是我们没写清楚（逻辑清不清楚）
  • 审稿人提出的一些可能，要实验验证，并给出验证结果，正确则加入到正文，不正确或者无效，则在回复中说明

Jin B. — EJOR 金波SZU

An exact algorithm for the unrestricted container relocation problem with new lower bounds and dominance rules

摘要

背景

• 翻箱问题
  • 集装箱搬迁（翻箱）问题，也称为区块搬迁问题，是集装箱码头研究最多的优化问题之一。该问题旨在最小化根据特定顺序从堆场检索集装箱的搬迁总数。
  • CRP background
  • 
  • 
  • 

内容

• 本研究的目的是开发一种高效的迭代深化分支定界算法，以准确解决该问题最实际的变体之一，即具有重复优先级的无限制集装箱搬迁问题。

方法

• 为了提高所提出算法的搜索效率，设计了两个新的下界，快速计算以将它们合并到分支定界算法中。提出了一组相互一致的支配规则以减少搜索空间，同时避免过度修剪。

写作

Abstract

• EJOR abstract
  • 

Introduction

• Background
  • 概述研究关注的领域，引入研究的主题或问题
  • 根据研究问题是经典问题还是新问题，适当精简或详细背景介绍
• Container relocation problem
  • 明确提出研究问题和假设
  • 方便审稿人和读者准确理解问题
• Purpose of this study
  • 研究目的、研究意义、理论重要性
  • 方便审稿人和读者快速了解本文的贡献和定位
  • 提供一个简要的概览，介绍论文的组织结构
• 如何写好引言
• 介绍研究背景，引出研究主题，引起读者兴趣
• 明确定义问题，强调问题的重要性
• 讨论现有工作，指出研究的必要性
  • 注意和文献综述的区别
  • 有的论文会直接把文献综述写在引言中
• 明确研究目的，介绍所使用的研究方法
• 强调研究的价值和贡献
• 最后给出论文的组织结构

Literature review

• Search-based exact methods

  • 本文算法属于该类，利用表格总结现有方法的研究空白，引出研究目的

• Integer programming approaches

  • 展现文献调研的全面性

• Heuristic approaches

  • 基于指标或规则的启发式方法（本文算法用到了其中的两个）
  • 基于元启发式框架的启发式方法

• Related optimization problems

  • 展现文献调研的全面性

• 如何写好文献综述

  • 明确定义研究领域，明确界定研究范围
  • 选择与研究直接相关的文献
    • 递归式收集文献，广泛阅读，精读关键文献
  • 对文献进行主题分类，制定清晰的综述结构
  • 寻找文献中的模式和趋势，帮助读者理解该领域的发展
  • 指出现有研究的缺陷或空白，论证研究的必要性
  • S. Keshav: How to Read a Paper

• Notation and terminology

  • 符号和术语的定义有时会干扰正文的流畅性，将其放在一个单独的章节中可以减少这种干扰，使正文更加流畅。同时，该章节为读者提供了一个参考点，方便读者随时检索特定符号的含义。
  • 建议：尽可能使用简单易懂的符号系统，增加可读性。

Algorithm

• Exact algorithm
  • Iterative deepening framework
    • 先介绍主框架
  • Depth-limited search
    • 迭代算法每一轮所执行的深度受限搜索
  • Probing heuristic
    • 混合使用两个不相上下的规则启发式方法（第三轮投稿新增）
• Lower bounds
  • Existing lower bounds
    • 回顾文献中的现有下界，发现模式和趋势
  • Motivation for new lower bounds
    • 改进和创新
  • LB-TS: lower bound by the tier scan method
    • 提出新下界（理论贡献）
  • LB-PS: lower bound by the priority scan method
    • 提出新下界（理论贡献）
  • Inheritance of blocking layers
    • 介绍阻塞层的继承机制
• Dominance rules
  • Lexicographic dominance principle
    • 提出字典序支配原则，并给出证明（理论贡献）
  • Mutually consistent dominance rules
    • 提出（整理和修订）13条相互兼容的支配规则
    • 每条支配规则的正确性证明放在附录

Computational experiments

• Experimental settings：实验环境和测试数据集
• Preliminary comparison of lower bounds：初步比较所有下界，挑选后续实验的对照组
• Computational results for the benchmark datasets：主要实验结果
• Effect of the inheritance technique：对LB-TS有负面效果，对LB-PS有正面效果
• Effect of the hybrid probing strategy：混合探测策略比单独使用一个探测函数更好（第
  三轮投稿新增）
• Effect of the same-group relocation rules：箱子优先级多样性越低，效果越明显（第二
  轮投稿新增）
• Comparison to metaheuristic approaches：在1秒的时间约束下，所提出的算法依然能
  够得到有竞争力的解（第二轮投稿新增）

Conclusion and future work

• 回顾研究问题，总结主要发现，强调研究贡献
• 指出研究局限性，展望未来研究方向

如何提高学术论文写作水平

• 深入了解领域知识，精确掌握领域术语
• 广泛阅读和模仿，学习使用标准的学术写作风格
• 仔细校对论文，确保语法、拼写和标点符号无误
• 反复检查和修订论文，以提高语言流畅度和逻辑性
• 寻求导师和合作者意见

OR相关

Model

Jia S. — TRB

The seaport traffic scheduling problem: Formulations and a column-row generation algorithm

Abstract

背景

• 海港交通拥堵可能导致泊位计划执行失控，船舶严重延误和等待时间过长。
  • 

内容

• 通过优化航道和码头港区锚地的利用来调度海港的船舶交通。将交通调度问题建模为MILP，将海港的物理布局和码头运营商设计的泊位计划作为输入，以最大限度地减少船舶的停泊和出发延误以及船舶数量无法顺利靠泊或离港。

方法

• 将 MILP 重新表述为更紧凑的集划分公式，开发了一种用于解决问题的列生成算法，并提出了三种性能增强策略，即行生成方法、定价问题减少方法和启发式定价方法，以加速列生成算法的收敛。

Formulation

OBJ

• 最小化靠泊和离港迟到的总成本 以及未满足船舶服务请求的成本

Cons

• 进出船舶在航道行驶的 安全间隙
• 每艘船舶只能在某一潮汐窗口内通过航道、
• 为船舶分配锚地
• 确定船舶进出锚地的时间点
• 每个分段锚地在单个时间点只能被一艘船占用

Model

• ORIG
  • 
  • 
• Reformulated
  • 

Solution

• Set-partitioning formulation
• Column generation
• Column-row generation
• Reducing the pricing problems
• Heuristic pricing
• Branch-and-bound method

Jin B. — EJOR

An exact algorithm for the unrestricted container relocation problem with new lower bounds and dominance rules

Graph Model

背景

• 集装箱搬迁（翻箱）问题，也称为区块搬迁问题，是集装箱码头研究最多的优化问题之一。该问题旨在最小化根据特定顺序从堆场检索集装箱的搬迁总数。
  • 
  • 

Graph M

• 

Formulation

• 建模思路
  • 借鉴经典问题的建模思路
  • 混合整数规划MILP（非线性—>线性）
  • 验证模型
    • 求解器（CPLEX GUROBI COPT）
    • 小规模算例（最优解对比算法性能）
    • 验证结果
• 建模
  • 初始模型，检查是否存在错误，所有约束是否表达
  • 编程验证、软件求解、输出结果，检查
  • 根据结果反馈修改模型
  • 对于文献中的问题，可通过不同的建模方式改进原文献提出的模型，并进行对比实验，突出建模方面的贡献

Algorithm

算法及实验

问题求解

精确算法

• 求解器（Branch and cut）
  • CPLEX
  • GUROBI
  • COPT
  • …
• 分支定界（Branch and bound）
• 分支切割（Branch and cut）
• 列生成（Column generation）
• 分支定价（Branch and price）
• Benders decompositon
• Logic-based Benders decomposition

启发式算法

• 传统基于规则或构造启发式方法
• 局部搜索方法
• 元启发式方法
  • TS SA ALNS
• 进化算法
  • GA PSO AC
• 基于数学的启发式方法
  • Relax and fix
  • Fix and optimize
  • Kernel search

算法选择

• 合适算法
  • 问题本身研究进度，哪类方法最有效
  • 问题归类，相似问题的最有效方法
  • 问题本身，平衡，方法有效且能完成（理论分析和编程实现）
• 不同方法的贡献点挖掘
  • 精确算法：框架适用，子问题的求解
  • 数学启发式：框架适用，基于模型的设计
  • 元启发式：初始解的设置，基于问题特点的算法设计
• 选址调度问题的算法设计
  • 选址和调度决策，具有较好的分解性质
  • 在经典的并行机调度问题中，LBBD表现出不错的效果
  • 而选址一调度问题是经典并行机调度问题的拓展
  • 可能LBBD对求解选址-调度问题有效
  • 因此，拟选用该方法对提出问题进行求解
• 贡献点挖掘
  • 框架的适用性（首次应用到所研究的问题）
  • 针对问题的特点，对框架的适用过程
  • 针对问题特点，对算法的独特设计（包含分解后子问题的求解）
  • 多个算法组合：要说明组合的必要性，如何互补提升效果；多层算法：讲清楚每层的贡献，多层之间的连接关系

实验设计

• 算例生成
  • 算例的选用
  • 经典问题（Benchmark）
  • 新问题（实际案例 + 随机算例 = new Benchmark）
  • 算例生成要充分参考文献，尊重现实数据
  • 算例数量适中
  • 对场景的覆盖程度
  • 小规模算例的必要性（验证、说明）
• 结果展示
  • 定义核心指标（通用）
  • 单目标问题，通常：上界、下界、gap、时间等指标
  • 多目标问题，通常：帕累托解的数量、e-dominance
  • 现实案例：展示算法给出的解决方案对应的收益或成本优于企业当前解决方案
  • 图文并茂、图表结合
• 结果分析
  • 对图表的解释，全面且有重点
  • 横向纵向比较
  • 基于图表，对规律进行总结、对异常进行解释
  • 关键参数的灵敏度分析
  • 算法性能分析实验（算法贡献点、实验结果支撑）

Appendix

• 飞书 Docs: https://pvkljwm7si8.feishu.cn/drive/folder/Wj03fCb8CllPkSdFRclcTV4an7e Password: @1N61P/@
• 参会反馈
  •