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?


Your objective is to minimize the convex function $-\sum_{i=1}^n(x_i−a_i)y_i$ subject to a system of linear constraints on the continuous variables $x_i$ and $y_i$.

Such convex minimization problems are polynomially solvable by so-called interior point methods; see for instance the book by Stephen Boyd and Lieven Vandenberghe: "Convex Optimization"; free pdf copy at: http://www.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf

  • 1
    $\begingroup$ I may be mistaken but are you sure that function is convex? I think $x\,y$ is neither concave nor convex over $[0,1]^2$. plot here $\endgroup$ – Neal Young Mar 12 '17 at 8:30

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.