标题： 有限支撑低维不确定性的拟凸机会约束的预处理技术 显示英文标题

标题： Presolve techniques for quasi-convex chance constraints with finite-support low-dimensional uncertainty

摘要： 机会约束规划（CCP）在优化中代表了保守性和鲁棒性之间的权衡。在许多CCP中，人们在由随机向量$\xi$连续参数化的概率约束下优化目标函数。在这项工作中，我们研究了一种特殊情况，即约束条件是准凸的，并且与$\xi$相关。此外，向量$\xi$的支撑集是由$N$个场景组成的集合，在$p=2$或$p=3$维度上。一般来说，即使约束条件和目标函数在决策变量上都是凸的，CCP的可行域是非凸的，使其成为一个困难的问题。然而，在温和假设下，许多CCP可以重新表述为大$M$混合整数凸规划（MICP）。不幸的是，这些MICP的难度随着场景数量的增加而急剧上升，限制了在合理时间内可实际求解的实例。为了减少MICP重新表述中考虑的有效场景数量并加速求解，我们提出了基于计算几何的预处理技术并进行了测试。我们的技术可以在求解常规MICP之前产生证书，以预先丢弃或选择某些场景。 此外，在预求解过程中聚合的信息能够利用并加强大常数$M$的可能性。 我们的数值实验表明，对于一类包括有趣类型设施选址问题的概率投影问题而言，花费时间进行预求解比直接求解更有效。 显示英文摘要

摘要： Chance-constrained programs (CCP) represent a trade-off between conservatism and robustness in optimization. In many CCPs, one optimizes an objective under a probabilistic constraint continuously parameterized by a random vector $\xi$. In this work, we study the specific case where the constraint is quasi-convex with $\xi$. Moreover, the support of vector $\xi$ is a collection of $N$ scenarios in dimension $p=2$ or $p=3$. In general, even when both the constraint and the objective are convex in the decision variable, the feasible region of a CCP is nonconvex, turning it into a difficult problem. However, under mild assumptions, many CCPs can be recast as big-$M$ mixed-integer convex programs (MICP). Unfortunately, the difficulty of these MICPs explodes with the number of scenarios, restricting the instances practically solvable in decent time. To cut down the effective number of scenarios considered in MICP reformulations and accelerate their solving, we propose and test presolve techniques based on computational geometry. Our techniques produce certificates to discard or select a priori some scenarios before solving a regular MICP. Moreover, the information aggregated during presolve leverages the possibility to strengthen big-$M$ constants. Our numerical experiments suggest that spending some time in presolve is more efficient than a direct solve for a class of probabilistic projection problems, including an interesting type of facility location problem.