Saturday, July 14, 2012

Piecewise Linear Functions in CPLEX

Patricia Randall just published a blog post, "Piecewise Linear Objective Functions in Mathematical Models", in which she mentions using (or trying to use) the support for piecewise linear functions built into CPLEX APIs. (There's also a rather groan-worthy mathematical pun at the end of the post, in case you want to abuse yourself.)  I've talked about piecewise linear functions before (links below), and I'll try not to repeat myself too much. I'm aware of the function Patricia refers to (in the Java API, it is IloMPModeler.piecewiseLinear(), and is overloaded several ways). I've never used it, though.

From a modeling perspective, not all piecewise linear functions are created equal. In particular, those that induce an economy of scale require the use of binary variables (or modified branching logic in a MIP, or some other trick) to implement, whereas those that induce a diseconomy of scale can be converted into sets of linear constraints. Cutting to the chase scene, if your model would otherwise be a linear program, sometimes piecewise linear functions turn it into a MILP and sometimes they don't.

As I read Patricia's piece, I got curious whether the implementation of  IloMPModeler.piecewiseLinear() included a check for whether binary variables were needed (which is easy in some specific contexts but could be hard in the general case), or whether it always used binary variables. So I created a little test case, and based on that test case, it appears the latter is true.

The test case is a continuous knapsack problem (maximization) where the value (objective contribution) of each item is a concave piecewise linear function with three segments (two breakpoints). The value of a typical item might look like

where $f_1,f_2,f_3$ are linear functions that extrapolate the three segments of the value function $f$.

The base model is \begin{gather*}\textrm{maximize }\sum_{i=1}^n f_i(x_i)\\\textrm{s..t. }\sum_{i=1}^n w_i x_i \le C\\0 \le x_i \le U_i \quad\forall i\in \{1,\dots,n\}\end{gather*} where $x_i$ is the amount of item $i$ packed in the knapsack, $U_i$ is the amount of that item available, $f_i(x_i)\ge 0$ is the (piecewise-linear) value of packing $x_i$, $w_i>0$ is the unit weight of item $i$, and $C$ is the capacity of the knapsack. I randomly generated parameter values, set this model up in CPLEX using IloMPModeler.piecewiseLinear() to express each $f_i()$, and solved it. CPLEX turned the model into a MILP.  Just to be sure I had not erred, I created a second CPLEX model using the following formulation:\begin{gather*}\textrm{maximize }\sum_{i=1}^n z_i\\\textrm{s..t. }\sum_{i=1}^n w_i x_i \le C\\z_i \le m_{i1} x_i\quad\forall i\in \{1,\dots,n\}\\ z_i \le (m_{i1}-m_{i2})b_{i1} + m_{i2}x_i \quad\forall i\in \{1,\dots,n\}\\ z_i \le (m_{i1}-m_{i2})b_{i1} + (m_{i2}-m_{i3})b_{i2} + m_{i3}x_i \quad\forall i\in \{1,\dots,n\}\\
0 \le x_i \le U_i \quad\forall i\in \{1,\dots,n\}\\0\le z_i\quad\forall i\in \{1,\dots,n\}\end{gather*}where $z_i$ is the objective contribution of item $i$, $b_{i1}$ and $b_{i2}$ are the breakpoints for $f_i$ (with $0<b_{i1}<b_{i2}<U_i$) , and $m_{i1}>m_{i2}>m_{i3}>0$ are the slopes of $f_i$ ordered by increasing $x_i$. CPLEX solved this model as an LP and returned the same solution that it found for the MILP.

Is this a matter of concern? I'm not positive, but I'm inclined not to think so, or at least not too much. CPLEX solved the MILP model ($n=50$ items) at the root node, and I suspect this is not a coincidence -- I'm pretty sure the LP relaxation of the MILP will push the binary variables in the desired direction. There is a size difference, though, as shown in the following table:

ModelConstraintsVariablesNonzerosSOS
MILP15130065050
LP151100350--

As a sidebar, with three segments (two breakpoints) in each function $f_i$, CPLEX introduces no binary variables but instead introduces one Special Ordered Set (I assume type 2) per item. With two segments (one breakpoint), though, it introduces one binary variable per item and no SOSes.

Related posts: