On January 29 and 30, I conducted a webinar on model review and validation about a specific project that entailed challenges and solutions of great potential interest to the larger community of optimization practitioners. Anita Bowers and Gwyneth Butera of Gurobi were the hosts and moderators. My co-presenter was Ugo Feunekes, the co-founder and CTO of Remsoft. Following is a lightly edited transcript of highlights of the webinar, which can be watched on this Gurobi webpage.
Ugo: We have a number of clients dealing with highly complex models. The range of planning challenges runs from short‑term crew scheduling to transportation and harvesting, to long‑term sustainable forest management plan. Back in the late '90s, we were dealing more often with long‑term strategic planning problems, but in the more recent decades, we've started dealing with shorter time intervals, dealing with intervals of seven‑day planning periods, for seven‑day planning periods. This introduces a whole series of new, complex problems because a lot of these problems now are using MIP formulations and solving them became more difficult.
In a typical “scary” model, we have maybe 25,000 non‑zeros and over 150,000 integers. These are the kinds of models that we wanted to talk to Princeton Consultants about. Another problem that we often have is that these models are constantly changing. If we’re dealing with models that are cycled every seven days, we plan every seven days. The old data, the data that actually has happened and time has passed, that goes away and new data gets entered into the model, and so, what worked a week before or two weeks before may not work anymore. Frequent refreshes generate issues sometimes for us.
What was the issue? I guess what we were finding is that we encounter what we thought are unreasonably long solve times. Sometimes we’d go for days and not even find solutions. Sometimes we’d find infeasibilities, but also things were sometimes unpredictable. We often try different Gurobi tuning parameters, but because our client's models are all slightly different, what works for one model doesn't necessarily work for the other one—sometimes it makes things actually worse. We're finding sometimes that simply adding an additional constraint makes solving impossible. Other times, removing constraints increases solve times, which baffles us. Compounding all that, when we remove constraints, even if that helps us, many times our clients are simply reluctant to simplify those models. They want to have as much reality in the model as possible. These are the kinds of issues that we approached Princeton Consultants with.
Our questions were, “What's happening here? What's causing these issues? Are there things that we can do to tweak our modeling platform, change our stuff to make things easier for users? Because our platforms are being used by users, are there things we can tell the users to do? Are there better ways to structure their models so that some of the problems, some of the solution times can come down? Can we improve Gurobi performance by changing parameters, and what are the best practices that you can share with us?”
That's basically the background. What we start to see now are the some of the outcomes, some of the results of the work we’ve done together. The first recommendation was discussion about precision versus accuracy. A standard recommendation that we’ve heard many times is to use double precision to represent values for your application. That's true. However, you have to be careful. Sometimes too much accuracy can be too precise for a problem. A lot of our data comes from other systems. A lot of our data comes from geographical information systems. We can have data that comes with area sections, area records that have precision down to five, six decimal places. People tend to like to have that accuracy in their model. Over time, I'm not sure how big an issue that was for us because many of our early models were not mixed integer formulations; they were just straight linear problems and the precision didn't cause as much problems there. We want to consider producing a number of significant digits if we can, make them relative to what the problem is.
Irv: Ugo, you said that, because the Remsoft platform had been around for years, you had started with single precision for some time back in the '90s, right?
Ugo: That's correct. We started this application in the late ‘90s. Hardware available to us was quite different than it is today. Because we have so many numbers, single precision numbers are smaller than double precision, so just to get the memory footprint to work for the app, the program to fit in memory, we started off in single precision.
Irv: One of the things that came out as we were studying the models at Remsoft is, as Ugo mentioned, there are different clients. Their modeling platform is a little bit analogous to what can be done with modeling languages. Each of their clients has different kinds of models, with different data feeding in the models. Being able to say there's a one-size-fits-all set of parameters for all the models really didn't work. As we looked closer at the models, we saw this issue with precision vs accuracy. In one example, when you would look at a constraint and try to understand the meaning of the constraint, you'd realize it was a constraint asking for something to be down to a very small thing that would be a pinch of your fingers, the level of accuracy wasn't appropriate.
The recommendation here is thinking about the data, how things get multiplied by each other, and understand you can use the platform to round numbers to a certain number of digits that's appropriate for the application. This is important when you're looking at applications that involve money. I’ve seen applications where people are specifying constraints and the unit of the constraint is dollars, the typical values are in the millions of dollars and they're asking for accuracy down to the penny. The same thing is true if your objective function is about money. If you're setting optimality tolerances, you want to be careful and say, "Does it really matter about the last few pennies or even the last few dollars if your objective function is going to be in the millions or tens of millions of dollars.” The statement, "We use double precision," comes with a little bit of a caveat because you have to consider the real accuracy that's needed with respect to how you stated the unit of your constraints and the units of your objective function.
Ugo: Remsoft has always had the ability to specify goals to help us find infeasibilities and constraints. What we encountered over time is we started to come up with blended objectives. The idea between the blended objectives was that, rather than run a strict goal run where our goal is to minimize penalties, we tell our user to make a combined or a blended objective where if your objective is to maximize net revenue, make your objective maximize net revenue minus this penalty function. The idea behind this was that by blending those objectives, a single run, we’d get you a solution. Instead of saying, "We're good to go—adjust the constraints," we run with the real objective. This simplifies process. However, it worked quite well for linear matrices. Once we started to get into the MIP formulations, Princeton Consultants suggested that this is causing us and the MIP solvers difficulties because it has a tough time figuring that out.
Since that time, we'd certainly recommend to people don't do that, but we have developed a system or process where we can basically deal with a hierarchical approach where we put two objectives into the matrix when we build the matrix. The first objective is the one that we're interested in. Maybe max net revenue. The second objective we put in is the goal formulation—the objective of that one is to minimize penalties. What we do, when we put the two objectives in, is we put a bound on the penalty function. The bound has to be zero, so that when we do the first optimization, the model will solve and it cannot take on penalty values because it's been bound. If our process detects infeasibility, we do two things—we change objectives to be the second objective. We change the bound on the penalties and resolve it. Once we’ve resolved it, we can then adjust our constraints automatically. Within one run, with one matrix, we do apparently what it looks like one solve. We can basically create a hierarchical approach similar to what Princeton suggests.
Irv: Ugo and I reconnected after this project. When he described this new approach, I said, “Hey, that is the hierarchical approach that we had written in our report.” Since that time, Gurobi now has added multiple objective support. I am using it on a project right now with another Gurobi Client. We're taking advantage of these approaches. In general, in the work that we've done with our clients, we often recommend the hierarchical approach. One reason is it can be more easily mapped to business requirements. It's hard to explain to a business person why an objective is a combination of two different types of things that have very different units. They can understand the idea of solving a problem, like Ugo was saying, where you have constraints. You're finding the best relaxation of that constraint in order to make the problem feasible and then finding the optimal solution subject to not letting it become any more infeasible than is needed. We often with our clients end up using these hierarchical approaches. Now that Gurobi has added the support, we're starting to use it more directly instead of having to code it ourselves as we've done in the past. We're also providing some feedback to Gurobi about how we'd like some support for things like piecewise-linear objectives inside of hierarchical objective functions.