[Math] Characterization of Subset Sum via Linear Programming

Question

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.

Answer 1

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