# Optimizing a linear sum under a system of linear constraints, does this identify legit subproblems?

A legit subproblem of a problem is loosely defined as a smaller sized problem than the original input, but if you solve this smaller problem first, then the original input becomes easier to solve ("divide and conquer" approach).

I think I'm seeing that in this:

$$a_{1,1} X_1 + \dots + a_{1, n} X_n = b_1 \\ \vdots \\ a_{m, 1} X_1 + \dots + a_{m, n} X_n = b_m$$ are the constraint equations. And they constrain the solution to minimizing:

$$c_1X_1 + \dots + c_k X_k$$

Question. If there is a proper subset of the constraint equations such that all other equations can be written without any of the proper subset's variables, then it would be wise to solve that smaller problem first, right?

Additionally, this is a valid argument, since I just have to formalize it in terms of zero coefficients or $$0$$'s appearing everywhere in the matrix $$A = (a_{i,j})$$ at the appropriate columns, except for the rows of the proper set of equations; also mentioning free variables with respect to the remaining equations etc.

• In my particular problem, these subproblems occur pretty much all the time. And I wasn't able to prove whether they were valid subproblems until now. – BananaCats Author Aug 2 '19 at 13:19