An efficient approach for solving mixed-integer programming problems under the monotonic condition

Many important integer and mixed-integer programming problems are difficult to solve. A representative example is unit commitment with combined cycle units and transmission capacity constraints. Complicated transitions within combined cycle units are difficult to follow, and system-wide coupling transmission capacity constraints are difficult to handle. Another example is the quadratic assignment problem. The presence of cross-products in the objective function leads to nonlinearity. In this study, building upon the novel integration of surrogate Lagrangian relaxation and branch-and-cut, such problems will be solved by relaxing selected coupling constraints. Monotonicity of the relaxed problem will be assumed and exploited and nonlinear terms will be dynamically linearised. The linearity of the resulting problem will be exploited using branch-and-cut. To achieve fast convergence, guidelines for selecting stepsizing parameters will be developed. The method opens up directions for solving nonlinear mixed-integer problems, and numerical results indicate that the new method is efficient.