5

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?

RobPratt
  • 32,006
  • 1
  • 44
  • 84
Displayed_Name
  • 135
  • 4
  • 1
    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. – A.Omidi Feb 09 '22 at 13:13
  • @A.Omidi Thanks. Replaced strict inequalities in the examples. I don't have them in the actual problem. – Displayed_Name Feb 09 '22 at 15:45
  • 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. – Mark L. Stone Feb 09 '22 at 16:09
  • @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 :) – Displayed_Name Feb 09 '22 at 17:13
  • Never mind my previous comment. I missed "positive variables". So go with @prubin's answer. – Mark L. Stone Feb 09 '22 at 17:19
  • 2
    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$? – RobPratt Feb 09 '22 at 18:39

1 Answers1

5

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,$$.

prubin
  • 39,078
  • 3
  • 37
  • 104
  • 2
    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. – Mark L. Stone Feb 09 '22 at 17:23
  • Thank you. (I failed in correctly formulating the question: objective function was not supposed to be separable. I created a different question here: https://or.stackexchange.com/questions/7806/how-to-handle-a-non-separable-bilinear-objective-function-in-the-special-case-of) – Displayed_Name Feb 10 '22 at 09:15