This work describes PUSH, a primal heuristic combining Feasibility Pump and
Shifting. The main idea is to replace the rounding phase of the Feasibility
Pump with a suitable adaptation of the Shifting and other rounding heuristics.
The algorithm presents different strategies, depending on the nature of the
partial rounding obtained. In particular, we distinguish when the partial
solution is feasible, infeasible with potential candidates, and infeasible
without candidates. We used a threshold to indicate the percentage of variables
to round with our algorithm and which other to round to the nearest integer.
Most importantly, our algorithm tackles directly equality constraints without
duplicating rows. We select the parameters of our algorithm on the 19 instances
provided for the Mip Competition 2022. Finally, we compared our approach to
other start heuristics, like Simple Rounding, Rounding, Shifting, and
Feasibility Pump on the first 800 MIPLIB2017 instances ordered by the number of
non-zeros.

本文提出一种名为 PUSH 的原始启发式算法，结合可行性泵和 Shifting 方法用于精确整数规划问题，并基于新的算法来处理相等的约束条件，同时在 MIPLIB2017 数据集上与其他启发式算法进行了比较。

基于可行性泵和移位的原始启发式算法: PUSH

PUSH: a primal heuristic based on Feasibility PUmp and SHifting

We present a solver for Mixed Integer Programs (MIP) developed for the MIP
competition 2022. Given the 10 minutes bound on the computational time
established by the rules of the competition, our method focuses on finding a
feasible solution and improves it through a Branch-and-Bound algorithm. Another
rule of the competition allows the use of up to 8 threads. Each thread is given
a different primal heuristic, which has been tuned by hyper-parameters, to find
a feasible solution. In every thread, once a feasible solution is found, we
stop and we use a Branch-and-Bound method, embedded with local search
heuristics, to ameliorate the incumbent solution. The three variants of the
Diving heuristic that we implemented manage to find a feasible solution for 10
instances of the training data set. These heuristics are the best performing
among the heuristics that we implemented. Our Branch-and-Bound algorithm is
effective on a small portion of the training data set, and it manages to find
an incumbent feasible solution for an instance that we could not solve with the
Diving heuristics. Overall, our combined methods, when implemented with
extensive computational power, can solve 11 of the 19 problems of the training
data set within the time limit. Our submission to the MIP competition was
awarded the "Outstanding Student Submission" honorable mention.

在 MIP 2022 竞赛的限时 10 分钟内，我们的混合整数规划求解器，利用分支定界算法和多线程的原始启发式方法，表现出优异的表现，特别是在使用 Diving heuristic 的情况下，成功地解决了 10 个数据集实例，这使得我们的竞赛作品获得了 “优秀学生投稿” 荣誉提名。

基于启发式增强分支定界算法的 MILP 求解器的设计与实现

Design and Implementation of an Heuristic-Enhanced Branch-and-Bound Solver for MILP

We present a scalable combinatorial algorithm for globally optimizing over
the space of geometrically consistent mappings between 3D shapes. We use the
mathematically elegant formalism proposed by Windheuser et al. (ICCV 2011)
where 3D shape matching was formulated as an integer linear program over the
space of orientation-preserving diffeomorphisms. Until now, the resulting
formulation had limited practical applicability due to its complicated
constraint structure and its large size. We propose a novel primal heuristic
coupled with a Lagrange dual problem that is several orders of magnitudes
faster compared to previous solvers. This allows us to handle shapes with
substantially more triangles than previously solvable. We demonstrate
compelling results on diverse datasets, and, even showcase that we can address
the challenging setting of matching two partial shapes without availability of
complete shapes. Our code is publicly available at
this http URL .

提出了可扩展的组合算法，用于全局优化 3D 形状之间具有几何一致性的映射空间，通过整数线性规划公式和原始启发式方法以及拉格朗日对偶问题相结合，实现了比以前更快、更高效的解决方法，成功地匹配了多个形状。