Accalia face the 3rd degree, re: OR



  • Continuing the discussion from Programming Confessions Thread:

    @boomzilla said:

    This sounds right up my alley (operations research). What are you using (e.g., CPLEX or hand rolled code)?

    Alright, @accalia , spill the beans. Let's talk OR. What kind of algorithm? Any libraries? Talk.

    Paging @boomzilla


    I'll confess first. LP using Inherited Java/C++ to text to AMPL/CPLEX and back.


  • ♿ (Parody)

    @ijij said:

    LP using Inherited Java/C++ to text to AMPL/CPLEX and back.

    That sounds painful.



  • ... and it's on distributed servers communicating via home-grown protocols over RMI. Did I mention the Oracle backend?


    Filed under: "The complicator's gloves"


  • ♿ (Parody)

    I have a couple of C++ programs that uses the old ILOG Solver / Scheduler libraries. I think they've been rolled into CPLEX at this point, but my version is, like, 7 or 8 years old at this point.

    @ijij said:

    ... and it's on distributed servers communicating via home-grown protocols over RMI. Did I mention the Oracle backend?

    Heh...mine just polls our Oracle DB waiting for someone to give it something to do.


  • FoxDev

    libraries... do internally developed ones with absolutely no documentation written by people who's replacements, replacements, replacements have left the company count?

    i swear i would not be surprised if we have some custom DLLs in there that we have no source code for anymore.

    as for design practices? the part i'm working on is fairly straightforward (even if the rules engine required gives a rediculous runtime) but a lot of the rest looks to have been thrown together under the influence of the Balmer Peak...

    I'm looking into replacing the rules engine with something that can get the runtime down to something like O(2^n) but i've got to prove to accounting that it will not create more than a 0.01% error in the VAT charges we apply when we sell the floor space. (that's not going to be easy to prove)


  • ♿ (Parody)

    You should look into actual OR sorts of libraries. You might have luck with constraint programming:

    These guys have spent years studying and implementing stuff attacking this sort of problem. It's unlikely you'll improve on any of that stuff. Additionally, CP is a little simpler to deal with than straight linear (esp. integer) programming, IME, and can deal with some things more flexibly, especially if you're unfamiliar with LP.


  • FoxDev

    I'll look into that, it might help a lot.

    honestly though, this whole thing could be made a million times easier if we just waited to invoice customers (or issued amended invoices when we had to recalculate VAT) until we placed them on the show floor. then we calculate taxes based on where they ended up, not what they asked for, and we can remove all that complication from the layout engine.

    but the beancounters, being the beancounters, want to get paid before they add someone to the show floor... and don't want to go through the effort of filing additional invoices for VAT.

    i can understand that, we're a US company after all, but we do so much business in the EU you'd think accounting would want an easier way of doing things!


  • ♿ (Parody)

    You could also go to a hybrid model, where the system computes all of your constraints and a person does at least some of the layout. This depends on the value of going from good enough to optimal.


  • FoxDev

    we went to the computer model because the manual/hybrid efforts we started with required too many VAT adjustments (about 2 per show... out of between 500 and 1500 exhibitors... that might be TRWTF).

    -sigh-

    i think i'm stuck with the optimal search. At least until our VP of finance retires (he's been retiring "3rd quarter of next year" for the past four years) I might have better luck with his replacement.


  • ♿ (Parody)

    @accalia said:

    i think i'm stuck with the optimal search.

    That's fine. I'd just recommend getting some help from a library that's built for that purpose.



  • CP - I'll look at that, too.

    I was actually thinking about the improvements that could be gained by using a Mixed Integer Programming (MIP) package.

    One approach, comes to mind right away. You could first solve for feasiblity viz. the VAT constraints, and then use that a hot-starting point for improving the solution for constraints and goals that don't affect VAT.

    (If I'm blabbering OR jibberish, holler, I can rewrite).


  • FoxDev

    i'll be looking into that. anything to get this off my plate for good (or for at least long enough to get something else done!)


  • ♿ (Parody)

    @ijij said:

    I was actually thinking about the improvements that could be gained by using a Mixed Integer Programming (MIP) package.

    This is probably the right tool, but I think it's more difficult for the non-OR person to use.



  • An important point - if you've got a business critical computing-step that takes two days to run (I think I've got that right) - it really screws up the business process:

    You can't do any what-if excursions of any kind.

    Even if you get it down to overnight, you'd be a rockstar at the company - and I bet you could do even better than that.


  • FoxDev

    I've tried a few different things, but none of them got the approval to go live. Some due to politics, others due to... i'm not sure.

    i had one change to the process that got it down to 2 hours but required refiling about 15 to 20% of invoices to account for VAT (most changes were less than five euro, changes over ten euro were extremely rare, direction of the change was about even between refund vs extra charge)

    that one was rejected because accounting didn't want to trigger a VAT audit because of the suddenly increased number of reissued invoices (somewhat reasonable, but by my estimate we'd make the cost of the audit back in three months, a year if we happened to trigger a fine as a result of the audit)



  • @boomzilla said:

    This is probably the right tool, but I think it's more difficult for the non-OR person to use.

    I'll reserve the right to agree or disagree after I have chance to get the rundown on CP. But this is what I was thinking.

    AMPL might help bridge the gap - it let's you write your goals and constraints pretty straightforwardly (and it lets you do the multi-stage stuff I was dreaming up) - but, no API except text.


  • ♿ (Parody)

    I guess I've never done LP/MLP outside of something like AMPL (or a dedicated program or simplex by hand O_o) , so maybe a good API fixes that.

    The "problem" with LP IME is that you have to be somewhat creative in how you define constraints and apply them to your objective. It takes a certain way of thinking that isn't immediately obvious until you've done it a bit. At least with a lot of interesting problems. So CP is a little more flexible at the obvious expense of efficiency.



  • @boomzilla said:

    The "problem" with LP IME is that you have to be somewhat creative in how you define constraints and apply them to your objective. It takes a certain way of thinking...

    So True. For almost all values of True!

    MIP constraints are even more so.

    I was just talking to a Game Artist about this over the weekend... (coincidentally on a Webelos campout) (campout is one word isn't it).
    ...he can't get his programmers to do it how he wants because they're not really thinking about things the same.

    He also asked me a math question, since he didn't grok the google-fu for math.. Answer: "You're looking for the Gaussian cumulative probability distribution function."


Log in to reply