2
$\begingroup$

It feels like this problem should be commonplace, but I don't know what it's called:


Minimize

$$ \sum_{i=1}^{n}a^{(i)}_{k_i} + \sum_{i=1}^n\sum_{j=i+1}^n b^{(ij)}_{k_i k_j} $$

with respect to integers $k_i \in [1 .. m]$ where $\forall i,j \in [1..n]$ $a^{(i)} \in \mathbf{R}^m$ and $b^{(ij)} \in \mathbf{R}^{m \times m}$


The problem thus involves finding the smallest of $m^n$ values (which can be a lot). I wonder if this can be done efficiently.

$\endgroup$
  • $\begingroup$ What is a real table? Is that the same as a real matrix? What is $a^i[x_i]$? What is $[x_i, x_j]$? What is $b^{ij}[x_i, x_j]$? Does this whole thing just amount to a quadratic? If so, then depending on the constraints, this is an Integer Quadratic Programming problem. $\endgroup$ – Mark L. Stone Aug 3 at 20:28
  • $\begingroup$ @MarkL.Stone Apologies! I hope the updated version is more readable. $\endgroup$ – MaxB Aug 3 at 21:04
  • $\begingroup$ What do the subindices mean? $\endgroup$ – nicoguaro Aug 4 at 4:07
  • $\begingroup$ @nicoguaro the subscripts are column/matrix elements, the superscripts denote completely separate matrices. $\endgroup$ – MaxB Aug 4 at 5:58
  • $\begingroup$ So, $n <m$ and the problem is about finding the columns/rows that minimize the sum? $\endgroup$ – nicoguaro Aug 4 at 13:04
3
$\begingroup$

This can be represented as an integer quadratic program, particularly with binary variables. Your problem (with slight tweaking of notation) is:

\begin{align} &\min_{k_i \in \lbrace 1, \cdots, m\rbrace} &&\sum_{i=1}^n \left(\hat{e}_{k_i}^T a^{(i)}\right) + \sum_{i=1}^n \sum_{j=i+1}^n \left(\hat{e}_{k_i}^T b^{(ij)} \hat{e}_{k_j}\right) \end{align}

where $a^{(i)} \in \mathbb{R}^m$ and $b^{(ij)} \in \mathbb{R}^{m \times m}$. We can reformulate this problem by defining the variables $x_{ij} \in \lbrace 0, 1 \rbrace$ such that in the original formulation, $k_{i} = j$ corresponds to $x_{ij} = 1$ and we have the further constraint that $\sum_{j=1}^m x_{ij} = 1$ for any $i$. Given this, we can reformulate the optimization problem as

\begin{align} &\min_{x_{ij} \in \lbrace 0, 1\rbrace} &&\sum_{i=1}^n \sum_{j=1}^m \left(\hat{e}_{j}^T a^{(i)}\right) x_{ij} + \sum_{i=1}^n \sum_{j=i+1}^n \sum_{l=1}^m \sum_{p=1}^m \left(\hat{e}_{l}^T b^{(ij)} \hat{e}_{p}\right) x_{il} x_{jp} \tag*{} \\ &\text{subject to} &&\sum_{j=1}^m x_{ij} = 1 \tag*{$\forall i$} \end{align}

As-is, this problem is going to be difficult to solve exactly in an efficient manner. You can consider approximating this by relaxing the constraint that $x_{ij} \in \lbrace 0, 1 \rbrace$ and instead using the interval constraint $x_{ij} \in [0, 1]$ and then perform some rounding approach. This might give you a problem that can be solved pretty efficiently, depending on how the quadratic coefficients work out. More specifically, you can take the above problem and represent its approximation in the form

\begin{align} &\min_{x_{ij} \in [0, 1]} &&\boldsymbol{c}^T \boldsymbol{x} + \frac{1}{2}\boldsymbol{x}^T Q \boldsymbol{x} \tag*{} \\ &\text{subject to} &&\sum_{j=1}^m x_{ij} = 1 \tag*{$\forall i$} \end{align}

where you stack all the $x_{ij}$ into the vector $\boldsymbol{x}$ in some manner. If $Q$ works out to be positive definite, this quadratic program could actually be solved pretty efficiently and then you can use some rounding strategy to get back an approximate integer solution. If an approximate solution is fine and you can show that $Q$ is positive definite, this is the way to go. Otherwise, you're going to be looking at an NP-Hard approach to solving this problem and so you'll be kind of stuck with a slow solution.

$\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.