tag:blogger.com,1999:blog-8781383461061929571.post4903320070580361848..comments2018-07-07T05:50:54.548-04:00Comments on OR in an OB World: Modeling Absolute ValuesPaul Rubinhttps://plus.google.com/111303285497934501993noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-8781383461061929571.post-47201036325298883962012-07-12T16:13:55.270-04:002012-07-12T16:13:55.270-04:00Convergence! :PConvergence! :Pmcghttps://www.blogger.com/profile/07835164854514314231noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-28091032640877299132012-07-12T14:33:32.016-04:002012-07-12T14:33:32.016-04:00Michael,
I agree with your points here (particula...Michael,<br /><br />I agree with your points here (particularly the last paragraph). I also suspect that there will be cases where the user can find a tighter formulation than whatever the modeling framework uses, just as (at least on my one test problem here) explicit introduction of binaries seems to beat CPLEX's built-in absolute value support. That said, I do think it would be best if, to the extent possible, a modeling language/API/system provided some support for absolute values, so that users who don't know how to model them (or don't have any problem-specific intuition better than whatever the modeling system's internal logic provides) can use absolute values without sweating over them.<br /><br />It would also help if there were some way to convey to users that absolute values come at a cost. I suspect some users think they can use absolute values willy-nilly and still have LP-like performance.Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-54912151446991015122012-07-12T12:13:15.750-04:002012-07-12T12:13:15.750-04:00Good point, Paul, I was thinking about just the co...Good point, Paul, I was thinking about just the convex case. Blast that tunnel vision!<br /><br />But in fact I've thought about the extension of my convex transformation ideas to non-convex cases, and other people have, too. For absolute values there are three cases to consider: (1) $|x|\leq y$, (2) $|x|\geq y$, (3) $|x|=y$. <br /><br />Other variations follow from these. For instance, $|x|+|y|=|z|$ is just an extension of case 3. For a nonlinear composition like $f(||x|) \leq y$, it depends on the monotonicity of $f$: it's case 1 if $f$ is nondecreasing, case 2 if $f$ is nonincreasing, and case 3 if $f$ is nonmontonic. If you don't know the monotonicity of $f$, stick with case 3.<br /><br />Yeah it gets complicated, but as a modeler---or a modeling framework---you can always truncate that complexity wherever you wish by defaulting to case 3 for any situation you don't handle.mcghttps://www.blogger.com/profile/07835164854514314231noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-52211279379069090842012-07-10T15:35:55.506-04:002012-07-10T15:35:55.506-04:00Your wish is my command (as long as no large hats ...Your wish is my command (as long as no large hats are involved). I added a fourth method above. It did better than either SOS method, not as well as explicit binaries.Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-43526611838532753742012-07-09T22:24:33.205-04:002012-07-09T22:24:33.205-04:00CPLEX does support modeling absolute value in the ...CPLEX does support modeling absolute value in the Concert API's and in OPL. I did a little experiment and it seems that CPLEX turns it into the binary model, but with indicator constraints. Paul - it would be interesting if you repeated your experiment using the IloCplexModeler.abs method from the Java API.Irv Lustighttp://sites.google.com/site/irvlustig/noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-58509374792824162012012-07-08T10:55:01.526-04:002012-07-08T10:55:01.526-04:00If you want to handle $|x|\le y$, you just need so...If you want to handle $|x|\le y$, you just need solver support for the epigraph. But what if you want to handle $|x|+|y|=|z|$? <br /><br />I'm looking at this from the (somewhat naive) user's perspective. Almost all users get that transcendental functions don't mix with LPs and MILPs. They're a bit less discerning about which quadratic functions are/are not supported, and where. My sense from various forums is that a lot of them think that because absolute value is common/low order/piecewise linear, they should be able to use it freely. <br /><br />If you say "no absolute values", they may internalize that; but if you say "you can use absolute values, but only in constraints that look like $|x|\le y$", they may not internalize the limitation ... and then your support people start buying aspirin in the big bottles. As the poet Paul Simon said, "a man hears what he wants to hear, and disregards the rest." (http://www.lyricsfreak.com/s/simon+and+garfunkel/the+boxer_20124664.html)Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-13518925529678482172012-07-07T15:47:32.160-04:002012-07-07T15:47:32.160-04:00A solver does not have to support the abs() functi...A solver does not have to support the abs() function, actually. It just has to support its epigraph, which is the set $|x|\leq z$. That's just a degenerate second-order cone. In fact, Gurobi now supports second-order-cone constraints, and I have successfully passed it absolute values in this way.<br /><br />Of course, nothing prevents Gurobi or other second-order solvers from reformulating this second-order-cone constraint into an equivalent set of linear constraints. Indeed, I would suspect that for performance reasons it _should_ do so. But it now has the freedom to implement it in whatever way is most efficient given the solver's internal design. Indeed, the answer could be model dependent: if the model has other binary or integer variables, for instance, it could choose an MILP formulation; otherwise, it could split the variables or use a formulation like Bo's.mcghttps://www.blogger.com/profile/07835164854514314231noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-77079719768004790882012-07-07T14:05:20.606-04:002012-07-07T14:05:20.606-04:00The graph on slide 21 would, I think, not be easy ...The graph on slide 21 would, I think, not be easy to produce when absolute values occur in constraints and larger absolute values benefit the objective (net, if not directly). There may still be room for algorithmic improvements, but I suspect they will be more complicated than what you showed (which was complicated enough for me).<br /><br />Based on our email conversation, I think we're agreed that wherever the support for absolute values falls, ideally it should not be on the users.Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-75064342424748313852012-07-07T12:36:19.238-04:002012-07-07T12:36:19.238-04:00My talk is not completely in same scope as your bl...My talk is not completely in same scope as your blog post, but I think the observations and conclusions are interesting. They affects most modeling choices with abs, which at some points need to be solved with a simplex algorithm. <br /><br />The interesting part is that even very simple improvements, which we can easily do by inspecting the solution, may not be straight forward for the simplex algorithm. <br /><br />Since LP is solved as relaxation in MIP, then it's also relevant for MIP.<br /><br />I am not sure abs should be supported by solvers, but one argument could be the solver then does not need to search for such patterns.Bo Jensenhttps://www.blogger.com/profile/10533779186894174073noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-34960661554362750962012-07-07T11:33:21.625-04:002012-07-07T11:33:21.625-04:00I'm not sure whether I would put the onus on m...I'm not sure whether I would put the onus on modeling languages or solvers, but I can see an argument for building it into solvers. I agree that one or the other should.<br /><br />Splitting free variables may be a bit different. You can split $n$ free variables into $n+1$ nonnegative variables. (I don't know if any solvers do that -- solvers are pretty much black boxes to me -- but I know that using a single additional variable is an option.) With absolute values, I think each expression has to be handled independently of any other absolute values.<br /><br />Your comment got me thinking about a parallel to indicator constraints, though. Like absolute values, you can convert indicators into either "big M" type constraints (danger of loose bounds, numerical instability) or branching logic (even weaker formulation, but no numerical issues). Apparently CPLEX supports both approaches and internally chooses between them. So I guess it makes sense that a solver could support absolute values in model inputs and then internally choose either the binary method or one of the SOS methods.Paul Rubinhttps://www.blogger.com/profile/05801891157261357482noreply@blogger.comtag:blogger.com,1999:blog-8781383461061929571.post-12899842429711675022012-07-07T10:26:53.231-04:002012-07-07T10:26:53.231-04:00It has always seemed to me that this is something ...It has always seemed to me that this is something that the solver should handle. Solvers that split free variables already have to take similar steps to control growth, right?<br /><br />In CVX I actually model the absolute value function using a second-order cone! In other words, $|x|\le y$ becomes $\|x\|\le y$. Of course when it's time to transform the problem to a solver standard form I can convert these degenerate SOC inequalities to linear constraints. But if a solver had a special facility to handle absolute values, then I've preserved enough problem structure to take advantage of it.mcghttps://www.blogger.com/profile/07835164854514314231noreply@blogger.com