1

I would like to linearize a product, for example $a*b$. if I solve my solution in log space, I can formulate it as $a+b$ and when my final output is returned, remember to convert back to original space by finding $e^a, e^b$.

Now, further suppose that I have integer constraints for binary assignment, where $a,b$ fall in the set {0,1}. By using $log_2{x}$ I can use set{1,2} rather than set{0,1}. This is because $log_2{1}=0$ and $log_2{2}=1$. So now, if I revisit the original problem of $a*b$ and I want to find if both $a,b$ are true, I can solve this in log space as $z= a+b$ remembering to subtract one from each variable to convert back to binary variables in the original space, where $z$ would indicate if both $a,b$ were true else False.

Often times, in MILP problems there will be multiple objective terms, which I believe that the MILP solver anticipates adding together. Consider my objective terms, in original space as $a*b + x*y$. Taking the logarithm, $log_2{(a*b + x*y)}$. However, I do not believe that this can be simplified any further. Because the log cannot be removed from the equation, I cannot so eloquently expunge it from the solver's logic. And MILP solvers are not equipped to evaluate log expressions.

The first workaround that comes to mind is using a geometric mean rather than an arithmetic mean.

To give an example, say that I had two objective terms in my original space, $a*b$ and $x*y*$. The arithmetic mean of these objective terms is $(a*b + x*y)/2$.

However, using a geometric mean, there are two formulations:

First, $\sqrt[\leftroot{-2}\uproot{2}2]{a*b*x*y}$. And second, $(log_2{a} + log_2{b} + log_2{x} + log_2{y})/2$.

I believe that this second formulation would enable me to find the geometric mean of my objective terms by treating inputs as logarithms and remembering to convert back to the original space post solution using exponentiation.

Any thoughts or experience here?

jbuddy_13
  • 551
  • 1
  • 8
  • 1
    If $a,b,x,y$ are binary, there are better linearizations of $ab+xy$. – RobPratt Jan 14 '23 at 17:04
  • A great question! This was just a toy example, some variables will be binary, however, others not depicted will continuous – jbuddy_13 Jan 14 '23 at 17:06
  • Are you familiar with Mixed-integer geometric programming? See section 9.2 of "A Tutorial on Geometric Programming" by S. Boyd, S.-J. Kim, L. Vandenberghe, and A. Hassibi https://web.stanford.edu/~boyd/papers/gp_tutorial.html " – Mark L. Stone Jan 14 '23 at 20:10

1 Answers1

1

If solver (and most solver can) handle log in constraints, I'd
$z_1 = \log_2 a + \log_2 b $
$ z_2 = \log_2 x + \log_2 y$

Obj = $z_1+z_2 $

Or

$x= e^{u_x} ; y= e^{u_y}$
Obj = $e^{u_1+u_2} + e^{u_a+u_b} $

Using geo mean, it may be vastly different from arithmetic mean. While log of a geometric mean is an addition and will be convex, also optimal point for log equivalent remains the same as original function but using geometric mean (nonconvex) as a function may give different optimal point than the original convex arithmetic mean.

OK found a close approximation of what OP is seeking here. It uses separable programming.

Sutanu Majumdar
  • 3,461
  • 1
  • 2
  • 11
  • A couple thoughts: First, I hadn't planned on supplying log_2{x} to the solver, at all. Rather, I had planned on correcting for it post-solution. And second, how would you extract the true variable values (not in log space) from the solution? – jbuddy_13 Jan 14 '23 at 17:08
  • Btw the solver that I will be using is likely SCIP – jbuddy_13 Jan 14 '23 at 17:13
  • Also, if I had two objectives of varying lengths such as O1: $ab$ and O2: $wxyz$ then the answer you've provided would be biased towards the second objective. I believe that using a geometric mean would curb this behavior. In fact, geometric mean will be biased toward the lowest value. For example, $geometricMean(1, 100)=10$ whereas $arithmeticMean(1,100)=50.5$. There's room for argument on which is better. But the geometric mean of objectives will not allow for the excellence on one objective to overpower weakness on another, which, depending on use case could, be beneficial. – jbuddy_13 Jan 14 '23 at 17:48
  • 1
    Check the new link in the edited answer. It may be helpful. – Sutanu Majumdar Jan 14 '23 at 18:07
  • Saw the link, will dig into it. Circling back to your answer, so rather than taking the geometric mean, you would recommend just summing all terms, and if there are more terms in one objective than another, that's still potentially better than the geometric mean? – jbuddy_13 Jan 14 '23 at 20:01
  • 1
    I'd check the optimal solution by adding the terms because geometric mean is essentially a different function. But if your objective is driven by business/research need to multiply then ofcourse go ahead. – Sutanu Majumdar Jan 14 '23 at 20:05