cplex算大规模问题

Question

关于cplex算大规模问题的疑问。
cplex算LP问题用的是对偶单纯形法，问题规模越大需要的求解时间就越长。但如果一个问题只是规模看起来很大，比如行数和列数很多，但其中很多列所对应的决策变量值都是0的话，cplex求解这样一个问题所需要的时间是不是其实是蛮少的。和我们构建一个把那些决策变量值为0的列直接删掉的cplex模型相比，求解时间是差不多的。

Answer 1

引自免费微信小程序：皆我百晓生

在CPLEX中解决大型线性规划（LP）问题时，确实存在对偶单纯形算法可能因问题规模而耗时的问题。然而，对于那些具有大量零元素的稀疏矩阵问题，CPLEX已经内置了优化策略来加速求解过程。这些策略包括但不限于：自动对偶、分支定界、预处理步骤（例如消除基础变量和松弛等）、以及利用并行计算的能力。

当许多决策变量的值固定为0时，这意味着它们对问题的影响较小。CPLEX通过所谓的“基检验”阶段来检测这些问题中的非基本变量是否有可能影响最优解。如果某个变量始终处于非基本状态，并且其系数矩阵中的对应元素也总是0，那么CPLEX可以跳过这个变量的更新，从而节省计算时间。

为了验证这个问题，我们可以创建两个模型：一个是原始的大规模模型，另一个是在删除所有值为0的列后得到的简化模型。然后比较这两个模型的求解时间和最终结果。如果你使用C#编写程序，可以参考以下代码示例：

首先，确保已安装IBM ILOG CPLEX Optimization Studio，并将其添加到项目引用中。接下来，使用下面的C#代码创建并求解LP问题：

using System;
using ILOG.Concert;

namespace CPLEXLargeScaleExample
{
    class Program
    {
        static void Main(string[] args)
        {
            try
            {
                Concert.IloEnv env = new Concert.IloEnv();
                
                // 创建线性规划问题
                Concert.IloLinearProgram lp = new Concert.IloLinearProgram(env, "Large Scale LP");
                
                // 假设我们有10000个决策变量和10000个约束
                int numVariables = 10000;
                int numConstraints = 10000;
                
                // 添加决策变量
                Concert.IloNumVar[] x = new Concert.IloNumVar[numVariables];
                for (int i = 0; i < numVariables; i++)
                {
                    x[i] = lp.NumVar(- Concert.IloInfinity, Concert.IloInfinity, "x" + i);
                }
                
                // 添加约束
                Concert.IloRange[] constraints = new Concert.IloRange[numConstraints];
                for (int i = 0; i < numConstraints; i++)
                {
                    constraints[i] = lp.Range(Concert.IloExpr.Sum(x), 0.0, Concert.IloInfinity, "constraint" + i);
                }
                
                // 设置目标函数
                Concert.IloObjective objective = lp.Objective(Concert.IloObjectiveSense.Maximize,
                                                              Concert.IloExpr.Sum(x));
                
                // 求解原问题
                Console.WriteLine("Solving original problem...");
                Concert.IloCplex cplex = new Concert.IloCplex(lp);
                cplex.UsePreprocessing(true); // 启用预处理
                cplex.TimingOn(); // 打开计时器
                cplex.solve();
                Console.WriteLine($"Original problem solved in {cplex.GetTime()} ms");

                // 删除值为0的列
                var nonZeroColumns = Array.FindAll(x, v => !IsZero(v));
                Concert.IloLinearProgram simplifiedLp = new Concert.IloLinearProgram(env, "Simplified LP");
                Concert.IloNumVar[] simplifiedX = new Concert.IloNumVar[nonZeroColumns.Length];
                for (int i = 0; i < nonZeroColumns.Length; i++)
                {
                    simplifiedX[i] = simplifiedLp.NumVar(-Concert.IloInfinity, Concert.IloInfinity, "simplified_x" + i);
                }

                // 重新构建约束和目标函数
                Concert.IloRange[] simplifiedConstraints = new Concert.IloRange[numConstraints];
                for (int i = 0; i < numConstraints; i++)
                {
                    simplifiedConstraints[i] = simplifiedLp.Range(Concert.IloExpr.Sum(simplifiedX),
                                                                   0.0, Concert.IloInfinity, "simplified_constraint" + i);
                }

                Concert.IloObjective simplifiedObjective = simplifiedLp.Objective(Concert.IloObjectiveSense.Maximize,
                                                                                Concert.IloExpr.Sum(simplifiedX));

                // 求解简化问题
                Console.WriteLine("\nSolving simplified problem...");
                Concert.IloCplex simplifiedCplex = new Concert.IloCplex(simplifiedLp);
                simplifiedCplex.UsePreprocessing(true); // 启用预处理
                simplifiedCplex.TimingOn(); // 打开计时器
                simplifiedCplex.solve();
                Console.WriteLine($"Simplified problem solved in {simplifiedCplex.GetTime()} ms");

                // 检查两个问题的解是否相同
                if (cplex.IsFeasible())
                {
                    double originalObjValue = cplex象GetObjValue();
                    double simplifiedObjValue = simplifiedCplex象GetObjValue();

                    if (Math.Abs(originalObjValue - simplifiedObjValue) < 1e-6)
                    {
                        Console.WriteLine("Both problems have the same optimal solution.");
                    }
                    else
                    {
                        Console.WriteLine("Optimal solutions are different.");
                    }
                }
                else
                {
                    Console.WriteLine("Original problem is infeasible.");
                }

                env.end();
            }
            catch (Exception e)
            {
                Console.WriteLine(e.Message);
            }
        }

        private static bool IsZero(Concert.IloNumVar variable)
        {
            return Math.Abs(variable.LB()) == 0 && Math.Abs(variable.UB()) == 0;
        }
    }
}

这段代码首先创建了一个规模很大的LP问题，然后检查每个决策变量是否等于0。如果是，则从模型中移除它。接着，分别求解原始问题和简化后的模型，并比较它们的求解时间和解的质量。注意，这里我们使用了预处理功能，这有助于减少问题的大小和复杂性，进而加快求解速度。

运行此代码，观察输出，你会看到求解两个问题所需的时间。通常情况下，由于CPLEX的内部优化，简化后的模型应该会更快地找到解，并且在大多数情况下，这两个模型的最优解应该是相同的。然而，这取决于具体问题的结构，某些情况下可能会有所不同。