Mathematical Programming: Turing completeness and applications to software analysis

Mathematical Programming is Turing complete, and can be used as a general-purpose declarative language. We present a new constructive proof of this fact, and showcase its usefulness by discussing an application to finding the hardest input of any given program running on a Minsky Register Machine. We also discuss an application of Mathematical Programming to … Read more

Cutting Stock with Bounded Open Stacks: a New Integer Linear Programming Model

We address a 1-dimensional cutting stock problem where, in addition to trim-loss minimization, we require that the set of cutting patterns forming the solution can be sequenced so that the number of stacks of parts maintained open throughout the process never exceeds a given $s$. For this problem, we propose a new integer linear programming … Read more

Code verification by static analysis: a mathematical programming approach

Automatic verification of computer code is of paramount importance in embedded systems supplying essential services. One of the most important verification techniques is static code analysis by abstract interpretation: the concrete semantics of a programming language (i.e.the values $\chi$ that variable symbols {\tt x} appearing in a program can take during its execution) are replaced … Read more

On LP Relaxations for the Pattern Minimization Problem

We discuss two formulations of the Pattern Minimization Problem: (1) introduced by Vanderbeck, and (2) obtained adding setup variables to the cutting stock formulation by Gilmore-Gomory. Let $z_i^{LP}(u)$ be the bound given by the linear relaxation of ($i$) under a given vector $u = (u_k)$ of parameters. We show that $z_2^{LP}(u}) \ge z_1^{LP}(u)$ and provide … Read more

A Lagrangian Heuristic for Satellite Range Scheduling with Resource Constraints

The task of scheduling communications between satellites and ground control stations is getting more and more critical since an increasing number of satellites must be controlled by a small set of stations. In such a congested scenario, the current practice, in which experts build hand-made schedules, often leaves a large number of communication requests unserved. … Read more

A p-Median Model for Assortment and Trim Loss Minimization with an Application to the Glass Industry

One of the main issues in the glass industry is the minimization of the trim loss generated when cutting large parts (stocks) into small items. In our application stocks are produced in the plant. Many distinct stock sizes are feasible, and technical constraints limit the variety of cutting patterns to those producing a single type … Read more