The weekly SILO Seminar Series is made possible through the generous support of the 3M Company and its Advanced Technology Group


with additional support from the Analytics Group of the Northwestern Mutual Life Insurance Company

Northwestern Mutual

Chance-constrained Packing Problems | Suppressing pseudocodewords by penalizing the objective of LP decoding

Yongjia Song | Xishuo Liu, CS Grad Student | ECE Grad Student

Date and Time: Feb 26, 2013 (12:30 PM)
Location: Orchard room (3280) at the Wisconsin Institute for Discovery Building


Song's abstract
We consider a probabilistic version of classical 0-1 packing problem, where we have a set of
items with random weights and a random knapsack capacity. The objective is to choose a set of
items that maximizes profit while ensuring the probability that the knapsack constraint is satisfi ed
is higher than a given risk tolerance. We introduce a simple decomposition algorithm based on a
probabilistic extension of cover inequalities to solve a sample average approximation (SAA) of this
problem. These inequalities ensure an exact formulation by cutting o ff all infeasible solutions, but,
similar to deterministic cover inequalities, these inequalities are weak. We propose a probabilistic
sequential lifting procedure to strengthen these inequalities, leveraging successful computational
strategies for the deterministic knapsack problem. Exact lifting is hard, but we obtain an e ffective
upper bound for the lifting problem using a scenario decomposition approach. Additional valid
inequalities are proposed to further strengthen the bounds. A key advantage of our algorithm
is that the number of branch-and-bound nodes searched is nearly independent of the number of
scenarios used in the SAA, which is in stark contrast to formulations that introduce binary variables
for choosing which scenario should be enforced to satisfy the chance constraint. Computational
results will be presented for instances of chance-constrained single and multi-dimensional knapsack
problems and set packing problems.

Xishuo's abstract
Linear programming (LP) decoding for low density parity check (LDPC) codes proposed by Feldman et al. has attracted considerable attention in recent years. Despite having theoretical guarantees in some regimes, at low SNRs LP decoding
is observed to have worse error performance than belief propagation (BP) decoding. In this work, we present a class of
decoding algorithm obtained by trying to solve a non-convex optimization problem using the alternating direction method of
multipliers (ADMM). This non-convex problem is constructed by adding a penalty term to the LP decoding objective.
The goal of the penalty term is to make “pseudocodewords”, which are the non-integer vertices of the LP relaxation to
which the LP decoder fails, more costly.
Based on this non-convex problem, we develop a reweighted LP decoding algorithm. We show that this reweighted LP has an improved theoretical recovery threshold compared to the original LP. In addition, simulations show that, in comparison to LP decoding, these two decoders both achieve significantly lower error rates and are not observed to have an “error floor”.