Here we prove by structural induction that (a) every result returned by Algorithm 1 is a solution of (4) and (b) the set of solutions returned by the algorithm contains all the optimal solutions. We note that the algorithm is designed to discard infeasible vectors and those solutions that are clearly suboptimal at each recursion to improve performance. The latter is based on positiveness of the elements of
as explained below.The algorithm generates a binary tree. Each node represents a problem of size
and
, and branches into two subproblems of size
and
. The former subproblem is a result of setting
and the latter a result of setting
. A leaf is reached when we need to solve
. Without loss of generality let us assume that the variable to be examined is the first variable (
) which is followed by
variables (
to
) that are constrained to
,
variables (
to
) that are constrained but not to
, and finally
unconstrained variables
to
. This can be easily accomplished by rearranging the columns of
.For
, it is clear that the only optimal solution to
is
which is returned by the algorithm. Hence, the
minimal structure of the algorithm returns the optimal solution and our claim is true for
. The induction hypothesis is that the two subproblems
and
have only discarded infeasible vectors and some suboptimal solutions. We need to prove that the same statement applies to the parent problem
.We first look at the left branch where
. According to the construction of the algorithm, any solution such as
of length
provided by the left branch
is appended by the parent problem
to form
where the head variable
is set to one, variables constrained to
are set to zero and all unconstrained variables are set to one. We first prove that
is indeed a solution and then show that changing any element of
results in either an infeasible or a clearly suboptimal
. We use Definitions 6–8.(i)For
we write the condition
as a weighted sum of columns of
. That is,
, where
is a submatrix of
of size
, which is input to
, and according to the induction hypothesis
. But since no variable in
is constrained to
, no column in
and
can have ones in the same row position. Therefore,
.(ii)Since
to
are unconstrained, no column
to
can have ones in the same row position. Hence,
.(iii)Using similar arguments, we can assert that no column in
or
can have ones in the same row positions as
to
do. Therefore,
and
is a solution.(iv)We now argue that variables
to
cannot be anything other than zero. This directly follows from the fact that
is constrained with
for
and hence, in any given solution they cannot be simultaneously one.(v)Since we have already found a solution
where the first and last
variables are one, we know that any other solution such as
with one or more zeros in these positions becomes suboptimal and can be discarded. That is,
due to positiveness of elements of
.(vi)Finally, according to induction hypothesis, we know that
cannot be changed into anything other than what
provides without making it either infeasible or suboptimal. In summary, for each solution
provided by the left branch
, the constructed vector
is the only solution that is not trivially suboptimal.Now we look at the right branch where
. According to the construction of the algorithm, a given solution such as
of length
provided by the right branch
is appended by the parent problem
to form
where the head variable is set to zero and all unconstrained variables are set to one. We need to show that for a given
this is indeed a solution. We then show that changing any element of
can only result in an infeasible vector, a clearly suboptimal solution, or a duplicate solution already provided by the left branch and hence, can be discarded. We use Definitions 6–8.(i)We write
as
, where
is a submatrix of
of size
, which is input to
, and according to the induction hypothesis
. Similar to the arguments for the left branch, we can assert that no column
to
corresponding to unconstrained variables can have ones in the same row position. Hence,
. Furthermore, that no column in
can have ones in the same row positions as
to
. Therefore,
and
is a solution.(ii)Since we have already found a solution
where the last
variables are one, we know that any other solution such as
with one or more zeros in these positions becomes suboptimal and can be discarded.(iii)Finally, we show that any vector of the form
with a one in the first variable is either infeasible or is already constructed based on solutions from the left branch and hence, need not be considered twice. We consider two possibilities for
. If
for any
, then we have already shown in the analysis of the left branch that
is infeasible because
and
are constrained to each other. If none of
to
are one, then
will be of the form
for some
. But,
has to be a solution of
. Hence, considering vectors of the form
does not lead to any new solution.In summary, for each solution
provided by the right branch
, the constructed vector
is the only novel solution that is not trivially suboptimal. By combining the arguments of left and right branch, the induction claim is proven.