0
$\begingroup$

I am not sure if this is the right place to ask this question, please point me to the correct forum if I posted in a wrong place.

I have an optimization problem like this

Max x2 - x1
st  x1x2 <= 0
    x1^2 + x2^2 <= 9
    x1 and x2 are integers

What can I do to transform this problem into a convex optimization problem (the 1st constraint)? Or to a linear Integer programming problem? Because I only know algorithms for solving problems in those two categories. Please help.

Edit: My intention was to know if there are any common ways to transform the 1st constraint into some convex constraints. The domain of the original problem is huge and it has 10s of dimensions that you cannot draw the functions to get the answer. Lets say the problem look like this (please forgive me, i don't know how to use Latex ...)

Min sum(yi)
st  sum on j(wij) <= cyi for all i in N
    sum on i(xij) = 1 for all j in N
    wij = wjxij for all i, j in N
    Lij = Ljxij for all i, j in N
    Dij = Lij + wij for all i, j in N
    (Lij - Dik)(Lik - Dij) <= 0 for all i, j, k in N
    Aj <= Lj for all j in N
    Lj <= Aj + Qj for all j in N
    xij = 0 or 1 for all i, j in N
    yi = 0 or 1 for all i in N
    Wj, Lj, Qj and c are constant
    N = 10000

Other than using implicit enumeration, what can i do? The only constraint that is not convex is this one

(Lij - Dik)(Lik - Dij) <= 0 for all i, j, k in N
$\endgroup$
3
  • $\begingroup$ Using symmetry you could assume $x_2 \ge 0$ and $x_1 \le 0$. That could replace the 1st constraint. $\endgroup$
    – user251257
    Sep 13, 2019 at 18:40
  • $\begingroup$ Check this to learn more about posting questions. $\endgroup$
    – IamKnull
    Sep 13, 2019 at 18:47
  • 1
    $\begingroup$ This question was asked and answered on MathOverflow here. $\endgroup$
    – RobPratt
    Sep 13, 2019 at 23:23

2 Answers 2

Reset to default
2
$\begingroup$

Perhaps I’m missing something, but this optimization problem should be relatively quick to solve because you only have a finite number of cases to check. There are only finitely many pairs of integers $(x_1,x_2)$ satisfying $x_1^2+x_2^2\le 9$, and they are all the elements of the set $\{-3,-2,-1,0,1,2,3\}^2$. Combined with the constraint that $x_1x_2\le 0$, and taking advantage of symmetry, this leaves a total of $16$ cases to check, which you can easily do by hand.

$\endgroup$
2
  • $\begingroup$ Let me edit my question to include the original problem, it is a more complicated problem with hundreds of constraints, my original intention was to know if there are ways to transform the first constraint into some series of convex constraints. $\endgroup$
    – Aaron_Geng
    Sep 13, 2019 at 18:52
  • $\begingroup$ I have updated the question, the original problem is actually a two stage stochastic programming problem, but I made everything static for simplicity, thank you very much $\endgroup$
    – Aaron_Geng
    Sep 13, 2019 at 19:12
0
$\begingroup$

Isn't the answer simply 4 with $x_1=2$ and $x_2=-2$? The second constraint imposes that the two numbers should have opposite signs and due to the structure of the maximization problem, $x_1\geq 0$ and $x_2\leq 0$. In this case, one needs to check the objective function for the pairs $(3,0)$ and $(2,-2)$ for $(x_1,x_2)$ (the rest of the cases is dominated by these pairs) and among the two $(2,-2)$ gives a higher value for the objective function.

$\endgroup$
1
  • $\begingroup$ Sorry, I didn't intent to confuse you, The question is edited, thanks $\endgroup$
    – Aaron_Geng
    Sep 13, 2019 at 19:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .