# Characterization of Subset Sum via Linear Programming

I have a sample subset sum problem.

Given numbers $x_1, x_2... x_N$ and a target value to sum to $x_S$

Minimize $x_S - x_1y_1 - x_2y_2 - x_3y_3 ... x_Ny_N$

such that

0 <= $y_1$ <= 1

0 <= $y_2$ <= 1 ...

0 <= $y_N$ <= 1

$x_S - x_1y_1 - x_2y_2 - x_3y_3.... - x_ny_n >= 0$

$x_S - x_1y_1 - x_2y_2 - x_3y_3.... - x_ny_n <= 0$

The set of vertices of the polyhedron will have coordinates equal to the $x_i$ meaning that usual simplex should hit the required values... By adding the third and fourth inequalities the only things that remain are those edges which satisfy the required constraints (only solution edges/vertices are now present)

Now if there is a way to find a trivial solution (some combination of edges) if there exists an algorithm that lets you traverse the figure and find its vertices... those correspond to solution of the problem.

Is this a good approach? I can always cut out the last (4th) inequality and then use simplex to handle it.

-

I would instead try to maximize $\sum x_i y_i$ subject to $\sum x_i y_i \leq x_S$ and $y_i \in [0,1]$. (If you want the integer version, then $y_i \in \{0,1\}$.
@frogeyedpeas Simplex does not solve integer programming problems. Only linear programming problems. (And it does not run in polynomial time, but there are other algorithms that do.) In other words, if you don't restrict $y_i$ to be binary, it is a $P$-complete problem and we can solve it quite quickly. But if $y_i$ are required to be binary, the problem becomes $NP$-complete and you need approximation algorithms. – gt6989b Jun 18 '13 at 16:43