An Exact Algorithmic Framework for a Class of Mixed-Integer Programs with Equilibrium Constraints
研究了一类含整数和连续变量的均衡约束数学规划问题，设计了基于分支定界的精确算法框架，并在考虑排队过程的竞争设施选址问题上验证了有效性。
In this study, we consider a rich class of mathematical programs with equilibrium constraints (MPECs) involving both integer and continuous variables. Such a class, which subsumes mathematical programs with complementarity constraints, as well as bilevel programs involving lower level convex programs is, in general, extremely hard to solve due to complementarity constraints and integrality requirements. For its solution, we design an (exact) algorithmic framework based on branch-and-bound (B&B) that treats each node of the B&B tree as a separate optimization problem and potentially changes its formulation and solution approach by designing, for example, a separate B&B tree. The framework is implemented and computationally evaluated on a specific instance of MPEC, namely a competitive facility location problem that takes into account the queueing process that determines the equilibrium assignment of users to open facilities, and a generalization of models for which, to date, no exact method has been proposed.