Decomposition and reformulation of integer linear programming problems

This thesis deals with an investigation of Decomposition and Reformulation to solve Integer Linear Programming Problems. This method is often a very successful approach computationally, producing high-quality solutions for well-structured combinatorial optimization problems like vehicle routing, cutting stock, p-median and generalized assignment . However, until now the method has always been tailored to the specific problem under investigation. The principal innovation of this thesis is to develop a new framework able to apply this concept to a generic MIP problem. The new approach is thus capable of auto-decomposition and autoreformulation of the input problem applicable as a resolving black box algorithm and works as a complement and alternative to the normal resolving techniques. The idea of Decomposing and Reformulating (usually called in literature Dantzig and Wolfe Decomposition DWD) is, given a MIP, to convexify one (or more) subset(s) of constraints (slaves) and working on the partially convexified polyhedron(s) obtained. For a given MIP several decompositions can be defined depending from what sets of constraints we want to convexify. In this thesis we mainly reformulate MIPs using two sets of variables: the original variables and the extended variables (representing the exponential extreme points). The master constraints consist of the original constraints not included in any slaves plus the convexity constraint(s) and the linking constraints(ensuring that each original variable can be viewed as linear combination of extreme points of the slaves). The solution procedure consists of iteratively solving the reformulated MIP (master) and checking (pricing) if a variable of reduced costs exists, and in which case adding it to the master and solving it again (columns generation), or otherwise stopping the procedure. The advantage of using DWD is that the reformulated relaxation gives bounds stronger than the original LP relaxation, in addition it can be incorporated in a Branch and bound scheme (Branch and Price) in order to solve the problem to optimality. If the computational time for the pricing problem is reasonable this leads in practice to a stronger speed up in the solution time, specially when the convex hull of the slaves is easy to compute, usually because of its special structure.

Constraint based methods for allocation and scheduling of periodic applications

This work presents exact algorithms for the Resource Allocation and Cyclic Scheduling Problems (RA&CSPs). Cyclic Scheduling Problems arise in a number of application areas, such as in hoist scheduling, mass production, compiler design (implementing scheduling loops on parallel architectures), software pipelining, and in embedded system design. The RA&CS problem concerns time and resource assignment to a set of activities, to be indefinitely repeated, subject to precedence and resource capacity constraints. In this work we present two constraint programming frameworks facing two different types of cyclic problems. In first instance, we consider the disjunctive RA&CSP, where the allocation problem considers unary resources. Instances are described through the Synchronous Data-flow (SDF) Model of Computation. The key problem of finding a maximum-throughput allocation and scheduling of Synchronous Data-Flow graphs onto a multi-core architecture is NP-hard and has been traditionally solved by means of heuristic (incomplete) algorithms. We propose an exact (complete) algorithm for the computation of a maximum-throughput mapping of applications specified as SDFG onto multi-core architectures. Results show that the approach can handle realistic instances in terms of size and complexity. Next, we tackle the Cyclic Resource-Constrained Scheduling Problem (i.e. CRCSP). We propose a Constraint Programming approach based on modular arithmetic: in particular, we introduce a modular precedence constraint and a global cumulative constraint along with their filtering algorithms. Many traditional approaches to cyclic scheduling operate by fixing the period value and then solving a linear problem in a generate-and-test fashion. Conversely, our technique is based on a non-linear model and tackles the problem as a whole: the period value is inferred from the scheduling decisions. The proposed approaches have been tested on a number of non-trivial synthetic instances and on a set of realistic industrial instances achieving good results on practical size problem.

Structure property relations in complex copolymer systems

A thorough investigation was made of the structure-property relation of well-defined statistical, gradient and block copolymers of various compositions. Among the copolymers studied were those which were synthesized using isobornyl acrylate (IBA) and n-butyl acrylate (nBA) monomer units. The copolymers exhibited several unique properties that make them suitable materials for a range of applications. The thermomechanical properties of these new materials were compared to acrylate homopolymers. By the proper choice of the IBA/nBA monomer ratio, it was possible to tune the glass transition temperature of the statistical P(IBA-co-nBA) copolymers. The measured Tg’s of the copolymers with different IBA/nBA monomer ratios followed a trend that fitted well with the Fox equation prediction. While statistical copolymers showed a single glass transition (Tg between -50 and 90 ºC depending on composition), DSC block copolymers showed two Tg’s and the gradient copolymer showed a single, but very broad, glass transition. PMBL-PBA-PMBL triblock copolymers of different composition ratios were also studied and revealed a microphase separated morphology of mostly cylindrical PMBL domains hexagonally arranged in the PBA matrix. DMA studies confirmed the phase separated morphology of the copolymers. Tensile studies showed the linear PMBL-PBA-PMBL triblock copolymers having a relatively low elongation at break that was increased by replacing the PMBL hard blocks with the less brittle random PMBL-r-PMMA blocks. The 10- and 20-arm PBA-PMBL copolymers which were studied revealed even more unique properties. SAXS results showed a mixture of cylindrical PMBL domains hexagonally arranged in the PBA matrix, as well as lamellar. Despite PMBL’s brittleness, the triblock and multi-arm PBA-PMBL copolymers could become suitable materials for high temperature applications due to PMBL’s high glass transition temperature and high thermal stability. The structure-property relation of multi-arm star PBA-PMMA block copolymers was also investigated. Small-angle X-ray scattering revealed a phase separated morphology of cylindrical PMMA domains hexagonally arranged in the PBA matrix. DMA studies found that these materials possess typical elastomeric behavior in a broad range of service temperatures up to at least 250°C. The ultimate tensile strength and the elastic modulus of the 10- and 20-arm star PBA-PMMA block copolymers are significantly higher than those of their 3-arm or linear ABA type counterparts with similar composition, indicating a strong effect of the number of arms on the tensile properties. Siloxane-based copolymers were also studied and one of the main objectives here was to examine the possibility to synthesize trifluoropropyl-containing siloxane copolymers of gradient distribution of trifluoropropyl groups along the chain. DMA results of the PDMS-PMTFPS siloxane copolymers synthesized via simultaneous copolymerization showed that due to the large difference in reactivity rates of 2,4,6-tris(3,3,3-trifluoropropyl)-2,4,6-trimethylcyclotrisiloxane (F) and hexamethylcyclotrisiloxane (D), a copolymer of almost block structure containing only a narrow intermediate fragment with gradient distribution of the component units was obtained. A more dispersed distribution of the trifluoropropyl groups was obtained by the semi-batch copolymerization process, as the DMA results revealed more ‘‘pure gradient type’’ features for the siloxane copolymers which were synthesized by adding F at a controlled rate to the polymerization of the less reactive D. As with trifluoropropyl-containing siloxane copolymers, vinyl-containing polysiloxanes may be converted to a variety of useful polysiloxane materials by chemical modification. But much like the trifluoropropyl-containing siloxane copolymers, as a result of so much difference in the reactivities between the component units 2,4,6-trivinyl-2,4,6-trimethylcyclotrisiloxane (V) and hexamethylcyclotrisiloxane (D), thermal and mechanical properties of the PDMS-PMVS copolymers obtained by simultaneous copolymerization was similar to those of block copolymers. Only the copolymers obtained by semi-batch method showed properties typical for gradient copolymers.

Mac protocols for linear wireless (sensor) networks

Wireless sensor networks (WSNs) consist of a large number of sensor nodes, characterized by low power constraint, limited transmission range and limited computational capabilities [1][2].The cost of these devices is constantly decreasing, making it possible to use a large number of sensor devices in a wide array of commercial, environmental, military, and healthcare fields. Some of these applications involve placing the sensors evenly spaced on a straight line for example in roads, bridges, tunnels, water catchments and water pipelines, city drainages, oil and gas pipelines etc., making a special class of these networks which we define as a Linear Wireless Network (LWN). In LWNs, data transmission happens hop by hop from the source to the destination, through a route composed of multiple relays. The peculiarity of the topology of LWNs, motivates the design of specialized protocols, taking advantage of the linearity of such networks, in order to increase reliability, communication efficiency, energy savings, network lifetime and to minimize the end-to-end delay [3]. In this thesis a novel contention based Medium Access Control (MAC) protocol called L-CSMA, specifically devised for LWNs is presented. The basic idea of L-CSMA is to assign different priorities to nodes based on their position along the line. The priority is assigned in terms of sensing duration, whereby nodes closer to the destination are assigned shorter sensing time compared to the rest of the nodes and hence higher priority. This mechanism speeds up the transmission of packets which are already in the path, making transmission flow more efficient. Using NS-3 simulator, the performance of L-CSMA in terms of packets success rate, that is, the percentage of packets that reach destination, and throughput are compared with that of IEEE 802.15.4 MAC protocol, de-facto standard for wireless sensor networks. In general, L-CSMA outperforms the IEEE 802.15.4 MAC protocol.

Development of Dynamic Constraint Models for a Model Based Transient Calibration Process

Model based calibration has gained popularity in recent years as a method to optimize increasingly complex engine systems. However virtually all model based techniques are applied to steady state calibration. Transient calibration is by and large an emerging technology. An important piece of any transient calibration process is the ability to constrain the optimizer to treat the problem as a dynamic one and not as a quasi-static process. The optimized air-handling parameters corresponding to any instant of time must be achievable in a transient sense; this in turn depends on the trajectory of the same parameters over previous time instances. In this work dynamic constraint models have been proposed to translate commanded to actually achieved air-handling parameters. These models enable the optimization to be realistic in a transient sense. The air handling system has been treated as a linear second order system with PD control. Parameters for this second order system have been extracted from real transient data. The model has been shown to be the best choice relative to a list of appropriate candidates such as neural networks and first order models. The selected second order model was used in conjunction with transient emission models to predict emissions over the FTP cycle. It has been shown that emission predictions based on air-handing parameters predicted by the dynamic constraint model do not differ significantly from corresponding emissions based on measured air-handling parameters.

Scaling relations between trabecular bone volume fraction and microstructure at different skeletal sites

In this study, we investigated the scaling relations between trabecular bone volume fraction (BV/TV) and parameters of the trabecular microstructure at different skeletal sites. Cylindrical bone samples with a diameter of 8mm were harvested from different skeletal sites of 154 human donors in vitro: 87 from the distal radius, 59/69 from the thoracic/lumbar spine, 51 from the femoral neck, and 83 from the greater trochanter. μCT images were obtained with an isotropic spatial resolution of 26μm. BV/TV and trabecular microstructure parameters (TbN, TbTh, TbSp, scaling indices (< > and σ of α and αz), and Minkowski Functionals (Surface, Curvature, Euler)) were computed for each sample. The regression coefficient β was determined for each skeletal site as the slope of a linear fit in the double-logarithmic representations of the correlations of BV/TV versus the respective microstructure parameter. Statistically significant correlation coefficients ranging from r=0.36 to r=0.97 were observed for BV/TV versus microstructure parameters, except for Curvature and Euler. The regression coefficients β were 0.19 to 0.23 (TbN), 0.21 to 0.30 (TbTh), −0.28 to −0.24 (TbSp), 0.58 to 0.71 (Surface) and 0.12 to 0.16 (<α>), 0.07 to 0.11 (<αz>), −0.44 to −0.30 (σ(α)), and −0.39 to −0.14 (σ(αz)) at the different skeletal sites. The 95% confidence intervals of β overlapped for almost all microstructure parameters at the different skeletal sites. The scaling relations were independent of vertebral fracture status and similar for subjects aged 60–69, 70–79, and >79years. In conclusion, the bone volume fraction–microstructure scaling relations showed a rather universal character.

A mixed-integer linear programming approach to the optimization of event-bus schedules: a scheduling application in the tourism sector

This paper deals with “The Enchanted Journey,” which is a daily event tour booked by Bollywood-film fans. During the tour, the participants visit original sites of famous Bollywood films at various locations in Switzerland; moreover, the tour includes stops for lunch and shopping. Each day, up to five buses operate the tour. For operational reasons, however, two or more buses cannot stay at the same location simultaneously. Further operative constraints include time windows for all activities and precedence constraints between some activities. The planning problem is how to compute a feasible schedule for each bus. We implement a two-step hierarchical approach. In the first step, we minimize the total waiting time; in the second step, we minimize the total travel time of all buses. We present a basic formulation of this problem as a mixed-integer linear program. We enhance this basic formulation by symmetry-breaking constraints, which reduces the search space without loss of generality. We report on computational results obtained with the Gurobi Solver. Our numerical results show that all relevant problem instances can be solved using the basic formulation within reasonable CPU time, and that the symmetry-breaking constraints reduce that CPU time considerably.

The coupling of non-linear supersymmetry to supergravity

We study the coupling of non-linear supersymmetry to supergravity. The goldstino nilpotent superfield of global supersymmetry coupled to supergravity is described by a geometric action of the chiral curvature superfield R subject to the constraint (R−λ)2=0 with an appropriate constant λ. This constraint can be found as the decoupling limit of the scalar partner of the goldstino in a class of f(R) supergravity theories.

Index Tracking Using Data-Mining Techniques and Mixed-Binary Linear Programming

Index tracking has become one of the most common strategies in asset management. The index-tracking problem consists of constructing a portfolio that replicates the future performance of an index by including only a subset of the index constituents in the portfolio. Finding the most representative subset is challenging when the number of stocks in the index is large. We introduce a new three-stage approach that at first identifies promising subsets by employing data-mining techniques, then determines the stock weights in the subsets using mixed-binary linear programming, and finally evaluates the subsets based on cross validation. The best subset is returned as the tracking portfolio. Our approach outperforms state-of-the-art methods in terms of out-of-sample performance and running times.

Relational and Allegorical Semantics for Constraint Logic Programming

El cálculo de relaciones binarias fue creado por De Morgan en 1860 para ser posteriormente desarrollado en gran medida por Peirce y Schröder. Tarski, Givant, Freyd y Scedrov demostraron que las álgebras relacionales son capaces de formalizar la lógica de primer orden, la lógica de orden superior así como la teoría de conjuntos. A partir de los resultados matemáticos de Tarski y Freyd, esta tesis desarrolla semánticas denotacionales y operacionales para la programación lógica con restricciones usando el álgebra relacional como base. La idea principal es la utilización del concepto de semántica ejecutable, semánticas cuya característica principal es el que la ejecución es posible utilizando el razonamiento estándar del universo semántico, este caso, razonamiento ecuacional. En el caso de este trabajo, se muestra que las álgebras relacionales distributivas con un operador de punto fijo capturan toda la teoría y metateoría estándar de la programación lógica con restricciones incluyendo los árboles utilizados en la búsqueda de demostraciones. La mayor parte de técnicas de optimización de programas, evaluación parcial e interpretación abstracta pueden ser llevadas a cabo utilizando las semánticas aquí presentadas. La demostración de la corrección de la implementación resulta extremadamente sencilla. En la primera parte de la tesis, un programa lógico con restricciones es traducido a un conjunto de términos relacionales. La interpretación estándar en la teoría de conjuntos de dichas relaciones coincide con la semántica estándar para CLP. Las consultas contra el programa traducido son llevadas a cabo mediante la reescritura de relaciones. Para concluir la primera parte, se demuestra la corrección y equivalencia operacional de esta nueva semántica, así como se define un algoritmo de unificación mediante la reescritura de relaciones. La segunda parte de la tesis desarrolla una semántica para la programación lógica con restricciones usando la teoría de alegorías—versión categórica del álgebra de relaciones—de Freyd. Para ello, se definen dos nuevos conceptos de Categoría Regular de Lawvere y _-Alegoría, en las cuales es posible interpretar un programa lógico. La ventaja fundamental que el enfoque categórico aporta es la definición de una máquina categórica que mejora e sistema de reescritura presentado en la primera parte. Gracias al uso de relaciones tabulares, la máquina modela la ejecución eficiente sin salir de un marco estrictamente formal. Utilizando la reescritura de diagramas, se define un algoritmo para el cálculo de pullbacks en Categorías Regulares de Lawvere. Los dominios de las tabulaciones aportan información sobre la utilización de memoria y variable libres, mientras que el estado compartido queda capturado por los diagramas. La especificación de la máquina induce la derivación formal de un juego de instrucciones eficiente. El marco categórico aporta otras importantes ventajas, como la posibilidad de incorporar tipos de datos algebraicos, funciones y otras extensiones a Prolog, a la vez que se conserva el carácter 100% declarativo de nuestra semántica. ABSTRACT The calculus of binary relations was introduced by De Morgan in 1860, to be greatly developed by Peirce and Schröder, as well as many others in the twentieth century. Using different formulations of relational structures, Tarski, Givant, Freyd, and Scedrov have shown how relation algebras can provide a variable-free way of formalizing first order logic, higher order logic and set theory, among other formal systems. Building on those mathematical results, we develop denotational and operational semantics for Constraint Logic Programming using relation algebra. The idea of executable semantics plays a fundamental role in this work, both as a philosophical and technical foundation. We call a semantics executable when program execution can be carried out using the regular theory and tools that define the semantic universe. Throughout this work, the use of pure algebraic reasoning is the basis of denotational and operational results, eliminating all the classical non-equational meta-theory associated to traditional semantics for Logic Programming. All algebraic reasoning, including execution, is performed in an algebraic way, to the point we could state that the denotational semantics of a CLP program is directly executable. Techniques like optimization, partial evaluation and abstract interpretation find a natural place in our algebraic models. Other properties, like correctness of the implementation or program transformation are easy to check, as they are carried out using instances of the general equational theory. In the first part of the work, we translate Constraint Logic Programs to binary relations in a modified version of the distributive relation algebras used by Tarski. Execution is carried out by a rewriting system. We prove adequacy and operational equivalence of the semantics. In the second part of the work, the relation algebraic approach is improved by using allegory theory, a categorical version of the algebra of relations developed by Freyd and Scedrov. The use of allegories lifts the semantics to typed relations, which capture the number of logical variables used by a predicate or program state in a declarative way. A logic program is interpreted in a _-allegory, which is in turn generated from a new notion of Regular Lawvere Category. As in the untyped case, program translation coincides with program interpretation. Thus, we develop a categorical machine directly from the semantics. The machine is based on relation composition, with a pullback calculation algorithm at its core. The algorithm is defined with the help of a notion of diagram rewriting. In this operational interpretation, types represent information about memory allocation and the execution mechanism is more efficient, thanks to the faithful representation of shared state by categorical projections. We finish the work by illustrating how the categorical semantics allows the incorporation into Prolog of constructs typical of Functional Programming, like abstract data types, and strict and lazy functions.

Comments and remarks over classic linear loop-gain method for oscillator design and analysis. New proposed method based on NDF/RRT

Abstract. This paper describes a new and original method for designing oscillators based on the Normalized Determinant Function (NDF) and Return Relations (RRT)- Firstly, a review of the loop-gain method will be performed. The loop-gain method pros, cons and some examples for exploring wrong solutions provided by this method will be shown. This method produces in some cases wrong solutions because some necessary conditions have not been fulfilled. The required necessary conditions to assure a right solution will be described. The necessity of using the NDF or the Transpose Return Relations (RRT), which are related with the True Loop-Gain, to test the additional conditions will be demonstrated. To conclude this paper, the steps for oscillator design and analysis, using the proposed NDF/RRj method, will be presented. The loop-gain wrong solutions will be compared with the NDF/RRj and the accuracy of this method to estimate the oscillation frequency and QL will be demonstrated. Some additional examples of plane reference oscillators (Z/Y/T), will be added and they will be analyzed with the new NDF/RRj proposed method, even these oscillators cannot be analyzed using the classic loop gain method.

Linear color correction for multiple illumination changes and non-overlapping cameras

Many image processing methods, such as techniques for people re-identification, assume photometric constancy between different images. This study addresses the correction of photometric variations based upon changes in background areas to correct foreground areas. The authors assume a multiple light source model where all light sources can have different colours and will change over time. In training mode, the authors learn per-location relations between foreground and background colour intensities. In correction mode, the authors apply a double linear correction model based on learned relations. This double linear correction includes a dynamic local illumination correction mapping as well as an inter-camera mapping. The authors evaluate their illumination correction by computing the similarity between two images based on the earth mover's distance. The authors compare the results to a representative auto-exposure algorithm found in the recent literature plus a colour correction one based on the inverse-intensity chromaticity. Especially in complex scenarios the authors’ method outperforms these state-of-the-art algorithms.