Recently I was asked if it would be possible to add the log
function to the Flips library. Flips is a library for modeling and solving Linear and MixedInteger Programming problems. Both classes of problems are constrained to only having linear (i.e. straight) lines. You may ask, “What do you mean by straight?” The following are examples of linear functions.
$$ \displaylines{ \text{Linear Functions}\\ y=1.0x+2.0 \\ y=2.0x_{1}+3.0x_{2} \\ y=1.2x_{1}+1.7x_{2}+x_{3} } $$
The following are nonlinear functions.
$$ \displaylines{ \text{NonLinear Functions} \\ y=1.0x^2+2.0 \\ y=2.0/x_{1}+3.0x_{2} \\ y=1.2x_{1}+1.7x_{2}\times x_{3} } $$
For a function to be linear in the domain of Linear/MixedInteger Programming the variables can only be added, subtracted, or multiplied by a coefficient. The reason this is important is because a Solver takes advantage of this structure which searching for solutions.
What if we need a NonLinear Function
Fortunately, we have ways of working around this limitation. Another way to think of a curve is just a series of straight lines. We could approximate our curve using a series of straight lines that were close enough to the original function to make our answer meaningful. For this example, let’s try modeling the parabola $y=x^2+10.0$. We will use this to represent the Objective Function of our model. Below you see a plot which has a smooth grey line for the exact values of our parabola and a series of point connect by blue line segments. You will notice that the blue line segments closely match the shape of the parabola.
Our goal is to now model our original parabola with a series of segments. We will create a Decision variable which corresponds to each point on the plot. To get a value along the line segments we take a percent of the adjacent points. If I wanted the value of $y$ at the point $x=0.5$, I would use 50% of the value of $x$ at 0.0 and 50% of the value of $x$ at $1.0$. You may recognize this as linearinterpolation. If we want a value for x that is between our Decision variable, we just use a percent of the adjacent decisions. Let’s get to the code!
We open the Flips
library and generate the set of points we want Decisions for. We create a range of values from 5.0
to 5.0
and provide an index for the value. We extract the index values to be elsewhere in our code.


We now want to create a Decision
which corresponds for each of these points.


Next, we need to create a constraints which says the total percentage of the points that we use must be equal to 1.0
. This ensures that the solver is selecting a point along one of our segments.


One of the other rules that we need to impose is that the Solver can only use adjacent points for interpolation. It would make no sense if the Solver interpolated between the points 5.0
and 5.0
. To enforce this behavior, we are going to need to create an additional set of Decisions which correspond to the adjacent points along our line. We use the List.pairwise
function to iterate through the adjacent indices and create the corresponding Decision
. This decision type will be a Boolean
because we either want the solver to use the pair of points or to not use them at all.


Now that we have a Boolean
decision which corresponds to the pairs of Decisions, we need to create a set of constraints which will ensure that the Solver is only using one pair of points. We will do this with two types of constraints. The first constraint states that only one of the Pair decisions can be on at any given time.


The second type of constraints is for each pair of points. It states that if the usePairDecision
is set to 1.0
, then the Solver must assign a total of 1.0
to the two corresponding decisions.


We now have all the structure we need in place to solve a model using our approximation of the parabola. We create a costExpression
which gives us the simplication of the parabola.


We take the costExpression
and use that to create our Objective
. From there we create the model
and populate it with the constraints we created earlier.


We are now ready to solve the model. We are only using the basic settings since this is such a simple problem. We call solve and print out the results.


The result that is printed out…


We can validate this result visually by looking at the plot above.
Constraints on NonLinear Functions
To make things more interesting, let’s add a constraint which says that our parabola can only go up to 1.0
. This would correspond to saying $x\leq 1.0$. Now remember, we do not actually have a single $x$, we have a series of them which correspond to the different points on our plat. So how do we model this? Quite easily! We add a constraint which says the value of our decisions multiplied the corresponding y
value, must be less or equal to 1.0
.


We can use the same code for creating the model and solving. We just add our new constraint to the model.


And the result…


Again, we look at our plot and this makes sense. Hopefully, that provides a little insight into how to model nonlinear functions using linear approximations.