Solving problems of discrete tomography

This is a summary of the most important results presented in the author's PhD thesis. This thesis, written in French, was defended on 24 November 2004 and supervised by Marie-Christine Costa and Christophe Picouleau. This thesis consists in developing the study of discrete tomography problems. It aims at reconstructing discrete objects (matrices, images, discrete sets, etc) that are accessible only through few projections. A copy of the thesis is available on "http: //cedric.cnam.fr/AfficheArticle.php?id = 698". Received: April 2005 AMS classification: 90B70, 68Q17, 52C15, 05B50     

An Iterative Exact Solution for the Dual Power Management Problem in Wireless Sensor Network

We study the dual power management problem in wireless sensor networks. Given a wireless sensor network with two possible power levels (heigh and low) for each sensor, the problem consists in minimizing the number of sensors assigned heigh power while ensuring the connectivity of the network. We formulate the problem by a binary integer programming model to minimize the total power consumption. Since the problem is NP-complete, we provide an iterative approximation based on iterative methods in combinatorial optimization. We solve the separation subproblem as a minimum spanning tree.     

An acyclic days-off scheduling problem

This paper studies the days off scheduling problem when the demand for staffing fluctuates from day to another and when the number of total workdays is fixed in advance for each employee. The scheduling problem is then to allocate rests to employees with different days off policies: (1) two or three consecutive days off for each employee per week and (2) at least three consecutive days off for each employee per month. For each one, we propose a polynomial time algorithm to construct a solution if it exists. Received: April 2005 / Revised version: October 2005 AMS classification: 60K25, 60K30     

CO<Subscript>2</Subscript>-Expanded Alkyl Lactates: A Physicochemical and Molecular Modeling Study

With the perspective of finding alternative benign media for various applications, this paper presents a study of the physicochemical behavior of some members of the alkyl lactate family when expanded by CO₂. Experimental and molecular modeling techniques have been used to determine and/or predict relevant physicochemical properties of these systems such as swelling, Kamlet–Taft parameters {polarity/polarizability (π*) and proticity or hydrogen-bond donator ability (α), dielectric constants and solubility parameters}. To complete the study of these properties, sigma profiles of the three lactates molecules have been obtained by performing quantum mechanical and phase equilibria calculations of CO₂/alkyl lactate systems by using the Peng–Robinson equation of state.     

Reconstructing Convex Matrices by Integer Programming Approaches

We consider the problem of reconstructing two-dimensional convex binary matrices from their row and column sums with adjacent ones. Instead of requiring the ones to occur consecutively in each row and column, we maximize the number of adjacent ones. We reformulate the problem by using integer programming and we develop approximate solutions based on linearization and convexification techniques.     

Thermal and mechanical behavior of amorphous and semi-crystalline poly(vinylidene fluoride)/poly(methyl methacrylate) blends

Various PVDF/PMMA (poly(vinylidene fluoride)/poly(methyl methacrylate)) blends were selected for mechanical testing in compression. At low PVDF content (less than 50/50 w/w), the blends remain amorphous and PVDF and PMMA are fully miscible. In PVDF-richer blends, PVDF crystallizes in part, leading to a PMMA-enriched homogeneous amorphous phase. In this study, the degree of crystallinity was set at equilibrium by appropriate annealing of the samples before testing. Mechanical analysis was focused on the low deformation range, and especially on the yield region. Depending on the test temperature and blend composition, three types of response were identified, depending on whether plastic deformation is influenced: 1) by the PMMA secondary relaxation motions, 2) by the PVDF/PMMA glass transition motions, or 3) by the crystallite-constrained PVDF chains.     

A Lagrangean-based heuristics for the target covering problem in wireless sensor network

We study the target coverage problem in wireless sensor networks. The problem consists in maximizing the network lifetime by grouping the sensors in disjoint set covers of the targets. A binary integer programing model is formulated to maximize the network lifetime. Since the problem is NP-complete, we provide an iterative approximation based on Lagrangean relaxation and subgradient optimization.