# 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.

-

Not sure this is helpful if no exact solution exists. In your case, the solver will report the problem is infeasible. Also, you would be much better off specifying an equality constraint instead of two inequality constraints, but the solver should be robust to handle these in preprocessing automatically.

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\}$.

Here in case the equality cannot be achieved, you will at least report the closest available solution.

It also sounds like this is a flavor of the classic Knapsack problem (my formulation makes it apparent). The usefullness of having a standard problem is that there are available heuristics and approximation algorithms...

-
But if a solution exists then does it find it in poly time (since simplex runs in polytime) –  frogeyedpeas Jun 18 '13 at 16:40
@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
I just realized there may be non integral vertices –  frogeyedpeas Jun 18 '13 at 17:00