2
$\begingroup$

I have the following integer optimization problem \begin{align}\min&\quad\sum_ix_i\\ \text{s.t.}&\quad Ax \geq b\\ &\quad x \geq 0,\\ &\quad x \in \mathbb{Z}^n\end{align} where $b$ is a general vector of integers, $A$ is an $n$ by $n$ matrix where all entries are integers, but it has a very specific format: it is symmetric, every entry in the main diagonal is equal to the opposite of the sum of its row/column except when $i=j$, and if $i \neq j$, $A_{ij}$ is either 0 or 1. I will try to write that more formally.

\begin{align}A_{ij} &\in \{0, 1\}\quad\text{if}\quad i \neq j\\A_{ii} &= -\sum_{j=0,j \neq i}^{n-1}A_{ij} = -\sum_{j=0,j \neq i}^{n-1}A_{ji}\end{align}

Example of $A$: $$ \begin{bmatrix} -3 & 1 & 1 & 0 & 1\\ 1 & -3 & 1 & 1 & 0\\ 1 & 1 & -3 & 0 & 1\\ 0 & 1 & 0 & -2 & 1\\ 1 & 0 & 1 & 1 & -3\\ \end{bmatrix} $$ According to wikipedia, a general ILP is NP-hard. How do I:

  1. Prove this specific format is still NP-hard (probably by some reduction) or find that this is a special case that can be solved in polynomial time?

  2. Find if it's feasible without actually solving the optimization problem?

$\endgroup$
2
  • 1
    $\begingroup$ Welcome to OR Stack Exchange. The vector $b$ has no sign restrictions (can contain positive, negative and zero components)? $\endgroup$
    – prubin
    Dec 16 '21 at 21:06
  • $\begingroup$ hello. Yes, no sign restrictions $\endgroup$ Dec 16 '21 at 21:14
1
$\begingroup$

Here is a partial answer to the feasibility question. Let $e\in \mathbb{R}^n$ be a vector with all components equal to 1. $Ax\ge b \implies e'Ax \ge e'b.$ Since $e'A=0,$ if the problem is feasible you must have $e'b\le 0.$ So if the sum of the components of $b$ is positive, the problem is infeasible.

$\endgroup$
3
  • $\begingroup$ It's an interesting partial result. What do you think would be a natural next step to try? $\endgroup$ Dec 18 '21 at 3:29
  • $\begingroup$ Sorry, other than trying an IP solver or maybe a constraint solver, I don't see a natural way to proceed. $\endgroup$
    – prubin
    Dec 18 '21 at 21:51
  • $\begingroup$ There are various metaheuristics you can try to use to find a feasible solution, but I don't think they are better than using an IP or CP solver in this case. $\endgroup$
    – prubin
    Dec 18 '21 at 22:04

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.