5
$\begingroup$

I have decision variables $x_i$ and $y_j$, real positive variables.

I would like to minimize objective function \begin{aligned} \min \quad & \sum_{ij} x_iy_j \\ \end{aligned}

All constraints are linear and decoupled/separable in the sense that each constraint involves either only $x_i$ or only $y_j$. For example,

\begin{aligned} x_1 \leq x_2 \\ y_1 \leq y_2 \end{aligned}

are acceptable constraints, but

\begin{aligned} x_1 \leq y_1 \\ \end{aligned}

is not an acceptable constraint.

What is a good way of solving such problems?

$\endgroup$
6
  • 1
    $\begingroup$ First, please be aware that, strictly inequality constraints $\lt or \gt$ are not used in the optimization models. Second, you could try to use $x_1 \leq y_1 - \epsilon + Mz$ or $y_1 \leq x_1 - \epsilon + Mz$ with introducing an auxiliary binary variable $z$ in which $z = 1$ then both of the constraints are redundant. $\endgroup$
    – A.Omidi
    Feb 9 at 13:13
  • $\begingroup$ @A.Omidi Thanks. Replaced strict inequalities in the examples. I don't have them in the actual problem. $\endgroup$ Feb 9 at 15:45
  • $\begingroup$ What is the dimension (number of elements of x and y) of the problem? You could just throw it in Gurobi, which (attempts to ) solve bilinear problems to global optimality. Or CPLEX, which does the same provided the constraints are linear, which they are in your case. if you are content with local minimum, you could use any Quadratic Programming (QP) solver which attempts to solve non-convex QPs to local optimality. $\endgroup$ Feb 9 at 16:09
  • $\begingroup$ @MarkL.Stone A concern I have is that the solver may not fully make use of the "nice" properties of the problem. Actually, I don't even know if separability makes a big difference, it just feels like it should. IF there is an efficient way of solving such problems, I would like to get a name for it so I can look into it a little, and also I would like to know how I can get some solver to use it. Dimensionality is not fixed really. The more the better. 10000 of each of x and y would be a nice start :) $\endgroup$ Feb 9 at 17:13
  • 2
    $\begingroup$ Is your objective function maybe instead $\sum_{i,j} c_{i,j} x_i y_j$, with $c_{i,j}$ actually depending on both $i$ and $j$? $\endgroup$
    – RobPratt
    Feb 9 at 18:39

1 Answer 1

5
$\begingroup$

Let $X$ and $Y$ be the (polyhedral) sets of feasible values for $x$ and $y$ respectively. Your objective function $\sum_{i,j}x_i y_j$ equates to $$\left(\sum_i x_i\right) \left(\sum_j y_j\right).$$ So your problem is separable. You can just solve two LPs, $$\min_{x\in X}\sum_i x_i$$and $$\min_{y\in Y} \sum_j y_j,$$.

$\endgroup$
2
  • 2
    $\begingroup$ Whoops, I missed "positive variables", when I formulated my comments. I couldn't understand your answer until I re-read the question and noticed "positive variables". So yeah, what you did. $\endgroup$ Feb 9 at 17:23
  • $\begingroup$ Thank you. (I failed in correctly formulating the question: objective function was not supposed to be separable. I created a different question here: or.stackexchange.com/questions/7806/…) $\endgroup$ Feb 10 at 9:15

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.