Given $a_i, b_i, c_i, d_{ij}\in [0,1]$ for $i,j\in [n]$ and $i\neq j$ such that $\sum_{i\in [n]} a_i=1$.

I have the following bilinear program:

max $\sum_{i=1}^n (x_i-a_i)y_i$

st. (1) $b_i\leq x_i\leq c_i$ for each $i\in [n]$; and (2) $0\leq y_i\leq 1$ for each $i\in [n]$; and (3) $y_i-y_j\leq d_{ij}$ for $i,j\in [n], i\neq j$.

Write $f$ to be the solution. The question is to decide whether $f\geq \theta$ for some given rational $\theta\in [0,1]$.

This question is known to be in NP. But is it NP-hard?

Given $a_i, b_i, c_i, d_{ij}\in [0,1]$ for $i,j\in [n]$ and $i\neq j$ such that $\sum_{i\in [n]} a_i=1$ and $d_{ij}=d_{ji}$.

I have the following bilinear program:

max $\sum_{i=1}^n (x_i-a_i)y_i$

subject to

• $b_i\leq x_i\leq c_i$ for each $i\in [n]$;
• $0\leq y_i\leq 1$ for each $i\in [n]$;
• $y_i-y_j\leq d_{ij}$ for $i,j\in [n], i\neq j$;
• $\sum_{i\in [n]} x_i=1$

Write $f$ to be the solution. The question is to decide whether $f\geq \theta$ for some given rational $\theta\in [0,1]$.

This question is known to be in NP. But is it NP-hard?

Given $a_i, b_i, c_i, d_{ij}\in [0,1]$ for $i,j\in [n]$ and $i\neq j$ such that $\sum_{i\in [n]} a_i=1$.

I have the following bilinear program:

max $\sum_{i=1}^n (x_i-a_i)y_i$

st. $b_i\leq x_i\leq c_i$ for each $i\in [n]$; and $0\leq y_i\leq 1$ for each $i\in [n]$; and $y_i-y_j\leq d_{ij}$ for $i,j\in [n], i\neq j$.

Write $f$ to be the solution. The question is to decide whether $f\geq \theta$ for some given rational $\theta\in [0,1]$.

This question is known to be in NP. But is it NP-hard?

Given $a_i, b_i, c_i, d_{ij}\in [0,1]$ for $i,j\in [n]$ and $i\neq j$ such that $\sum_{i\in [n]} a_i=1$.

I have the following bilinear program:

max $\sum_{i=1}^n (x_i-a_i)y_i$

st. (1) $b_i\leq x_i\leq c_i$ for each $i\in [n]$; and (2) $0\leq y_i\leq 1$ for each $i\in [n]$; and (3) $y_i-y_j\leq d_{ij}$ for $i,j\in [n], i\neq j$.

Write $f$ to be the solution. The question is to decide whether $f\geq \theta$ for some given rational $\theta\in [0,1]$.

This question is known to be in NP. But is it NP-hard?