基于Yalmip工具箱的整数规划模型求解方法

熊文涛， 雍龙泉

(1.湖北工程学院 数学与统计学院， 湖北 孝感 432000；2.陕西理工学院 数学与计算机科学学院， 陕西 汉中 723001)

整数规划模型是运筹学中一类常见的数学模型，在现实生活中有着广泛的应用。在许多仿真实验中，求解整数规划最常见的工具有Matlab和Lingo软件。然而，Matlab软件并没有提供直接求解一般整数规划的内部函数。尽管它提供了求解0-1规划的bintprog函数，但其输入的约束条件要求采用矩阵乘积形式，这对于人们习惯用求和或任意形式构造成的模型，不便于转换成标准的矩阵乘积形式，求解起来非常费时。虽然Lingo软件能根据人们计算习惯将求解一般整数规划问题的模型转换成程序语句，但无法自动多次求解整数规划，仅限于每次求解一个优化模型。为方便整数优化模型求解，本文将介绍求解最优化模型的Yalmip工具箱。Yalmip是在Matlab软件的仿真平台上，采用Matlab的程序设计语言开发的一个工具箱。它不仅可以利用Matlab强大的计算能力，调用Matlab软件自带的优化工具箱和Matlab语言编写的其他工具箱中的函数，而且还能将多种优化求解器(如Cplex和Gurobi等工具)结合在一起使用。本文阐述了利用Yalmip工具箱求解整数规划的一般方法，并通过一个具体的实例说明使用Yalmip工具箱在求解整数规划模型的一般方法。

1 Yalmip工具箱简介

Yalmip是由Lofberg开发的一种免费的Matlab工具箱[1]，其最初目的是为求解控制与系统理论中的半定规划和线性矩阵不等式而设计的。后来经过不断发展，可以求解更多的优化模型，如二阶锥规划、混合整数规划、正项几何规划、双线性矩阵不等式以及多参数线性规划和二次规划等。Yalmip最大的特色在于能集成许多外部的最优化求解器，无论这些求解器是否采用Matlab程序语言编写的。通常，这些求解器把优化问题描述成一个非常紧凑的格式，学习、使用起来比较耗时，并且编程时容易出错。为了克服这一方面的不足，Yalmip提供了一种合适的建模语言和编程接口，以方便不同求解器之间的集成。Yalmip也能调用Matlab自带的优化工具箱，特别是对于未知变量较多的线性规划问题，调用Linprog函数不需要转换成矩阵的形式，使用起来非常方便。Yalmip也包含内置的整数规划求解器，可以求解一些小型的整数规划问题，并且与外部的整数规划求解器具有较好的兼容性。

Yalmip作为一个Matlab的工具箱，与一般的外部工具箱安装相同。使用者可以通过该工具箱的网址http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Tutorials.Installation下载安装包并解压后，可通过如下步骤将对应的文件夹放到Matlab路径里：首先点击File中的Set Path菜单，然后点击Add with subfolders菜单，找到解压好的文件夹Yalmip，最后确定、保存即可。对于外部的一些优化求解器，可采用类似的方法放入到Matlab路径中。

2 整数规划模型及其Yalmip工具箱的程序实现

一般的整数规划可表示为：

(1)

其中，f(x)为目标函数，gi(x)和hj(x)是定义在Rn上的多元实值函数，决策变量x至少有一个分量为整数。当x全部为整数时，模型(1)为纯整数规划。

特别地，当f(x),gi(x),hj(x)均为线性函数时，此模型(1)称为整数线性规划，模型(1)可重新改写为如下的矩阵表示形式：

(2)

其中c是n维列向量，A和Aeq分别是m×n矩阵和l×n矩阵，b是m维列向量，beq是l维列向量。

对于许多实际问题，人们习惯于用求和形式与任意的符号形式进行表示，而不是矩阵的乘积形式，于是模型(2)又可写为模型(3)的形式，即：

(3)

其中ci，bi，beqs分别向量c，b，beq的分量，aij，aeqsj则分别A,Aeq是矩阵中元素。

为了方便，假设模型(3)中所有未知变量 全部为整数。若部分变量不是整数，则只需改变申明变量类型的函数即可。表1给出了求解整数线性规划的一般程序。

表1 求解整数线性规划的一般程序模式

3 实例求解

3.1 问题描述

以文献[2]中一个电力生产问题作为实例，介绍使用Yalmip工具箱求解整数规划模型的求解方法。为满足每日电力需求(单位为MW，见表2)，有4种不同类型的发电机可供选用。所有发电机都存在一个启动成本(在每个时段开始时才允许启动或关闭)，以及工作于最小功率状态时的固定成本，并且如果功率高于最小功率，则超出部分的功率每兆瓦每小时还存在一个边际成本。另外，每种发电机都有一个最大发电能力，当接入电网时，其输出功率不应低于某一最小输出功率，具体数据见表3。与启动发电机不同，关闭发电机不需要付出任何代价。在任意时刻，正在工作的发电机组必须留出20%的发电能力余量，以防用电量突然上升。每个时段应分别使用哪些发电机才能使每天的总成本最小？

表2 每日用电需求(MW)

表3 发电机情况

3.2 模型建立与求解

假设P为发电机型号集合，T={1，2，…，NT}为每天的时段集合，Lenj,Demj分别表示第j个时段的长度(小时数)和电网的用电量需求，Pmini，Pmaxi,Availi,Cstarti,Cmini,Caddi为i型发电机的最小功率、最大功率、可用的发电机数目、启动成本、最小功率每小时工作成本、以及每兆每小时的边际成本。未知变量startij，workij及paddij分别表示在时段j开始工作的型号i的发电机数量，在时段j内工作型号i的发电机数量，以及型号i的发电机在时段j内功率超出其最低功率之上的量。根据上述问题描述可以得到如下的整数规划模型。

(4)

其中，约束条件(4.1)表示对于每个类型和每个时段的发电机(型号为i)，其额外功率都不能超过Pmaxi-Pmini；约束条件(4.2)表示每个时段内发电量都应满足用电需求；约束条件(4.3)则表示在不启动新的发电机的前提下，当前正在工作的发电机的发电能力必须高于实际用电量的20%；另外，根据需求，当不关闭发电机时，在开始时段时，投入开始工作的发电机数目应等于时段j和j-1间工作的发电机数量之差。如果有些发电机可能会被关闭，那么开始工作的发电机数量应至少等于此差值，于是得到约束条件(4.4)；约束条件 (4.5)表示当日午夜和次日凌晨这两个时段的情形。

针对此模型，可以通过表4的程序语句计算出其最优解和最优值，得到发电机的使用计划，其结果见表5。在Windows xp操作系统，3.20 GHz Intel Core i5 CPU和 4 GB RAM的PC上求解此整数规划，时间仅用了0.3 s。表5的结果表明：对于型号1的发电机，时段1时有3台在工作，时段2开始时启动1台，时段4开始时启动3台，时段4之后关闭4台,4台型号2的发电机都将连续工作；对于型号3的发电机，时段1时有2台在工作，时段2 开始时启动6台，时段6结束后关闭4台，一天结束时再关闭2台；对于型号4的发电机，时段2开始时启动3台，到下一时段时关闭2台，然后在下面的几个时段这2台反复开闭，

表4 求解模型(4)的Matlab程序

直到一天结束时，所有发电机都关闭。每种型号的发电机在每个时段的总功率可以通过发电机使用数量、最小输出功率和额外功率计算，如型号1的发电机在第2时段的总功率为4600 MW。

4 结语

整数规划模型是运筹学中一类常见的优化求解问题，在实际应用中有着非常广泛的应用。由于Matlab软件并没有提供直接求解一般整数规划的内部函数，不便于人们直接对一般整数规划优化求解问题。为方便整数规划问题求解，本文利用Matlab平台，介绍了一种使用Yalmip工具箱求解整数规划问题的一般方法。该方法能利用Matlab的强大计算能力，以Matlab为平台调用Yalmip工具箱对优化问题进行求解，编程方式具有灵活、直观等优点。而且利用Yalmip能够集成多种优化求解器的优点，该方法能方便求解其他类型的优化问题，如线性规划、二次规划和一般的非线性规划，便于对多个求解器计算的结果进行比较和选择。以电力生产问题作为实例，说明了使用Yalmip工具箱求解整数规划模型的过程。计算结果表明了本文方法的有效性。

表5 发电机的使用计划

[参 考 文 献]

[1] Lofberg J. YALMIP: A toolbox for modeling and optimization in MATLAB[C]//Proceedings of 2004 IEEE International Symposium on Computer Aided Control Systems Design, 2004:284-289.

[2] Gueret C,Prins C,Sevaux M.运筹学案例[M].北京: 北京林森科技发展有限公司,2006.