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?

Improve this question
$\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
    Commented Feb 9, 2022 at 13:13
  • $\begingroup$ @A.Omidi Thanks. Replaced strict inequalities in the examples. I don't have them in the actual problem. $\endgroup$
    – Displayed_Name
    Commented Feb 9, 2022 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$
    – Mark L. Stone
    Commented Feb 9, 2022 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$
    – Displayed_Name
    Commented Feb 9, 2022 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
    Commented Feb 9, 2022 at 18:39

1 Answer 1

Reset to default
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,$$.

Improve this answer
$\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$
    – Mark L. Stone
    Commented Feb 9, 2022 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$
    – Displayed_Name
    Commented Feb 10, 2022 at 9:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.