Mohsen Moarefdoost Ph.D.
Jan 18th, 2016

iStock_000026778700_Large Multiple Targets for Web

Operations research analysts and modelers try to avoid non-linear models in network and supply chain design. This has led many of us to believe that most of the problems in the area of supply chain are inherently mixed-integer linear problems. In fact, there are many problems that require non-linear modeling; remember that the most basic inventory theory model, EOQ, is non-linear. I’ll give you another simple example: assume that as a planning analyst you are asked to provide a planning solution that is as close as possible to several pre-specified targets. How do you model this? Do you use multi-objective decision-making models? Or, do you use an optimization model to minimize the total distance from the targets? If the target values are given, I use the latter. (If you are a data scientist, this problem is familiar to you, isn’t it?)  But, wait a minute, how do you calculate the distance? If you are a smart OR modeler, you’d say “absolute value” and then with modeling tricks, you’d convert it to a linear program. But maybe you, like me, are fascinated by non-linear programs, so you use a quadratic model, which is non-linear!

 

Sometimes, you can find the optimal solution of an unconstrained non-linear problem by taking its first and second derivatives. Problems that can be solved this way include EOQ, least-squares solution for linear regression, etc. However, most of the time it is difficult to find the optimal solution using derivatives. Or, you may have constrained problem. So, you need to use a non-linear optimization algorithm, like line search, Newton, BFGS, etc. I’m not going to talk about these algorithms; instead I will introduce to you a strong open-source solver that can handle non-linear problems (and uses algorithms like these under the hood).

 

During, my Ph.D., I was dealing with non-linear problems and I found the Ipopt solver to be one of the best. It has interfaces with AMPL, R, MATLAB and Java. If, you are dealing with a mixed integer non-linear program, you can use it inside any branch-and-bound algorithm. With the current computational power, it makes sense to deal with a non-linear model directly rather than trying to cast a non-linear problem as a linear model.

 

Finally, convexity is an important characteristic of any non-linear optimization problem that shouldn’t be ignored. How to solve a non-convex optimization problem is still an open question. There are solvers like BARON designed to find global optima of a non-convex problem. These solvers use branch-and-cut approach and branch-and-reduce approaches to find global optima.