离散优化

离散优化

离散优化又称整数规划,是数学规划中研究变量全部或部分取整数值的分支。根据变量约束形式可分为纯整数规划、混合整数规划及0-1规划三类,其中0-1规划要求变量仅取0或1值 。

该领域通过分支定界法、割平面法、隐枚举法等算法求解,典型问题包括背包问题、旅行商问题及生产调度问题。二进制分解技术可将有界整数规划转化为0-1规划,蒙特卡洛法通过随机采样处理非线性整数规划 。

离散优化求解器始于1958年Ralph E. Gomory提出的割平面算法,后续发展出分支定界、分支切割等算法。2018年后国产求解器CMIP、COPT、MindOpt相继问世,2023年国产技术在线性规划和整数规划测评中获得全球前列排名 。

想要了解更多“离散优化”的信息,请点击:离散优化百科

标签:离散,优化,例题