大M法

在使用线性规划的时候，遇到了一个场景。

这里简单的说一下场景，要求广告要至少投放2个城市，现在有3个城市可供选择。但是城市投放量要么不投，要投放至少投放100cpm。

这种情况下如何转换成线性规划呢？

这里就可以使用大M法，来将非线性约束线性化，引入binary变量(即只有0和1)，这里ca={0,1}，然后引入一个极大值M，构建如下约束

// 由于有三个城市，这里我们引入3个binary变量，即ca1、ca2、ca3
// 每个城市的投放量 c1、c2、c3
// 0表示投放，1表示不投放
1. ca1+ca2+ca3 <= 1
// 当ca1等于0时，也就是c1进行投放,此时c1>=100
// 当ca1等于1时，也就是c1不进行投放，此时M+c1<=M，如果要满足，必须是c1等于0
// 依次写 c2和c3的表达式
2. 100 =< ca1 * M + c1 <= M

根据自己的情况，来选取M的值

ExpressionsBasedModel model = new ExpressionsBasedModel();
model.addVariable(Variable.makeInteger("c"+1).lower(0).upper(3000).weight(5));
model.addVariable(Variable.makeInteger("c"+2).lower(0).upper(3000).weight(6));
model.addVariable(Variable.makeInteger("c"+3).lower(0).upper(3000).weight(23));

model.addVariable(Variable.makeBinary("ca1").lower(0).upper(1).weight(0));
model.addVariable(Variable.makeBinary("ca2").lower(0).upper(1).weight(0));
model.addVariable(Variable.makeBinary("ca3").lower(0).upper(1).weight(0));

// 总投放量为3000
Expression expression = model.addExpression("e" + 1);
expression.set(0,1);
expression.set(1,1);
expression.set(2,1);
expression.lower(3000);
System.out.println(expression);


// ca1+ca2+ca3 <= 1
Expression expression2 = model.addExpression("e" + 2);
expression2.set(3,1);
expression2.set(4,1);
expression2.set(5,1);
expression2.upper(1);
System.out.println(expression2);

// 设定M为5000
// 100 =< ca1 * M + c1 <= M
Expression expression3 = model.addExpression("e" + 3);
expression3.set(3,5000);
expression3.set(0,1);
expression3.upper(5000);
System.out.println(expression3);

Expression expression4 = model.addExpression("e" + 4);
expression4.set(3,5000);
expression4.set(0,1);
expression4.lower(100);
System.out.println(expression4);

// 100 =< ca2 * M + c2 <= M
Expression expression5 = model.addExpression("e" + 5);
expression5.set(4,5000);
expression5.set(1,1);
expression5.upper(5000);
System.out.println(expression5);

Expression expression6 = model.addExpression("e" + 6);
expression6.set(4,5000);
expression6.set(1,1);
expression6.lower(100);
System.out.println(expression6);

// 100 =< ca3 * M + c3 <= M
Expression expression7 = model.addExpression("e" + 7);
expression7.set(5,5000);
expression7.set(2,1);
expression7.upper(5000);
System.out.println(expression7);

Expression expression8 = model.addExpression("e" + 8);
expression8.set(5,5000);
expression8.set(2,1);
expression8.lower(100);
System.out.println(expression8);

model.setOptimisationSense(Optimisation.Sense.MIN);
model.options.debug(SolverORTools.class);
model.options.progress(SolverORTools.class);

SolverORTools tools = SolverORTools.INTEGRATION.build(model);
Optimisation.Result result = tools.solve(null);
System.out.println(result);

结果为

1	{ 2900.0, 100.0, 0.0, 0.0, 0.0, 1.0 }