Cómo formular una Función Lineal a Trozos

Una de las preguntas que me hacen con cierta frecuencia en la Unidad de Investigación Operativa de decide4AI es: ¿Cómo se formula una Piecewise Linear Function (PWL) para resolverla con un motor de Programación Lineal Entera?

La respuesta fácil es: No hace falta formularla. Muchos de los productos que resuelven problemas de Programación Lineal Entera traen por defecto una formulación de las PWL que permite usarlas sin saber cómo se representan realmente de forma interna. Aun así, como dice siempre nuestro compañero Miguel Ángel Bógalo, y que yo comparto por completo, «antes de usar un framework, utilidad, o lo que sea, es interesante haber hecho lo mismo a mano previamente, para entender en profundidad lo que se está haciendo.»

Así, voy a utilizar este post para explicar una formulación de la PWL, y las implicaciones de la incorporación de este tipo de funciones a los modelos que se resuelven mediante el uso de Programación Lineal Entera.

¿Qué es una Piecewise Linear Function?

Como vale más una imagen que mil palabras, podemos definir una PWL como esto:

Es decir, una PWL consiste en una secuencia de segmentos contiguos. De cara a representarla con una fórmula, podría representarse de esta manera:

\(f(x)= \left\{ \begin{array}{lcc} 3+4x~for~0\leq x \leq 2\\ 15-2x~for~2\leq x \leq 3\\ 6~+~x~for~3\leq x \leq 7\end{array}\right.\)

¿Cómo linearizar una PWL?

A pesar de que la PWL no es lineal en sí, se observa que en cada intervalo de x correspondiente a cada uno de los segmentos sí que lo es. Así, pensando un poco, podemos llegar a otra formulación que se convierte en casi lineal: Si representamos x como:

\(x=0 \lambda_1+2 \lambda_2+3 \lambda_3+7 \lambda_4\\\lambda_1+ \lambda_2+ \lambda_3+ \lambda_4 = 1\)

y asegurando que como máximo dos λ’s son distintos de 0, y en caso de serlo, son consecutivos, entonces tendremos que Z puede representarse del siguiente modo:

\( z=3\lambda _1+11\lambda _2+9\lambda _3+13\lambda _4 \)

En definitiva, al representar x como una combinación lineal convexa de los valores a, y forzando además a que como máximo dos λ’s son distintos de 0, y en caso de serlo, sean consecutivos, conseguimos ubicar x en uno de los segmentos, quedando, de hecho, Z como:

\( z=3\lambda _1+11\lambda _2+9\lambda _3+13\lambda _4\\\lambda _1+\lambda _2+\lambda _3+\lambda _4 = 1 \)

Para los distintos valores que x puede tomar en el dominio de nuestra función, en donde λ’s son no negativas.

Es muy importante notar la importancia de la propiedad: en caso de serlo, sean consecutivos. Con esta propiedad, al calcular z para un x arbitrario, el cálculo es correcto:

\( \lambda_1=0.5, \lambda _2=0.5, \lambda _3=0, \lambda _4=0\\X = 0*0.5 + 2*0.5 + 3*0 + 7*0 = 1\\Z = 3*0.5+11*0.5+9*0+13*0 = 7 \)

Como vemos, el valor de Z coincide con el que devolvería nuestra función original para x = 1

En caso de no cumplirse esta propiedad, una combinación lineal convexa ‘inadecuada’ podría llevarnos a esta situación:

\( \lambda_1=0.5, \lambda _2=0, \lambda _3=0, \lambda _4=0.5 \\X = 0*0.5 + 2*0 + 3*0 + 7*0.5 = 3.5\\Z = 3*0.5+11*0+9*0+13*0.5 = 8 \)

El valor de Z seria 8 en cambio, nuestra función original valdría 9.5

Esta propiedad, debido a su importancia, tiene un nombre: Special Ordered Set de tipo 2 (SOS2). Todos los motores de Programación Lineal Entera tienen una representación interna de este tipo de conjuntos, y son tratados eficientemente. Aun así, y siguiendo el espíritu de este post, pasaremos ahora a formular este tipo de conjuntos mediante el uso de variables binarias intermedias, de modo que tengamos una representación completamente lineal de las PWL. Esta formulación es la siguiente:

\( x_i\leq y_i~i=1 ,…,4 \\ sum_{i=1}^{4}y_{i}\leq 2\\ y_1+y_3 \leq 1\\ y_1+y_4 \leq 1\\ y_2+y_4 \leq 1\\ \)

Notad que, en esta formulación, cada variable binaria aparece en dos ecuaciones, correspondiendo con los λ’s que podrán ser positivos en caso de que la variable binaria sea 1. De esta manera, hemos conseguido formular de una manera completamente lineal la PWL, ayudándonos de una serie de variables binarias para conseguir formular el Special Ordered Set de tipo 2.

Consideraciones Adicionales

Lo primero que hay que tener en cuenta al usar este tipo de Funciones Lineales a Trozos, es que el problema se hace, en general, bastante más complejo. En nuestro caso, y si nuestro modelo trabajara solamente con variables continuas, automáticamente pasaría de ser un Problema Lineal a ser un Problema Lineal Entero, mucho más complejo en general.

Aun así, hay casos en los que el introducir este tipo de funciones no afecta a la complejidad del problema. Estos son los casos en los que la solución relajada al problema coincide automáticamente con la solución entera.

Si suponemos que la función z que obtenemos es la siguiente:

\( z=13\lambda _1+3\lambda _2+3\lambda _3+13\lambda _4 \)

que se obtendría si nuestra función tuviese forma de U, una elección incorrecta sería:

\( \lambda_1=0.5, \lambda _2=0, \lambda _3=0, \lambda _4=0.5 \)

¿Por qué el motor de Programación Lineal haría esta selección incorrecta de λ’s? Realmente esto sólo podría ocurrir si nuestra función objetivo tratara de maximizar la función de coste. En este caso, le sale más rentable seleccionar estos λ’s, ya que así consigue un valor para la función objetivo más grande. Si la función objetivo, por el contrario, tratara de minimizar la función de coste, jamás habría seleccionado estos λ’s, ya que la opción correcta:

\( \lambda_1=0, \lambda _2=0.5, \lambda _3=0.5, \lambda _4=0 \)

le proporciona un mayor beneficio (un valor menor de la función de coste).

Por lo tanto, si la función de la PWL es la de estar en la función objetivo (cosa, por cierto, bastante común), nos bastará con analizar su concavidad o convexidad, así como el sentido (minimizar o maximizar) de la función objetivo, para determinar la necesidad de incorporar las variables binarias que fuerzan la propiedad SOS2 sobre los λ’s, haciendo que nuestro problema no aumente en complejidad.

Actualización: En cualquier caso, mi recomendación es la de usar, casi siempre, las formulaciones nativas de PWL que traiga el motor de Programación Lineal por defecto y, en caso de no hacerlo, siempre las de SOS2.