1.
Introduccin
La pulpa es una biblioteca para el lenguaje de programacin Python que
permite a los usuarios describir programas matemticos. Python es un nivel
alto bien establecida y apoyada lenguaje de programacin con nfasis en el
desarrollo rpido, la claridad del cdigo y la sintaxis, y un modelo simple
objeto. Pulp funciona enteramente dentro de la sintaxis y expresiones
naturales del lenguaje Python, proporcionando objetos de Python que
representan problemas de optimizacin y variables de decisin, y que
permiten a las limitaciones expresarse de una manera que es muy similar a
la expresin matemtica originales. Para mantener la sintaxis tan simple e
intuitiva como sea posible, la pulpa se ha centrado en el apoyo a los
modelos lineales mixtos y enteros. Pulpa puede ser fcilmente desplegado
en cualquier sistema que tenga un intrprete de Python, ya que no tiene
dependencias en cualquier otra paquetes de programas. Es compatible con
una amplia gama de tanto comerciales como de cdigo abierto
solucionadores, y se pueden ampliar para apoyar solucionadores
adicionales. Por ltimo, est disponible bajo una licencia de cdigo abierto
permisiva que impulse y facilite el uso de la pulpa dentro de otros proyectos
que necesitan capacidades de optimizacin lineal.
2 Diseo y Caractersticas de Pulpa
Se consideraron varios factores en el diseo de la pulpa y en la seleccin de
Python como el lenguaje a utilizar.
2.1 gratis, de cdigo abierto, porttil
Era deseable que la pulpa sea utilizable en cualquier lugar, ya sea como un
sencillo el modelado y la herramienta de experimentacin, o como parte de
una aplicacin industrial ms grande. Esto requiere que la pulpa sea
asequible, fcil de licencia, y adaptable a diferentes entornos de hardware y
software. Python en s ms que cumple estos requisitos: tiene una licencia
de cdigo abierto permisiva y tiene implementaciones disponibles sin costo
para una amplia variedad de plataformas, tanto convencionales como
exticas. Pulp se basa en estas fortalezas tambin por ser libre y con
licencia en virtud de la muy permisiva licencia MIT [11]. Est escrito en
cdigo Python puro, sin crear nuevas dependencias que pueden inhibir la
distribucin o aplicacin.
2.2 Interfaz con solucionadores
Muchos entera mixta de programacin lineal (MILP) solucionadores estn
disponibles, tanto comerciales (Por ejemplo CPLEX [1], Gurobi [2]) y de
cdigo abierto (por ejemplo CBC [6]). Pulp hace una enfoque modular para
resolver por el manejo de la conversin de expresiones Python-Pulp en
nmeros "en bruto" (es decir, matrices dispersas y representaciones del
vector modelo) internamente, y luego exponer estos datos a una clase de
interfaz solver. A medida que la interfaz para muchos solucionadores es
similar, o puede ser manejado por escrito el modelo de los formatos de
archivo estndar L P ORM PS, clases genricas solucionador de base se
incluyen con Pulp, adems de interfaces especficas a los solucionadores
actualmente populares. Estas solucionador clases de medicamentos
genricos pueden ser extendidos por los usuarios o los desarrolladores de
nuevo solucionadores con el mnimo esfuerzo.
2.3 Sintaxis, Sencillez, Estilo
Un estilo formal de la escritura de cdigo Python [13], conocido como cdigo
"Pythonic", se ha desarrollado durante los ltimos 20 aos de desarrollo de
Python. Este estilo es tambin establecida y se centra en la legibilidad y
mantenibilidad del cdigo a travs de "inteligente" manipulaciones que son
ms concisa, pero se consideran perjudiciales para la capacidad de
mantenimiento de proyectos de software. Pulp se basa en este estilo
mediante el uso de los idiomas naturales de programacin Python siempre
que sea posible. Esto se hace por tener muy pocos especiales funciones o
"palabras clave", para evitar contaminar el espacio de nombres de la
lengua. En su lugar, proporciona dos objetos principales (para un problema y
para una variable) y luego usos de las estructuras de control y operadores
aritmticos Python (vase la seccin 3). A diferencia de a Pyomo (seccin
4), otro lenguaje de modelado basado en Python, pulpa hace no permiten a
los usuarios crear modelos puramente abstractos. Mientras que en un
sentido terico esta restringe el usuario, creemos que no es necesaria la
construccin de un modelo abstracto para gran nmero de enfoques en las
lenguas modernas, flexibles dinmicos como Python. Estos lenguajes no
hacen distincin entre los datos o funciones hasta que el cdigo es corren,
permitiendo a los usuarios todava construyen modelos complejos de una
manera pseudo-abstracto. Esto se demuestra en theWedding ejemplo
Planner ( 3.3), donde un pitn funcin est incluida en la funcin objetivo.
2.4 Biblioteca estndar y Paquetes
Uno de los puntos fuertes del lenguaje Python es la extensa biblioteca
estndar que est disponible para todos los programas que utiliza el
intrprete de Python. El estndar biblioteca [4] incluye cientos de mdulos
que permiten al programador, por ejemplo:
leer archivos de datos y bases de datos; ha podido recuperar la
informacin de la Internet; manipular los nmeros y las fechas; crear
interfaces grficas de usuario. Adems de la biblioteca estndar de Python
hay ms de 10.000 paquetes de terceros El ndice de paquetes en Python
[3]. Muchos paquetes relacionados con la investigacin de operaciones se
puede encontrar aqu, incluida la pulpa [10], Coopr [7], Dippy [12], y Yaposib
[5], que son todos los proyectos en el COIN-O repositorio.
3 Ejemplos: pulpa en Accin
En esta seccin se demuestra cmo pulpa puede ser utilizado para modelar
dos diferentes
problemas. El primero, el problema de salud Localizacin capacitado,
demuestra
suficiente cantidad de pulpa para permitir que cualquier MILP que se
describir. La segunda, la boda
problema del planificador, se extiende al
caractersticas ms avanzadas y expresiones
mostrar
algunas
de
las
que describen el modelo de forma ms concisa.
3.1 Sintaxis Python
Para ayudar en la comprensin de los ejemplos, es til para introducir algo
de la
caractersticas del lenguaje pertinentes de Python.
Los espacios en blanco: Python usa la sangra (con espacios o tabuladores)
para indicar las subsecciones
de cdigo.
Declaracin de variables: las variables tienen tipos especficos (por
ejemplo, cadena, nmero,
objeto), pero no es necesario pre-declarar los tipos de variables - la Python
intrprete determinar el tipo de la primera utilizacin de la variable.
Diccionarios y listas: Se trata de dos estructuras de datos comn en
[Link] listas son un simple contenedor de artculos, al igual que las
matrices en muchos idiomas. Pueden cambiar el tamao en cualquier
momento, pueden contener artculos de diferentes tipos, y son uno
dimensional. Los diccionarios son otra estructura de almacenamiento,
donde cada elemento est asociado con una "clave". Esto a veces se
llama un mapa o asociativa matriz en otros idiomas. La clave tal vez sea
casi cualquier cosa, siempre y ya que es nico. Para un anlisis ms
detallado de las fortalezas y capacidades de estas dos estructuras,
consulte la documentacin de Python [14].
comprensin de lista: Estos son dispositivos de "programacin funcional"
que se utiliza en Python para generar dinmicamente listas, y son muy
tiles para generar lineal expresiones como encontrar la suma de un
conjunto. Se proporcionan muchos ejemplos en el cdigo de abajo, pero el
concepto general es crear una nueva lista en su lugar por filtrado, la
manipulacin y la combinacin de otras listas. Por ejemplo, una lista por
comprensin que proporciona los nmeros pares entre 1 y 9 se implementa
con el cdigo Python:
donde tenemos utilizar la divisin de mdulo operador% como nuestro filtro.
3.2 capacitado Facility
Tha capacitado problema de salud Localizacin determina dnde, entre los
lugares m, colocar instalaciones y asigna la produccin de n productos de
estas instalaciones de una manera que (en esta variante) reduce al mnimo
la capacidad de desperdicio de las instalaciones. Cada producto j = 1; :::; n
tiene un requisito de produccin y RJ cada instalacin tiene la misma
capacidad C. Extensiones de este problema surgen a menudo en problemas,
incluyendo diseo de redes y de cuadrantes. La formulacin MILP de este
problema es la siguiente:
A continuacin, podemos preparar los datos necesarios para una instancia
especfica de este problema.
Debido a Pulp crea modelos concretos, a diferencia de otros lenguajes de
modelado, tales como AMPL y Pyomo, tenemos que hacer esto antes de
definir el modelo. Usaremos valores fijos se definen en la secuencia de
comandos en este ejemplo sencillo, pero los datos podran fcilmente ser
almacenados en un archivo, en la Internet, o incluso leer de un sensor u otro
dispositivo.
Se crea un objeto a continuacin, que representar a nuestra instancia
especfica del modelo.
Este objeto, un LpProblem, tiene algunos parmetros opcionales. Aqu
establecemos el problema
nombrar y dar el sentido objetivo, reducir al mnimo.
Todas nuestras variables de decisin en el programa matemtico anterior se
indexan,
y esto se puede expresar de forma natural y de manera concisa con el
objeto de LpVariable
funcionalidad dict. Los yi / use_vars y wi / waste_vars son a la vez similar:
proporcionamos
el nombre de esta variable, la lista de ndices (lugares, lo que hemos
definido
anteriormente), los lmites inferior y superior, y los tipos de variables (si es
una variable
Tipo no est previsto, LpContinuous se supone).
Los xij / assign_vars se definen de la misma manera, excepto por el
ligeramente ms
complicada definicin de los ndices. Aqu se utiliza poderosos "listas por
comprensin" de Python
para crear dinmicamente nuestra lista de ndices, que es un uno-a-un
partido
con los ndices del utilizados en la formulacin. En Ingls, el sub-declaracin
dice "crear
una entrada en la lista de la forma (i, j) para cada combinacin de ubicacin
y el producto ".
Ahora tenemos un problema y algunas variables, podemos definir el objetivo
y
restricciones. El modelo se construye aadiendo literalmente expresiones.
en Python
y muchos otros lenguajes de programacin, el operador en un + b = es la
abreviatura de
"Asignar el valor de a + b a a". Aqu prob + = expresin aade la expresin
a la
Problema como una funcin objetivo o restriccin. Objetivos y limitaciones
pueden ser
expresan exactamente como lo son en la descripcin matemtica, pero se
puede emplear
algunas de las caractersticas que hacen que el modelo ms concisa. El
objetivo es simplemente el
suma de las variables de desecho. Pulp distingue el objetivo de las
restricciones
observando que no hay ningn operador de comparacin utilizado en la
expresin.
Las restricciones se aaden en una forma similar a la del objetivo. Observe
el uso de Pitn de bucle y su paralelo directo en la formulacin matemtica.
Por ltimo utilizamos el solucionador predeterminado, CBC, para resolver el
problema. La solucion es que se muestra a la pantalla mediante el uso de la
propiedad var Valor de las variables, teniendo en cuenta cualquier
imprecisin de punto flotante en las respuestas.
Para el conjunto de datos utilizado en este ejemplo, la solucin ptima es la
siguiente:
3.3 Problema planificador de la boda - una
particin del conjunto de problemas
El problema del planificador de la boda es el siguiente: dada una lista de
asistentes de la boda, un planificador de la boda debe llegar a un plan de
asientos para minimizar la infelicidad de todos los invitados. La infelicidad
de los invitados se define como su mximo infelicidad a estar sentados con
cada uno de los otros huspedes en la mesa, es decir, es una funcin de
pares. La infelicidad de una tabla es la infelicidad mximo de todos los
invitados a la mesa. Todos los huspedes deben estar sentados y hay un
nmero limitado de asientos en cada mesa. Este es un problema de
particin del conjunto, como el conjunto de huspedes G debe ser
particionado en mltiples subconjuntos, con cada miembro de un
subconjunto dado sentado a la misma mesa. La cardinalidad de los
subconjuntos se determina por el nmero de asientos en una mesa y la
infelicidad de una tabla pueden determinarse por el contenido de un
subconjunto.
La
formulacin
MILP
es:
En esta implementacin del problema enumeramos cada mesa sea posible.
Este enfoque llega a ser intratable para un gran nmero de artculos sin
necesidad de utilizar la columna generacin [9], pero es suficiente para los
fines de este ejemplo. Nuestra gente" estar representada por las letras del
alfabeto individuales, y la relativa infelicidad entre dos personas es una
funcin del nmero de cartas entre el dos en el alfabeto Ingls. Cada
particin posible tendr un coeficiente de la funcin objetivo asociada con
eso. La funcin de la felicidad calcula el costo, lo que demuestra una ventaja
de la utilizacin de un lenguaje de propsito general como Python para la
definicin del modelo: todos el poder y la expresividad de Python est
disponible para la implementacin de un modelo.
Tenga en cuenta que esta idea puede extenderse para permitir que varios
mtodos para calcular el costo o incluso permitiendo que la funcin
generadora de costo para ser un "argumento" a la funcin de Python que se
basa el modelo. Utilizamos combinaciones funcin de enumeracin [Link]
de pulpa para generar una lista de todos los posibles asientos de tabla
mediante una lista por comprensin. las variables binarias que ser uno si
un diseo de tabla particular, se utiliza en la solucin, o cero en caso
contrario, se crean usando la funcionalidad mismos [Link]
utilizado en el anterior
ejemplo.
Al igual que antes, creamos un objeto problema y aadimos el objetivo.
Observe el uso de la funcin que hemos creado previamente directamente
en el objetivo - Pulp no le importa que una funcin se utiliza en el objetivo
que la funcin no es dependiente de la las variables - Devuelve un valor
constante para cada tabla.
Se necesita una limitacin para limitar las tablas mximos que se pueden
seleccionar.
La restriccin restante afirma que cada husped se sienta en exactamente
una mesa. Los capacidad del pitn de los bucles de repeticin de cada
miembro de una lista directamente, en lugar de utilizar un ndice numrico,
conduce a cdigo que es de gran fuerza expresiva. Traductorio de nuevo a
partir del cdigo, esta implementacin de la restriccin establece que para
cada uno de los huspedes, el total (suma) de arreglos de mesa /
subconjuntos en donde est el husped en debe ser igual a uno.
Por ejemplo, un problema con trece invitados representado por las letras A
hasta M, la salida de la solucin ptima es la siguiente:
4 Las diferencias entre la pulpa y el Pyomo
La existencia de dos lenguajes de modelado que utilizan Python invita a una
comparacin. Las principales diferencias entre la filosofa de Pyomo [8] y la
pulpa son que la pulpa de modelos no son abstractas, y que la pulpa no
pueden expresar los modelos no lineales. Los decisin de no apoyar
modelos de optimizacin no lineal directa es intrnseca a la diseo de pulpa,
lo que permite la sintaxis de permanecer simple y para mantener el tamao
de la biblioteca pequea al permitir que el cdigo de asumir linealidad. La
necesidad de resumen el modelado se juzga a ser baja en la prctica,
especialmente teniendo en cuenta la visin de la pulpa siendo integrable en
sistemas mayores, donde los datos son casados con el modelo y ninguna
separacin entre ellos es arbitraria. Dado que todos los modelos abstractos
debe convertirse en concreto a resolver, la naturaleza de Python
interpretado difumina la lnea entre ellos como el cdigo del modelo no
interpretada puede ser visto como el modelo abstraccin, y el modelo que
existe en tiempo de ejecucin es de hormign. Pyomo adopta un enfoque
diferente a la funcionalidad adicional, no la construccin de modelos, elegir
para incluir soporte para cargar y guardar los datos dentro de la biblioteca.
Es Tambin acoplado al proyecto ms amplio Cooper, que ofrece an ms
funcionalidad. Pulp elige el camino ms tradicional, favorecido
especialmente por el cdigo abierto comunidad, de hacer una cosa y
hacerlo bien, apoyndose en otras bibliotecas a proporcionar una
funcionalidad adicional. Dada rico ecosistema de paquetes de Python,
sentimos Pulp pierde nada de funcionalidad sin incluir la carga de datos y en
su lugar ganancias por tener menos dependencias y un cdigo de base ms
pequea. La sintaxis de las dos lenguas son similares, pero existe una
diferencia interesante en el modelado de las restricciones. Consideremos el
siguiente ejemplo pulpa, que obliga a los variables de asignacin binarias de
productos a cero si la correspondiente variable de ubicacin es cero:
El cdigo Pyomo no tiene una correspondencia lo ms claro de la
formulacin a codificar yes mas verbal. Utiliza la capacidad de Python para
declarar funciones en cualquier lugar y para almacenar una referencia a una
funcin en una variable, que es til en algunas situaciones pero aumenta la
complejidad y el conocimiento requerido con Python. Se tiene el beneficio
que Pyomo ahora sabe que este conjunto de restricciones se agrupan, pero
muchos solucionadores no admite el uso de esta informacin para mejorar
las soluciones, o CAN no ganar mucho beneficio de ella. Por lo tanto esta
ventaja normalmente se desperdicia en prctica.
5 Conclusin: el caso de la pasta de En las secciones anteriores hemos
hablado de cmo pulpa fue diseado, muestra su fortalezas, demostraron su
uso, y contrastan con su principal "competidor". Aqu se revisan algunos de
los puntos clave de por qu pulpa es una adicin til a la mundo de los
lenguajes de modelado:
5.1 Licencias
La concesin de licencias, de pasta bajo una licencia de cdigo abierto
permisiva permite pasta a utilizar en cualquier lugar y en cualquier
aplicacin, ya sea como una investigacin de operaciones herramienta de
enseanza que pueden los estudiantes pueden descargar y utilizar de forma
gratuita, o integrado de forma transparente en una aplicacin comercial sin
ningn tipo de problemas con las licencias que tratar. Permite a los usuarios
avanzados para modificar y mejorar pulpa para sus propios fines,y asegura
que cualquier problema con el cdigo pueden dirigirse inmediatamente por
una desarrollador o por la comunidad en general.
5.2 interoperabilidad
La capacidad para la pulpa para llamar a un nmero de solucionadores
libres y no libres es importante como profesional de la investigacin de
operaciones desea a menudo para comparar la solucin de un problema con
una variedad de solucionadores. El usuario puede desear para desarrollar LP
sencillo modelos en un solucionador libre y luego proporcionar una solucin
a un cliente usando un comercial solucionador de lo que puede reducir
drsticamente el tiempo de solucin del modelo. Pulpa permite el libre
intercambio de solucionadores con poco esfuerzo - el cambio de un
parmetro para la funcin [Link] es generalmente suficiente.
5.3 sintaxis
La descripcin matemtica de un problema a menudo es el ms potente y
ms limpio Descripcin posible, y cualquier lenguaje de modelado pretende
captar la mayor cantidad de que como sea posible. Creemos Pulp ofrece un
cierre para el mapeo de cdigo a las matemticas que permite a los
usuarios traducir rpidamente un modelo matemtico. Tiene gran legibilidad
del cdigo eso hace que sea fcil de mantener y actualizar los modelos en
una ltima fecha. Esta se consigue mediante el uso de expresiones
idiomticas "Pythonic" y aprovechar todo el poder de la subyacente idioma.
Todos los modelos son de pulpa de hormign y los parmetros del modelo
pueden ser
proporcionado y manipulado de cualquier manera el programador siente es
ms adecuado para la aplicacin. La naturaleza interpretado de Python
permite que los datos de los parmetros sean almacenan como listas,
diccionarios o clases personalizadas, siempre que estas expresiones son
lineales despus de ejecutar el cdigo.
En conclusin, la pulpa es una herramienta de modelado basado en Python
que tiene una combinacin nica de la expresividad, capacidad de
despliegue y el poder que lo diferencia de otros lenguajes de modelado de
alto nivel disponibles. Para el cdigo fuente completo utilizada en los
ejemplos, ms estudios de casos y instrucciones de instalacin visitan la
documentacin Pulp alojada en http: // [Link]/PuLP/.