Including intercept terms in piecewise linear programming

Question

I am new to linear programming and am hoping to get some help in understanding how to include intercept terms in the objective for a piecewise function (see below code example).

import pulp as pl

# Pieces
pieces = [1, 2]

# Problem 
prob = pl.LpProblem('Example', pl.LpMaximize)

# Decision Vars
x_vars = pl.LpVariable.dict('x', pieces, 0, None, pl.LpInteger)
y_vars = pl.LpVariable.dict('y', pieces, 0, None, pl.LpInteger)

# Objective
prob += (-500+10*x_vars[1]) + (150+9*x_vars[2]) + (2+9.1*y_vars[1]) + (4+6*y_vars[2])

# Constraints
prob += pl.lpSum(x_vars[i] for i in pieces) + pl.lpSum(y_vars[i] for i in pieces) <= 1100

prob += x_vars[1] <= 700
prob += x_vars[2] <= 700
prob += y_vars[1] <= 400
prob += y_vars[2] <= 400

# Solve
prob.solve()

# Results
for v in prob.variables():
    print(v.name, "=", pl.value(v))

The terms included in the objective function are the piecewise intercepts and coefficients obtained from univariate piecewise regression models. For example, the linear regression model for x is yhat=-500+10*x for the first piece, and yhat=150+9*x for the second piece. Likewise, for y we have yhat=2+9.1*x and yhat=4+6*x for the first and second pieces, respectively.

If I remove and/or change any of the intercept values, I arrive at the same solution. I would have thought that each intercept is required for producing the estimates in the objective function. Have I not specified the objective function properly? ..or are the intercept terms not required (and therefore not taken into account) in this type of LP formulation.

Answer 1

I don't exactly understand what you are trying to achieve. But let me try to explain what we normally do when we talk about piecewise linear functions.

A piecewise linear function is completely determined by its breakpoints. E.g.

The input is just these points

xbar = [1,3,6,10]
ybar = [6,2,8,7] 

These points you have to calculate in advance, outside the optimization model. The intercept and slope of the segments are represented in these points. Note that the intercept cannot be ignored: it would lead to a very different segment. Calculations of these breakpoints need care: without correct breakpoints, your model will not function properly.

When using such a piecewise linear function, we want to maintain a mapping between x and y (both decision variables). I.e. we always want to hold for any feasible solution:

  y = f(x)

where f represents the piecewise linear function. This means that besides choosing a segment, we need to interpolate between the breakpoints (i.e. we want to trace the blue line). The formulations below essentially form the constraint y=f(x) but in such a way that it is accepted by a MIP (Mixed Integer Programming) solver.

To interpolate between the breakpoints, we can use a lot of different formulations. The simplest is to use SOS2 variables. (SOS2 stands for Special Ordered Sets of Type 2, a construct that is supported by most high-end solvers). The formulation would look like:

Here x,y, and λ are decision variables (and xbar,ybar are data, i.e. constants). k is the set of points (here: k=1,..,4).

Not all solvers and modeling tools support SOS2 variables. Here is another formulation using binary variables:

Here s is the segment index: s=1,2,3. This is sometimes called the incremental formulation.

These are just two formulations. There are many others. Note that some solvers and modeling tools have special constructs to express piecewise linear functions. But all these share the idea of providing a collection of breakpoints.

This is very different from what you did. But this is what we typically do to model piecewise linear functions in Mixed-Integer Programming models.

A well-written reference is: H. Paul Williams, Model Building in Mathematical Programming, Wiley. You are encouraged to consult this practical book: it is very good.