LPBlocks: a block-based language for linear programming

Abstract

Linear programming is a mathematical optimization technique used in numerous fields including mathematics, economics, and computer science, with numerous industrial contexts, including solving optimization problems such as planning routes, allocating resources, and creating schedules. As a result of its wide breadth of applications, a considerable amount of its user base lacks programming knowledge and experience and thus often resorts to using graphical software such as Microsoft Excel. However, despite its popularity amongst less technical users, the methodologies used by these tools are often ad-hoc and prone to errors. Block-based languages have been successfully used to aid novice programmers and even children in programming. Thus, we created a block-based programming language termed LPBlocks that allows users to create linear programming models using data contained in spreadsheets. This language guides the users to write syntactically and semantically correct programs and thus aids them in a way that current languages do not. We have also implemented a web application where users can define linear programming models, reactively see their mathematical representation and execute them to obtain the optimization values for the variables defined by the users. To assess the applicability of LPBlocks we used it to successfully express numerous and varied linear programming problems. Furthermore, we designed and ran a qualitative empirical study to understand the experience our tool and language brings to users from various backgrounds. Although we see differences amongst the users, most of them were able to model several problems using LPBlocks.

Programação linear é um conjunto de técnicas de otimização matemática utilizada em várias áreas estas incluem matemática, economia, ciências da computação e usos em contextos industriais, incluindo planear rotas, alocar recursos e planear horários. Como resulta das suas aplicações variadas uma grande quantidade dos seus utilizadores não possuem conhecimentos de programação e por isso utilizam software gráfico como o Microsoft Excel. Apesar da sua popularidade este software utiliza metodologias ad-hoc e propicias a erros. As linguagem de programação por blocos tem surgido nos últimos anos com o intuito de ajudar programadores iniciantes, tendo mesmo aplicações no ensino de crianças. Sendo assim nos criamos uma linguagem de programação pro blocos que utiliza dados contidos em folhas de calculo para criar modelos de programação linear chamada LPBlocks. Esta linguagem guia utilizadores na criação de modelos semanticamente e sintaticamente corretos. Para avaliar a validade de LPBlocks nos implementamos vários problemas utilizando a mesma. Posteriormente implementamos esta linguagem e utilizamo-la num estudo com utilizadores de vários níveis de experiência. Depois utilizamos a informação recolhida durante o estudo para avaliar LPBlocks e propor melhorias.