# Non-Linear objective function due to piecewise component

I have the following objective function:

$$\sum_{n}(1-prob_{n})(1+x_n)$$

Where $$x$$ is my decision variable. $$prob_{n}$$ is a piecewise function that can look like:

$$prob_{n} =$$

$$\begin{cases} 0.5, & x_n \leq 4 \\ 0.05, & x_n > 4 \end{cases}$$

The other constraints are:

$$\sum_{n}(1-prob_{n}) > k, k \in R^{+}$$

Seeing as $$prob_n$$ depends on the decision variable, does this mean that the objective function is no longer linear? I 'linearized' it using Big-M notation but when I try to solve it using glpk, I get an error saying that the objective is non-linear. The only reason I can think of is the one stated above or I have misspecified something in my code.

I am a little confused because I am not multiplying the decision variable (i.e. there is no $$x^2$$ term). So I don't see what type of non-linear problem this is.

• Yes, $\text{prob}_n$ times $x_n$ is nonlinear. Also, you have a conflict when $x_n=4$. What type of decision variable is $x_n$? Jul 24 at 21:32
• LaTeX typo, apologies. I have left out a lot of constraints but x is a continuous variable. So I suppose I would need to use a MINLP solver for this (assuming it is convex) Jul 24 at 22:02
• I have added one constraint to the post. Note that this is the only constraint. What I have left out are definitions of variables. Jul 25 at 6:07

This can be MILP using the escape-hatch that binary constraints can capture what would otherwise be a non-linear expression:

With $$d_n \in \lbrace 0, 1 \rbrace$$ as an auxiliary binary decision variable saying whether $$prob_n$$ is "low or high",

$$\sum_{n}(1-prob_{n})(1+x_n)$$

decomposes to

$$\sum_n (1 - 0.05 - (0.5 - 0.05) d_{n})(1+x_n)$$

$$= \sum_n (0.95 - 0.45 d_{n})(1+x_n)$$

$$= 0.95 n + \sum_n \left( 0.95 x_n - 0.45 d_n ( 1 + x_n ) \right)$$

$$= 0.95 n + \sum_n \left( 0.95 x_n - 0.45 d_n -0.45 x'_n \right)$$

where $$x'_n$$, an auxiliary continuous (or semicontinuous) variable, is constrained to be either 0 or $$x_n$$ based on the value of $$d_n$$ with a big-$$M$$ constraint. In many problem constructions you can drop the first $$0.95n$$ term as it is not a function of your variables. You will need constraints smelling roughly like:

$$x_n \le 4 + M_0 (1-d_n)$$

$$x_n > 4 - M_1 d_n$$

$$x'_n \le M_2 d_n$$ $$x'_n \le x_n$$ $$x'_n \ge x_n - M_3 (1-dn)$$

• Very cool approach! I will have to read through it a couple of times before I can wrap my head around this. Just one quick question: would this also be applicable if my piecewise function had several segments instead of just two? Or is this the limiting factor since d_n has to be binary? Jul 25 at 6:02
• The approach would need modification and potentially more variables but will work for more segments Jul 25 at 12:03
• So, I've gone through this a few times now and it is such a nice solution! Is does 'trick' have some name so I can read about using it for more complex functions? Jul 25 at 16:42
• It's basically all in the theme of linearization using integral variables. Some piecewise functions with regular intervals may use integer (non-binary) variables. Too many cases to describe exhaustively. Generally look for expressions that may take a fixed number of values. Jul 25 at 17:05