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