Technical Note - Complementary Programming
Technical Note - Complementary Programming
复制标题
技术说明 - 补充编程
作者：
T. Ibaraki
一个数学规划问题P：最小化z = dTx + eTu + fTv，满足Ax + Bu + Cv ≠ g，x，u，v ≠ 0，uTv = 0，称为互补规划（CP）问题。条件uTv = 0区分CP问题从普通的LP问题。许多非线性规划问题都可以用这种形式表示，包括绝对值规划问题、0-1混合整数规划问题、二次规划问题等等。本文提出了一个求解CP问题的分枝定界算法，并给出了一些计算结果。
A mathematical programming problem P: minimize z = dTx + eTu + fTv subject to Ax + Bu + Cv ≧ g, x, u, v ≧ 0, uTv = 0, is called a complementary programming (CP) problem. The condition uTv = 0 distinguishes CP problems from ordinary LP problems. A variety of nonlinear programming problems can be formulated in this form, including absolute-value programming problems, 0-1 mixed-integer-programming problems, quadratic-programming problems, and so forth. This paper proposes a branch-and-bound algorithm for CP problems and reports some computational results.