MPI parallel programming of mixed integer optimization problems using CPLEX with COIN-OR

The aim of this technical report is to present some detailed explanations in order to help to understand and use the Message Passing Interface (MPI) parallel programming for solving several mixed integer optimization problems. We have developed a C++ experimental code that uses the IBM ILOG CPLEX optimizer within the COmputational INfrastructure for Operations Research (COIN-OR) and MPI parallel computing for solving the optimization models under UNIX-like systems. The computational experience illustrates how can we solve 44 optimization problems which are asymmetric with respect to the number of integer and continuous variables and the number of constraints. We also report a comparative with the speedup and efficiency of several strategies implemented for some available number of threads.

Scenario Cluster Lagrangian Decomposition in two stage stochastic mixed 0-1 optimization

In this paper we introduce four scenario Cluster based Lagrangian Decomposition (CLD) procedures for obtaining strong lower bounds to the (optimal) solution value of two-stage stochastic mixed 0-1 problems. At each iteration of the Lagrangian based procedures, the traditional aim consists of obtaining the solution value of the corresponding Lagrangian dual via solving scenario submodels once the nonanticipativity constraints have been dualized. Instead of considering a splitting variable representation over the set of scenarios, we propose to decompose the model into a set of scenario clusters. We compare the computational performance of the four Lagrange multiplier updating procedures, namely the Subgradient Method, the Volume Algorithm, the Progressive Hedging Algorithm and the Dynamic Constrained Cutting Plane scheme for different numbers of scenario clusters and different dimensions of the original problem. Our computational experience shows that the CLD bound and its computational effort depend on the number of scenario clusters to consider. In any case, our results show that the CLD procedures outperform the traditional LD scheme for single scenarios both in the quality of the bounds and computational effort. All the procedures have been implemented in a C++ experimental code. A broad computational experience is reported on a test of randomly generated instances by using the MIP solvers COIN-OR and CPLEX for the auxiliary mixed 0-1 cluster submodels, this last solver within the open source engine COIN-OR. We also give computational evidence of the model tightening effect that the preprocessing techniques, cut generation and appending and parallel computing tools have in stochastic integer optimization. Finally, we have observed that the plain use of both solvers does not provide the optimal solution of the instances included in the testbed with which we have experimented but for two toy instances in affordable elapsed time. On the other hand the proposed procedures provide strong lower bounds (or the same solution value) in a considerably shorter elapsed time for the quasi-optimal solution obtained by other means for the original stochastic problem.

On parallel computing for stochastic optimization models and algorithms

167 p.

Desarrollo de software para la realización de ensayos dinámicos de mecanismos de cinemática paralela

[ES]El presente Trabajo de Fin de Grado tiene como objetivo contribuir al desarrollo de un proyecto de investigación mediante la programación y control del movimiento de mecanismos de cinemática paralela para la realización de ensayos dinámicos. Dicho proyecto está enmarcado dentro de una línea de investigación del grupo de investigación CompMech de la UPV-­‐EHU que gira en torno al desarrollo y estudio de este tipo de mecanismos. Esto es; este trabajo, más allá de la utilidad que pudiera tener por sí mismo, está pensado para formar parte de un proyecto de mayor envergadura, para cuyo éxito será imprescindible la colaboración con otros investigadores y la integración de este trabajo con los realizados por ellos. Consiste en la creación de un software para el control y movimiento de mecanismos, generando vibraciones para la realización de ensayos dinámicos. Para ello, se programarán sobre la plataforma LabVIEW la interfaz de usuario y el motor de cálculo. Una vez se compruebe que el programa funciona correctamente, se integrará dentro de un programa principal, un control articular que será el encargado de comunicarse con la máquina. Posteriormente, se procederá a la realización de ensayos experimentales sobre los propios robots, en taller. Se tomarán medidas mediante acelerómetros y otros dispositivos, determinando las medidas más adecuadas para su correcta validación. Finalmente, se generalizará el trabajo realizado para posibilitar su empleo futuro en diferentes mecanismos

Optimisation of the first principle code Octopus for massive parallel architectures: application to light harvesting complexes

150 p.

Structural Synthesis of 3-DoF Spatial Fully Parallel Manipulators

In this paper, the architectures of three degrees of freedom (3-DoF) spatial, fully parallel manipulators (PMs), whose limbs are structurally identical, are obtained systematically. To do this, the methodology followed makes use of the concepts of the displacement group theory of rigid body motion. This theory works with so-called 'motion generators'. That is, every limb is a kinematic chain that produces a certain type of displacement in the mobile platform or end-effector. The laws of group algebra will determine the actual motion pattern of the end-effector. The structural synthesis is a combinatorial process of different kinematic chains' topologies employed in order to get all of the 3-DoF motion pattern possibilities in the end-effector of the fully parallel manipulator.

Análisis cinemático de una máquina de cinemática híbrida XY3PRS.

[Es]El objetivo principal de este Trabajo Fin de Grado consiste en calcular los movimientos que son necesarios en los actuadores de la plataforma de un mecanismo de cinemática paralela, a fin de poder localizar la pieza en la posición adecuada para poder llevar a cabo la operación de microfresado de la misma. Para desarrollar el proyecto se necesitará un software de programación como es Matlab. Este trabajo surge de la necesidad de dar soporte a un proyecto mayor que consiste en el diseño de un manipulador de cinemática paralela cuyas juntas funcionan por deformación. Se pretende que mientras la herramienta se encuentra inmóvil, se consiga el microfresado de moldes para la fabricación de microlentes mediante el movimiento del manipulador. Se ha resuelto la cinemática inversa y se ha calculado el espacio de trabajo. En este documento se van a presentar las tareas, el presupuesto y los riesgos del proyecto así como unos anexos en los que se incluirá el código de la programación.

Dimensionamiento geométrico y resistente de manipulador paralelo XY.

[ES]Se trata de diseñar, programar, fabricar y montar un manipulador paralelo de 5 pares de revolución, que sirva para el atrape y posterior desplazamiento de objetos pequeños en un área de trabajo determinado. Este proyecto se centra exclusivamente en el análisis cinemático, resistente y posterior optimización del diseño del mecanismo de barras del manipulador.

Distribution of Healthcare resources II.Study and Comparison of a Linear Programming Problem and its Dual. Resolution and Evaluation of a Practical Case and its Programming using Excel and Win QSB.

[EN]This research had as primary objective to model different types of problems using linear programming and apply different methods so as to find an adequate solution to them. To achieve this objective, a linear programming problem and its dual were studied and compared. For that, linear programming techniques were provided and an introduction of the duality theory was given, analyzing the dual problem and the duality theorems. Then, a general economic interpretation was given and different optimal dual variables like shadow prices were studied through the next practical case: An aesthetic surgery hospital wanted to organize its monthly waiting list of four types of surgeries to maximize its daily income. To solve this practical case, we modelled the linear programming problem following the relationships between the primal problem and its dual. Additionally, we solved the dual problem graphically, and then we found the optimal solution of the practical case posed through its dual, following the different theorems of the duality theory. Moreover, how Complementary Slackness can help to solve linear programming problems was studied. To facilitate the solution Solver application of Excel and Win QSB programme were used.