1
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ If $a,b,x,y$ are binary, there are better linearizations of $ab+xy$. $\endgroup$
    – RobPratt
    Jan 14 at 17:04
  • $\begingroup$ A great question! This was just a toy example, some variables will be binary, however, others not depicted will continuous $\endgroup$
    – jbuddy_13
    Jan 14 at 17:06
  • $\begingroup$ 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 web.stanford.edu/~boyd/papers/gp_tutorial.html " $\endgroup$
    – Mark L. Stone
    Jan 14 at 20:10

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – jbuddy_13
    Jan 14 at 17:08
  • $\begingroup$ Btw the solver that I will be using is likely SCIP $\endgroup$
    – jbuddy_13
    Jan 14 at 17:13
  • $\begingroup$ Also, if I had two objectives of varying lengths such as O1: $a*b$ and O2: $w*x*y*z$ 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. $\endgroup$
    – jbuddy_13
    Jan 14 at 17:48
  • 1
    $\begingroup$ Check the new link in the edited answer. It may be helpful. $\endgroup$
    – Sutanu
    Jan 14 at 18:07
  • 1
    $\begingroup$ 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. $\endgroup$
    – Sutanu
    Jan 14 at 20:05

Your Answer

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

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