I am an electrical engineer and currently I am learning some optimization for my research work. Note that this is a follow up question from my previous question at this link.
My project requires me to solve this problem and I am not sure about two things:
1/ Does case 1 easier than case 2 or does case 2 easier than case 1 ?
2/ For both cases, are there a special structure in the matrix $A$ that I can exploit ?
Expoit can mean anything, even if it means that I could solve it more faster or decompose this problem into other smaller subproblems since I have some distributed computing capability.
This is how case 1 looks:
$\begin{array}{l} \begin{array}{*{20}{c}} {{\rm{Min}}}&{{x_1} + {x_2} + {x_3} + {x_4} + {x_5} + {x_6}} \end{array}\\ \begin{array}{*{20}{c}} {}&{\underbrace {\left[ {\begin{array}{*{20}{c}} 1&1&0&{}&{}&{}\\ 0&1&1&{}&{}&{}\\ {}&{}&{}&1&1&0\\ {}&{}&{}&0&1&1 \end{array}} \right]}_A\left[ {\begin{array}{*{20}{c}} {{x_1}}\\ {{x_2}}\\ {{x_3}}\\ {{x_4}}\\ {{x_5}}\\ {{x_6}} \end{array}} \right] \ge \left[ {\begin{array}{*{20}{c}} a\\ b\\ c\\ d \end{array}} \right]}\\ {}&{a + c \le 1}\\ {}&{b + d \le 1}\\ {}&{{x_i},a,b,c,d \in \left\{ {0,1} \right\}} \end{array} \end{array}$
This is how case 2 looks:
$\begin{array}{l} \begin{array}{*{20}{c}} {{\rm{Min}}}&{{x_1} + {x_2} + {x_3} + {x_4} + {x_5} + {x_6}} \end{array}\\ \begin{array}{*{20}{c}} {}&{\underbrace {\left[ {\begin{array}{*{20}{c}} 1&1&0&{}&{}&{}\\ 0&1&1&{}&{}&{}\\ {}&{}&{}&1&1&0\\ {}&{}&{}&0&1&1 \end{array}} \right]}_A\left[ {\begin{array}{*{20}{c}} {{x_1}}\\ {{x_2}}\\ {{x_3}}\\ {{x_4}}\\ {{x_5}}\\ {{x_6}} \end{array}} \right] \ge \left[ {\begin{array}{*{20}{c}} a\\ b\\ c\\ d \end{array}} \right]}\\ {}&{a + c = 1}\\ {}&{b + d = 1}\\ {}&{{x_i},a,b,c,d \in \left\{ {0,1} \right\}} \end{array} \end{array}$
For more information, a larger scale of this problem with $x_7$, $x_8$ and $x_9$ would make the matrix $A$ into this form which is quite sparse:
$\underbrace {\left[ {\begin{array}{*{20}{c}} 1&1&0&{}&{}&{}&{}&{}&{}\\ 0&1&1&{}&{}&{}&{}&{}&{}\\ {}&{}&{}&1&1&0&{}&{}&{}\\ {}&{}&{}&0&1&1&{}&{}&{}\\ {}&{}&{}&{}&{}&{}&1&1&0\\ {}&{}&{}&{}&{}&{}&0&1&1 \end{array}} \right]}_A\left[ {\begin{array}{*{20}{c}} {{x_1}}\\ {{x_2}}\\ {{x_3}}\\ {{x_4}}\\ {{x_5}}\\ {{x_6}}\\ {{x_7}}\\ {{x_8}}\\ {{x_9}} \end{array}} \right] \ge \left[ {\begin{array}{*{20}{c}} a\\ b\\ c\\ d\\ e\\ f \end{array}} \right]$
The constraints on $a,b,c,d,e,f$ of the larger case would look like this
$\begin{array}{l} a + c + e \le 1\\ b + d + f \le 1 \end{array}$
Or this
$\begin{array}{l} a + c + e = 1\\ b + d + f = 1 \end{array}$
Would you kindly help me with this ?
Thank you for your enthusiam !
