论文标题
稀疏近似的MIP和设置覆盖方法
MIP and Set Covering approaches for Sparse Approximation
论文作者
论文摘要
稀疏近似问题要求找到一个解决方案$ x $，以便$ || y -hx || <α$，对于给定的规范$ || \ cdot || $，最小化支持$ || x || _0的大小：= \＃\ {j \ | \ | \ x_j \ neq 0 \} $。我们提出了用于此问题的混合整数编程（MIP）配方的有效不平等现象，我们表明这些家庭足以描述可行的支持集。这导致了该问题作为整数编程（IP）模型的重新重新制定，而整数编程模型又代表了最低设置涵盖公式的设置，从而产生了许多有效不平等的家庭，这些家庭可用于加强模型。我们提出了算法来解决稀疏近似问题，包括用于MIP的分支\＆切割，这是一种两阶段算法，以解决覆盖IP的集合以及基于局部分支类型约束的启发式方法。在计算实验中比较了这些方法，以测试其实际潜力。
The Sparse Approximation problem asks to find a solution $x$ such that $||y - Hx|| < α$, for a given norm $||\cdot||$, minimizing the size of the support $||x||_0 := \#\{j \ |\ x_j \neq 0 \}$. We present valid inequalities for Mixed Integer Programming (MIP) formulations for this problem and we show that these families are sufficient to describe the set of feasible supports. This leads to a reformulation of the problem as an Integer Programming (IP) model which in turn represents a Minimum Set Covering formulation, thus yielding many families of valid inequalities which may be used to strengthen the models up. We propose algorithms to solve sparse approximation problems including a branch \& cut for the MIP, a two-stages algorithm to tackle the set covering IP and a heuristic approach based on Local Branching type constraints. These methods are compared in a computational experimentation with the goal of testing their practical potential.
