0
$\begingroup$

There are two Mixed Integer Linear Programs. They have the same set of linear constraints constraints, but different objectives with variables $\mathbf{z}$ and $\mathbf{x}$.

The first objective is:

$\text{max}_{~\mathbf{z},\mathbf{x}} ~~~ \sum_{u=1}^{N_1} z_u$

where $z_i \in \{0,1\}$.

The second objective is:

$\text{max}_{~\mathbf{z},\mathbf{x}} ~~~ \sum_{u=1}^{N_1} z_u -\sum_{i=1}^{N_2} \sum_{j=1}^{N_3} \frac{1}{c_{i,j}}x_{i,j}$

where $z_i \in \{0,1\}$, $x_{i,j} \in \{0,1\}$, and values $c_{i,j}$ are given.

I came up with the second objective because I wanted to achieve the same optimal $\mathbf{z}^*$ in both programs, but to make optimal $\mathbf{x}^*$ sparser in the second program. I am sure that my approach in the second objective maximizes the number of non-zero elements in $\mathbf{z}$ and at the same time it minimizes the number of non-zero elements in $\mathbf{x}$. This happens due to the set of constraints that I have.

Question: Is there a standard mathematical tool/approach that I can use to prove my claim? I need to show that $\mathbf{z}^*$ is the same in both programs, and that $\mathbf{x}^*$ is sparser with the second objective, which are the things I wanted to achieve.

$\endgroup$
5
  • $\begingroup$ If $(x^*, z^*)$ is optimal in the second problem, it is also optimal in the first one. So you need to be careful saying $x^*$ is sparser than the solution to the first problem. If you have multiple optima in the first problem, $x^*$ may be sparser than the optimum you happened to get when you solved the first problem, but someone else solving the first problem might get $(x^*, z^*)$. $\endgroup$ – prubin Jan 20 '19 at 0:35
  • $\begingroup$ You are right when you say that the same optimal solutions ($\mathbf{x}^*$,$\mathbf{z}^*$) can be obtained in the first problem, but it is not guaranteed. In other words, sparsity of $\mathbf{x}^*$ can happen to be the same in both problems, but it is not guaranteed, and in general, sparsity of $\mathbf{x}^*$ in the second problem is greater or equal to that in the first problem. How can I mathematically prove that $\mathbf{z}^*$ is the same in both problems? $\endgroup$ – Veljko Jan 21 '19 at 4:07
  • $\begingroup$ Sorry, I should not have said $(x^*, z^*)$ is automatically optimal in the first problem (not true). What I meant was that it might be optimal in the first problem. $\endgroup$ – prubin Jan 22 '19 at 20:56
  • $\begingroup$ Is $x$ binary in the first problem. (You didn't say.) Also, when you say $z^*$ is the same, do you mean that for any optimal solution to the second problem the sum of the $z$ variables is the same as in an optimal solution to the first, or are you trying to prove that any optimal solutions of the first and second problems have exactly the same value for every $z_i$ (which requires that solutions be unique) or that for every optimal solution to either problem, there exists an optimal solution to the alternate problem with identical values for all $z_i$? $\endgroup$ – prubin Jan 22 '19 at 21:19
  • $\begingroup$ Vectors $\mathbf{z}$ and $\mathbf{x}$ are binary in both problems. The optimal $\mathbf{z}^*$ depends on how I set some of my constraints. I can set them in such way that I know there is unique solution $\mathbf{z}^*$, which is the same in both problems. Alternatively, I can set constraints such that there are multiple solutions, and they won't be necessarily the same in both problems. But, sum of $z_i$ variables is always the same in both problems, regardless of constraints. As I said, $\mathbf{x}^*$ can be sparser in the second problem, and this vector is never unique. $\endgroup$ – Veljko Jan 23 '19 at 4:01
0
$\begingroup$

If you can show that, in the second problem, $\sum_{i=1}^{N_2} \sum_{j=1}^{N_3}\frac{1}{c_{i,j}} x_{i,j} < 1$ for any possible (optimal) $x$, then I think you can show that $\sum_i z_i$ is the same for optimal solutions of the two problems. I'm not sure how you find a more general proof.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.