cplex入门系列（二）--- 线性规划求解

一、cplex项目模板

一般一个的cplex项目，一般分为五个模块，分别是创建模型、定义优化参数、设置目标函数、设置约束和模型求解及输出。下面针对这五个模块使用cplex的Java API来进行介绍。

1.1 创建模型

即在内存中开辟一个空间来实例化IloCplex类；

IloCplex cplex = new IloCplex(); // 创建一个模型

1.2 定义优化参数

这里定义将要求解的优化参数，常见的参数类型包括单个变量、一维及二维数组类型。

1.2.1 单变量定义

在实际生产问题中，常见的变量类型就实数，整数比较常见：
○ 实数型变量 cplex.numVar
○ 整数型变量 cplex.intVar
单变量参数，主要是值变量的取值范围，例如该变量取值范围为 $0≤x≤5$ ，若不想定义范围也可以设置为-Double.MAX_VALUE和Double.MAX_VALUE,表示负无穷到正无穷；比如cplex.numVar(0,5)，表示 $0≤x≤5$ 。

1.2.2 一维数组定义

○ 实数型变量 cplex.numVarArray(num,min,max)
○ 整数型变量 cplex.intVarArray(num,min,max)
参数表示数组的大小(num)，最小值(min)和最大值(max)，这样定义的就是三个定义域相同的变量；
如果要为每个变量设置不同的范围

double[] rangeVar = {0,3,2,8,1,7}; // 每个变量的最小值和最大值
IloNumVar[] x = new IloNumVar[3];
for(int i=0;i<3;i++){
    x[i] = cplex.numVar(rangeVar[2*i], rangeVar[2*i+1]);
}

这样就将数组中的三个变量设置了不同的取值范围，分别为[0,3]，[2,8]，[1,7]

1.2.3 二维数组定义

IloNumVar[][] x2array1 = new IloNumVar[2][];
for (int i=0; i<2; i++){
    x2array1[i] = cplex.numVarArray(2, 0.0, 5.0);
}
IloIntVar[][] x2array2 = new IloIntVar[2][];
for (int i=0; i<2; i++){
    x2array2[i] = cplex.intVarArray(2, 0, 5);
}

1.3 设置目标函数和约束

目标函数一般是取一个表达式的最大值或者最小值，约束一般是设定一个表达式的取值范围，一个共同点就是都需要先定义表达式，而且它们定义表达式的方式是完全相同的。

1.3.1 定义表达式

官方根据表达式类型的不同提供了不同的接口，包括：

接口	描述
IloIntExpr/IloNumExpr	整数/实数表达式的基本公共接口
IloLinearIntExpr/IloLinearNumExpr	整数/实数类型变量的一次线性表达式的接口
IloLQIntExpr/IloLQNumExpr	具有线性和二次项的一般表达式
IloQuadIntExpr/IloQuadNumExpr	整数/实数型二次数值表达式

需要根据模型表达式类型选择合适自己的接口形式，比如 $x_1+2x_2+3x_3$ ，属于线性类型，那么就可以一次线性表达式的接口：

IloNumVar[] x =cplex.numVarArray(3, -5, 5);
IloLinearNumExpr cs = cplex.linearNumExpr();
cs.addTerm(1, x[0]);
cs.addTerm(2, x[1]);
cs.addTerm(3, x[2]);

每个接口都提供了非常多的方法，详细参考官方文档的使用方法和说明。尽管官方为不同形式的表达式提供了不同的接口，但是存在一定的问题，比如无法在一次线性规划表达式中添加二次项，当表达式比较复杂的时候通常不止一种类型。因此一般就用最基本的公式接口IloNumExpr，在这个接口中可以利用cplex模型库中的加减乘除来添加任何形式的表达式。

先创建模型Ilocplex cplex = new IloCplex(); 然后通过cplex.xxx的方式使用模型中的各种运算方法，常用的包括：

方法	说明
sum	求和
diff	求差
prod	乘积
abs	绝对值

有了以上这四种方法基本就可以应对大部分的表达式了，比如 $x_1+2x_2+3x_3$ ，用基本公共接口表示为：

IloNumVar[] x =cplex.numVarArray(3, -5, 5);
double[] vars = {1,2,3};
IloNumExpr cs = cplex.numExpr();
for(int i=0;i<3;i++){
    cs = cplex.sum(cs, cplex.prod(x[i], vars[i]));
}

虽然这种方式增加了代码量，但是代码可读性增强了，所以这种方式会更好，再比如，求变量x的平方和绝对值之和：

IloNumVar[] x =cplex.numVarArray(3, -5, 5);
IloNumExpr cs1 = cplex.numExpr();
IloNumExpr cs2 = cplex.numExpr();
for(int i=0;i<3;i++){
    cs1 = cplex.sum(cs1, cplex.abs(x[i]));
    cs2 = cplex.sum(cs2, cplex.prod(x[i], x[i]));
}

1.3.2 定义目标函数

假设定义后目标函数的表达式用obj表示：

函数	说明
cplex.addMinimize(obj)	求obj的最小值
cplex.addMaximize(obj)	求obj的最大值

1.3.3 定义约束

假设定义后约束的表达式用cs表示：

函数	说明
cplex.addEq(cs,a)	$cs=a$
cplex.addLe(cs,a)	$cs{\le}a$
cplex.addGe(cs,a)	$cs{\ge}a$
cplex.addRange(a,cs,b)	$a{\le}cs{\le}b$

在添加了约束后我们可以通过cplex.diff(cs,cs)来清空表达式cs，然后就可以在cs中添加新的表达式。

1.4 清空表达式

有时候在定义目标函数和约束时需要通过循环来定义新的表达式，每次重新初始化表达式很麻烦，这时候就需要清空表达式：

cplex.diff(cs,cs)
cplex.numExpr()
第一种方式有时候会爆出内存溢出的错误，因此更推荐使用第二种方式。

1.5 模型求解及输出

模型求解以及输出的模板如下所示：

if (cplex.solve()) {
    cplex.output().println("Solution status = " + cplex.getStatus());
    cplex.output().println("Solution value = " + cplex.getObjValue());
    double[] val = cplex.getValues(x);
    for (int j = 0; j < val.length; j++){
        System.out.println("x" + (j+1) + "  = " + val[j]);
    }
}
cplex.end();

其中

函数	说明
cplex.getStatus()	获得模型求解的状态
cplex.getObjValue()	获取目标函数的值
cplex.getValues(x)	获取优化变量的值
cplex.end()	结束模型

模型求解包括以下几个状态

状态	说明
Optimal	找到了一个最优的解决方案
Feasible	找到了一个可行的解决方案
Infeasible	该模型不可行
Error	遇到了错误
Bounded	模型不是无界的
Unbounded	模型是无界的

二、cplex 项目实战

2.1 案例一

该案例为《运筹学》清华大学第四版P15例2-1题目，具体应用场景请参考教材。
目标函数： $max⁡ z=2x_1+3x_2$
约束条件：
$x_1+2x_2≤8$
$4x_1≤16$
$4x_2≤12$
$x_1,x_2≥0$

package com.opreation.research;
import ilog.concert.*;
import ilog.cplex.IloCplex;

public class CplexTest {
    public static void main(String[] args) throws IloException {
        try{
            // 1. 创建模型
            IloCplex cplex = new IloCplex();

            // 2. 定义优化参数
            IloNumVar[] x = cplex.numVarArray(2, 0, Double.MAX_VALUE);
            double[] c = {2,3};
            IloNumExpr cs1 = cplex.numExpr();
            for(int i=0;i<2;i++){
                cs1 = cplex.sum(cs1,cplex.prod(c[i], x[i]));
            }


            // 3. 设置目标函数
            cplex.addMaximize(cs1);
            // 4. 设置约束
            cplex.addLe(cplex.sum(x[0], cplex.prod(2, x[1])), 8);
            cplex.addLe(cplex.prod(4, x[0]), 16);
            cplex.addLe(cplex.prod(4, x[1]), 12);

            // 5. 模型求解及输出
            if(cplex.solve()){
                cplex.output().println("Solution status = " + cplex.getStatus());
                cplex.output().println("Solution Value = " + cplex.getObjValue());
                double[] val = cplex.getValues(x);
                for(int j=0;j<2;j++){
                    System.out.println("x" + (j+1) + " = " + val[j]);
                }
            }
            cplex.end();
        } catch (IloException e){
            System.err.println("Concert exception caught: " + e);
        }

    }
}

运行结果

Tried aggregator 1 time.
LP Presolve eliminated 2 rows and 0 columns.
Reduced LP has 1 rows, 2 columns, and 2 nonzeros.
Presolve time = 0.00 sec. (0.00 ticks)

Iteration log . . .
Iteration:     1   Dual objective     =            14.000000
Solution status = Optimal
Solution Value = 14.0
x1 = 4.0
x2 = 2.0

可以根据上面的运行结果获悉，该问题为LP(线性规划)求解问题，迭代了一次，对偶目标解为14，解的状态为Optimal，即找到了一个最优的解决方案，目标函数的最优解为14，对应的变量x1和x2分别取4和2。

2.2 案例二

该案例为《运筹学》清华大学第四版P60例2-10题目，具体应用场景请参考教材。
目标函数： $min⁡ z=0x_1+0.1x_2+0.2x_3+0.3x_4+0.8x_5$
约束条件：
$x_1+2x_2+x_4=100$
$2x_3+2x_4+x_5=100$
$3x_1+x_2+2x_3=3x_5=100$
$x_1,x_2,x_3,x_4,x_5≥0$

package com.opreation.research;
import ilog.concert.*;
import ilog.cplex.IloCplex;

import org.omg.PortableInterceptor.SYSTEM_EXCEPTION;

import java.util.HashSet;
import java.util.Random;

public class CplexTest {

    public static void main(String[] args) throws IloException {
        try{


            // 1. 创建模型
            IloCplex cplex = new IloCplex();


            // 2. 定义优化参数
            IloNumVar[] x = cplex.numVarArray(5, 0, Double.MAX_VALUE);
            double[] c = {0, 0.1, 0.2, 0.3, 0.8};
            IloNumExpr cs1 = cplex.numExpr();
            for(int i=0;i<5;i++){
                cs1 = cplex.sum(cs1,cplex.prod(c[i], x[i]));
            }


            // 3. 设置目标函数
            cplex.addMinimize(cs1);
            // 4. 设置约束
            cplex.addEq(cplex.sum(x[0], cplex.prod(2, x[1]), x[3]), 100);
            cplex.addEq(cplex.sum(cplex.prod(2, x[2]), cplex.prod(2, x[3]), x[4]), 100);
            cplex.addEq(cplex.sum(cplex.prod(3, x[0]), x[1], cplex.prod(2, x[2]), cplex.prod(3, x[4])), 100);
            cplex.addGe(x[0], 0);
            cplex.addGe(x[1], 0);
            cplex.addGe(x[2], 0);
            cplex.addGe(x[3], 0);
            cplex.addGe(x[4], 0);


//            // 5. 模型求解及输出
            if(cplex.solve()){
                cplex.output().println("Solution status = " + cplex.getStatus());
                cplex.output().println("Solution Value = " + cplex.getObjValue());
                double[] val = cplex.getValues(x);
                for(int j=0;j<5;j++){
                    System.out.println("x" + (j+1) + " = " + val[j]);
                }

            }
            cplex.end();
        } catch (IloException e){
            System.err.println("Concert exception caught: " + e);
        }

    }
}