Skip to main content
added 128 characters in body
Source Link
RobPratt
  • 5.4k
  • 1
  • 15
  • 25

Given $n \times n$ matrix $M$, you want to find $A,B,C \subset \{1,\dots,n\}$ to maximize $$\sum\limits_{i \in A, j \in C} m_{ij} - \sum\limits_{i \in B, j \in C} m_{ij}$$ subject to $A < B < C$ and $|A|=|B|=|C|$.

Introduce binary decision variables $a_i, b_i, c_i \in \{0,1\}$ to indicate whether $i\in A, i\in B, i\in C$, respectively. Introduce decision variable $d$ to represent the common cardinality. The problem is to maximize $$\sum_{i=1}^n \sum_{j=1}^n m_{ij} (a_i c_j - b_i c_j)$$ subject to linear constraints \begin{align} a_i + b_j &\le 1 &&\text{for $i \ge j$} \\ b_i + c_j &\le 1 &&\text{for $i \ge j$} \\ \sum_i a_i &= d \\ \sum_i b_i &= d \\ \sum_i c_i &= d \\ \end{align} This is an integer quadratic programming (IQP) problem, but you can linearize by introducing binary variables $u_{ij}$ and $v_{ij}$ to replace the products $a_i c_j$ and $b_i c_j$, respectively. The resulting integer linear programming (ILP) problem is to maximize $$\sum_{i=1}^n \sum_{j=1}^n m_{ij} (u_{ij} - v_{ij})$$ subject to linear constraints \begin{align} a_i + b_j &\le 1 &&\text{for $i \ge j$} \\ b_i + c_j &\le 1 &&\text{for $i \ge j$} \\ \sum_i a_i &= d \\ \sum_i b_i &= d \\ \sum_i c_i &= d \\ a_i &\ge u_{ij} &&\text{for all $i$ and $j$}\\ c_j &\ge u_{ij} &&\text{for all $i$ and $j$}\\ a_i + c_j - 1 &\le u_{ij} &&\text{for all $i$ and $j$}\\ b_i &\ge v_{ij} &&\text{for all $i$ and $j$}\\ c_j &\ge v_{ij} &&\text{for all $i$ and $j$}\\ b_i + c_j - 1 &\le v_{ij} &&\text{for all $i$ and $j$} \end{align}\begin{align} a_i + b_j &\le 1 &&\text{for $i \ge j$} \\ b_i + c_j &\le 1 &&\text{for $i \ge j$} \\ \sum_i a_i &= d \\ \sum_i b_i &= d \\ \sum_i c_i &= d \\ a_i &\ge u_{ij} &&\text{for all $i$ and $j$} \tag1\label1 \\ c_j &\ge u_{ij} &&\text{for all $i$ and $j$} \tag2\label2 \\ a_i + c_j - 1 &\le u_{ij} &&\text{for all $i$ and $j$}\\ b_i &\ge v_{ij} &&\text{for all $i$ and $j$}\\ c_j &\ge v_{ij} &&\text{for all $i$ and $j$}\\ b_i + c_j - 1 &\le v_{ij} &&\text{for all $i$ and $j$} \tag3\label3 \end{align} For nonnegative $m_{ij}$, you can omit constraints \eqref{1}, \eqref{2}, and \eqref{3}.

Given $n \times n$ matrix $M$, you want to find $A,B,C \subset \{1,\dots,n\}$ to maximize $$\sum\limits_{i \in A, j \in C} m_{ij} - \sum\limits_{i \in B, j \in C} m_{ij}$$ subject to $A < B < C$ and $|A|=|B|=|C|$.

Introduce binary decision variables $a_i, b_i, c_i \in \{0,1\}$ to indicate whether $i\in A, i\in B, i\in C$, respectively. Introduce decision variable $d$ to represent the common cardinality. The problem is to maximize $$\sum_{i=1}^n \sum_{j=1}^n m_{ij} (a_i c_j - b_i c_j)$$ subject to linear constraints \begin{align} a_i + b_j &\le 1 &&\text{for $i \ge j$} \\ b_i + c_j &\le 1 &&\text{for $i \ge j$} \\ \sum_i a_i &= d \\ \sum_i b_i &= d \\ \sum_i c_i &= d \\ \end{align} This is an integer quadratic programming (IQP) problem, but you can linearize by introducing binary variables $u_{ij}$ and $v_{ij}$ to replace the products $a_i c_j$ and $b_i c_j$, respectively. The resulting integer linear programming (ILP) problem is to maximize $$\sum_{i=1}^n \sum_{j=1}^n m_{ij} (u_{ij} - v_{ij})$$ subject to linear constraints \begin{align} a_i + b_j &\le 1 &&\text{for $i \ge j$} \\ b_i + c_j &\le 1 &&\text{for $i \ge j$} \\ \sum_i a_i &= d \\ \sum_i b_i &= d \\ \sum_i c_i &= d \\ a_i &\ge u_{ij} &&\text{for all $i$ and $j$}\\ c_j &\ge u_{ij} &&\text{for all $i$ and $j$}\\ a_i + c_j - 1 &\le u_{ij} &&\text{for all $i$ and $j$}\\ b_i &\ge v_{ij} &&\text{for all $i$ and $j$}\\ c_j &\ge v_{ij} &&\text{for all $i$ and $j$}\\ b_i + c_j - 1 &\le v_{ij} &&\text{for all $i$ and $j$} \end{align}

Given $n \times n$ matrix $M$, you want to find $A,B,C \subset \{1,\dots,n\}$ to maximize $$\sum\limits_{i \in A, j \in C} m_{ij} - \sum\limits_{i \in B, j \in C} m_{ij}$$ subject to $A < B < C$ and $|A|=|B|=|C|$.

Introduce binary decision variables $a_i, b_i, c_i \in \{0,1\}$ to indicate whether $i\in A, i\in B, i\in C$, respectively. Introduce decision variable $d$ to represent the common cardinality. The problem is to maximize $$\sum_{i=1}^n \sum_{j=1}^n m_{ij} (a_i c_j - b_i c_j)$$ subject to linear constraints \begin{align} a_i + b_j &\le 1 &&\text{for $i \ge j$} \\ b_i + c_j &\le 1 &&\text{for $i \ge j$} \\ \sum_i a_i &= d \\ \sum_i b_i &= d \\ \sum_i c_i &= d \\ \end{align} This is an integer quadratic programming (IQP) problem, but you can linearize by introducing binary variables $u_{ij}$ and $v_{ij}$ to replace the products $a_i c_j$ and $b_i c_j$, respectively. The resulting integer linear programming (ILP) problem is to maximize $$\sum_{i=1}^n \sum_{j=1}^n m_{ij} (u_{ij} - v_{ij})$$ subject to linear constraints \begin{align} a_i + b_j &\le 1 &&\text{for $i \ge j$} \\ b_i + c_j &\le 1 &&\text{for $i \ge j$} \\ \sum_i a_i &= d \\ \sum_i b_i &= d \\ \sum_i c_i &= d \\ a_i &\ge u_{ij} &&\text{for all $i$ and $j$} \tag1\label1 \\ c_j &\ge u_{ij} &&\text{for all $i$ and $j$} \tag2\label2 \\ a_i + c_j - 1 &\le u_{ij} &&\text{for all $i$ and $j$}\\ b_i &\ge v_{ij} &&\text{for all $i$ and $j$}\\ c_j &\ge v_{ij} &&\text{for all $i$ and $j$}\\ b_i + c_j - 1 &\le v_{ij} &&\text{for all $i$ and $j$} \tag3\label3 \end{align} For nonnegative $m_{ij}$, you can omit constraints \eqref{1}, \eqref{2}, and \eqref{3}.

Source Link
RobPratt
  • 5.4k
  • 1
  • 15
  • 25

Given $n \times n$ matrix $M$, you want to find $A,B,C \subset \{1,\dots,n\}$ to maximize $$\sum\limits_{i \in A, j \in C} m_{ij} - \sum\limits_{i \in B, j \in C} m_{ij}$$ subject to $A < B < C$ and $|A|=|B|=|C|$.

Introduce binary decision variables $a_i, b_i, c_i \in \{0,1\}$ to indicate whether $i\in A, i\in B, i\in C$, respectively. Introduce decision variable $d$ to represent the common cardinality. The problem is to maximize $$\sum_{i=1}^n \sum_{j=1}^n m_{ij} (a_i c_j - b_i c_j)$$ subject to linear constraints \begin{align} a_i + b_j &\le 1 &&\text{for $i \ge j$} \\ b_i + c_j &\le 1 &&\text{for $i \ge j$} \\ \sum_i a_i &= d \\ \sum_i b_i &= d \\ \sum_i c_i &= d \\ \end{align} This is an integer quadratic programming (IQP) problem, but you can linearize by introducing binary variables $u_{ij}$ and $v_{ij}$ to replace the products $a_i c_j$ and $b_i c_j$, respectively. The resulting integer linear programming (ILP) problem is to maximize $$\sum_{i=1}^n \sum_{j=1}^n m_{ij} (u_{ij} - v_{ij})$$ subject to linear constraints \begin{align} a_i + b_j &\le 1 &&\text{for $i \ge j$} \\ b_i + c_j &\le 1 &&\text{for $i \ge j$} \\ \sum_i a_i &= d \\ \sum_i b_i &= d \\ \sum_i c_i &= d \\ a_i &\ge u_{ij} &&\text{for all $i$ and $j$}\\ c_j &\ge u_{ij} &&\text{for all $i$ and $j$}\\ a_i + c_j - 1 &\le u_{ij} &&\text{for all $i$ and $j$}\\ b_i &\ge v_{ij} &&\text{for all $i$ and $j$}\\ c_j &\ge v_{ij} &&\text{for all $i$ and $j$}\\ b_i + c_j - 1 &\le v_{ij} &&\text{for all $i$ and $j$} \end{align}