Constraint qualifications in convex vector semi-infinite optimization

Convex vector (or multi-objective) semi-infinite optimization deals with the simultaneous minimization of finitely many convex scalar functions subject to infinitely many convex constraints. This paper provides characterizations of the weakly efficient, efficient and properly efficient points in terms of cones involving the data and Karush–Kuhn–Tucker conditions. The latter characterizations rely on different local and global constraint qualifications. The results in this paper generalize those obtained by the same authors on linear vector semi-infinite optimization problems.

A multi-depot travelling salesman problem and its iterative and integrated approaches

This paper formulates a logistics distribution problem as the multi-depot travelling salesman problem (MDTSP). The decision makers not only have to determine the travelling sequence of the salesman for delivering finished products from a warehouse or depot to a customer, but also need to determine which depot stores which type of products so that the total travelling distance is minimised. The MDTSP is similar to the combination of the travelling salesman and quadratic assignment problems. In this paper, the two individual hard problems or models are formulated first. Then, the problems are integrated together, that is, the MDTSP. The MDTSP is constructed as both integer nonlinear and linear programming models. After formulating the models, we verify the integrated models using commercial packages, and most importantly, investigate whether an iterative approach, that is, solving the individual models repeatedly, can generate an optimal solution to the MDTSP. Copyright © 2006 Inderscience Enterprises Ltd.

The influence of memory in a threshold model for distributed task assignment

A nature inspired decentralised multi-agent algorithm is proposed to solve a problem of distributed task selection in which cities produce and store batches of different mail types. Agents must collect and process the mail batches, without a priori knowledge of the available mail at the cities or inter-agent communication. In order to process a different mail type than the previous one, agents must undergo a change-over during which it remains inactive. We propose a threshold based algorithm in order to maximise the overall efficiency (the average amount of mail collected). We show that memory, i.e. the possibility for agents to develop preferences for certain cities, not only leads to emergent cooperation between agents, but also to a significant increase in efficiency (above the theoretical upper limit for any memoryless algorithm), and we systematically investigate the influence of the various model parameters. Finally, we demonstrate the flexibility of the algorithm to changes in circumstances, and its excellent scalability.

A new three phase method (SDP method) for the multi-objective vehicle routing problem with simultaneous delvery and pickup (VRPSDP)

Transportation service operators are witnessing a growing demand for bi-directional movement of goods. Given this, the following thesis considers an extension to the vehicle routing problem (VRP) known as the delivery and pickup transportation problem (DPP), where delivery and pickup demands may occupy the same route. The problem is formulated here as the vehicle routing problem with simultaneous delivery and pickup (VRPSDP), which requires the concurrent service of the demands at the customer location. This formulation provides the greatest opportunity for cost savings for both the service provider and recipient. The aims of this research are to propose a new theoretical design to solve the multi-objective VRPSDP, provide software support for the suggested design and validate the method through a set of experiments. A new real-life based multi-objective VRPSDP is studied here, which requires the minimisation of the often conflicting objectives: operated vehicle fleet size, total routing distance and the maximum variation between route distances (workload variation). The former two objectives are commonly encountered in the domain and the latter is introduced here because it is essential for real-life routing problems. The VRPSDP is defined as a hard combinatorial optimisation problem, therefore an approximation method, Simultaneous Delivery and Pickup method (SDPmethod) is proposed to solve it. The SDPmethod consists of three phases. The first phase constructs a set of diverse partial solutions, where one is expected to form part of the near-optimal solution. The second phase determines assignment possibilities for each sub-problem. The third phase solves the sub-problems using a parallel genetic algorithm. The suggested genetic algorithm is improved by the introduction of a set of tools: genetic operator switching mechanism via diversity thresholds, accuracy analysis tool and a new fitness evaluation mechanism. This three phase method is proposed to address the shortcoming that exists in the domain, where an initial solution is built only then to be completely dismantled and redesigned in the optimisation phase. In addition, a new routing heuristic, RouteAlg, is proposed to solve the VRPSDP sub-problem, the travelling salesman problem with simultaneous delivery and pickup (TSPSDP). The experimental studies are conducted using the well known benchmark Salhi and Nagy (1999) test problems, where the SDPmethod and RouteAlg solutions are compared with the prominent works in the VRPSDP domain. The SDPmethod has demonstrated to be an effective method for solving the multi-objective VRPSDP and the RouteAlg for the TSPSDP.

On the k-anonymization of time-varying and multi-layer social graphs

The popularity of online social media platforms provides an unprecedented opportunity to study real-world complex networks of interactions. However, releasing this data to researchers and the public comes at the cost of potentially exposing private and sensitive user information. It has been shown that a naive anonymization of a network by removing the identity of the nodes is not sufficient to preserve users’ privacy. In order to deal with malicious attacks, k -anonymity solutions have been proposed to partially obfuscate topological information that can be used to infer nodes’ identity. In this paper, we study the problem of ensuring k anonymity in time-varying graphs, i.e., graphs with a structure that changes over time, and multi-layer graphs, i.e., graphs with multiple types of links. More specifically, we examine the case in which the attacker has access to the degree of the nodes. The goal is to generate a new graph where, given the degree of a node in each (temporal) layer of the graph, such a node remains indistinguishable from other k-1 nodes in the graph. In order to achieve this, we find the optimal partitioning of the graph nodes such that the cost of anonymizing the degree information within each group is minimum. We show that this reduces to a special case of a Generalized Assignment Problem, and we propose a simple yet effective algorithm to solve it. Finally, we introduce an iterated linear programming approach to enforce the realizability of the anonymized degree sequences. The efficacy of the method is assessed through an extensive set of experiments on synthetic and real-world graphs.

Real-time scheduling of embedded applications on multi-core platforms

For the past several decades, we have experienced the tremendous growth, in both scale and scope, of real-time embedded systems, thanks largely to the advances in IC technology. However, the traditional approach to get performance boost by increasing CPU frequency has been a way of past. Researchers from both industry and academia are turning their focus to multi-core architectures for continuous improvement of computing performance. In our research, we seek to develop efficient scheduling algorithms and analysis methods in the design of real-time embedded systems on multi-core platforms. Real-time systems are the ones with the response time as critical as the logical correctness of computational results. In addition, a variety of stringent constraints such as power/energy consumption, peak temperature and reliability are also imposed to these systems. Therefore, real-time scheduling plays a critical role in design of such computing systems at the system level. We started our research by addressing timing constraints for real-time applications on multi-core platforms, and developed both partitioned and semi-partitioned scheduling algorithms to schedule fixed priority, periodic, and hard real-time tasks on multi-core platforms. Then we extended our research by taking temperature constraints into consideration. We developed a closed-form solution to capture temperature dynamics for a given periodic voltage schedule on multi-core platforms, and also developed three methods to check the feasibility of a periodic real-time schedule under peak temperature constraint. We further extended our research by incorporating the power/energy constraint with thermal awareness into our research problem. We investigated the energy estimation problem on multi-core platforms, and developed a computation efficient method to calculate the energy consumption for a given voltage schedule on a multi-core platform. In this dissertation, we present our research in details and demonstrate the effectiveness and efficiency of our approaches with extensive experimental results.

Simplified PRBMs of spatial compliant multi-beam modules for planar motion

PRBMs (pseudo-rigid-body models) have been becoming important engineering technologies/methods in the field of compliant mechanisms to simplify the design and analysis through the use of the knowledge body of rigid-body mechanisms coupling with springs. This article addresses the PRBMs of spatial multi-beam modules for planar motion, which are composed of three or more symmetrical wire/slender beams parallel to each other where the planar twisting DOF (degree of freedom) is assumed to be very small for specific applications/loading conditions. Simplified PRBMs are firstly proposed through replacing each beam in spatial multi-beam module with a rigid-body link plus two identical spherical joints at its two ends. The characteristics factor, bending stiffness and twisting stiffness for the spherical joint are determined. Load-displacement equations are then derived for a class of spatial multi-beam modules and general spatial multi-beam modules using the virtual work principle and kinematic relationships. Finally, nonlinear FEA (finite element analysis) is employed with comparisons with the PRBMs. The present PRBMs have shown the ability to predict the primary nonlinear constraint characteristics such as load-stiffening effect, cross-axis coupling in the two primary translational directions and buckling load.

The High-Redshift Quasar Luminosity Function from Multi-Epoch Imaging Surveys

Thesis (Ph.D.)--University of Washington, 2016-08

Towards a Multi-device Constraints Solver

To reduce the amount of time needed to solve the most complex Constraint Satisfaction Problems (CSPs) usually multi-core CPUs are used. There are already many applications capable of harnessing the parallel power of these devices to speed up the CSPs solving process. Nowadays, the Graphics Processing Units (GPUs) possess a level of parallelism that surpass the CPUs, containing from a few hundred to a few thousand cores and there are much less applications capable of solving CSPs on GPUs, leaving space for possible improvements. This article describes the work in progress for solving CSPs on GPUs and CPUs and compares results with some state-of-the-art solvers, presenting already some good results on GPUs.

Constraint Programming-based Job Dispatching for Modern HPC Applications

A High-Performance Computing job dispatcher is a critical software that assigns the finite computing resources to submitted jobs. This resource assignment over time is known as the on-line job dispatching problem in HPC systems. The fact the problem is on-line means that solutions must be computed in real-time, and their required time cannot exceed some threshold to do not affect the normal system functioning. In addition, a job dispatcher must deal with a lot of uncertainty: submission times, the number of requested resources, and duration of jobs. Heuristic-based techniques have been broadly used in HPC systems, at the cost of achieving (sub-)optimal solutions in a short time. However, the scheduling and resource allocation components are separated, thus generates a decoupled decision that may cause a performance loss. Optimization-based techniques are less used for this problem, although they can significantly improve the performance of HPC systems at the expense of higher computation time. Nowadays, HPC systems are being used for modern applications, such as big data analytics and predictive model building, that employ, in general, many short jobs. However, this information is unknown at dispatching time, and job dispatchers need to process large numbers of them quickly while ensuring high Quality-of-Service (QoS) levels. Constraint Programming (CP) has been shown to be an effective approach to tackle job dispatching problems. However, state-of-the-art CP-based job dispatchers are unable to satisfy the challenges of on-line dispatching, such as generate dispatching decisions in a brief period and integrate current and past information of the housing system. Given the previous reasons, we propose CP-based dispatchers that are more suitable for HPC systems running modern applications, generating on-line dispatching decisions in a proper time and are able to make effective use of job duration predictions to improve QoS levels, especially for workloads dominated by short jobs.

Distributed Large-scale Mixed-Integer Optimization with Application to Energy and Multi-robot Networks

Several decision and control tasks in cyber-physical networks can be formulated as large- scale optimization problems with coupling constraints. In these "constraint-coupled" problems, each agent is associated to a local decision variable, subject to individual constraints. This thesis explores the use of primal decomposition techniques to develop tailored distributed algorithms for this challenging set-up over graphs. We first develop a distributed scheme for convex problems over random time-varying graphs with non-uniform edge probabilities. The approach is then extended to unknown cost functions estimated online. Subsequently, we consider Mixed-Integer Linear Programs (MILPs), which are of great interest in smart grid control and cooperative robotics. We propose a distributed methodological framework to compute a feasible solution to the original MILP, with guaranteed suboptimality bounds, and extend it to general nonconvex problems. Monte Carlo simulations highlight that the approach represents a substantial breakthrough with respect to the state of the art, thus representing a valuable solution for new toolboxes addressing large-scale MILPs. We then propose a distributed Benders decomposition algorithm for asynchronous unreliable networks. The framework has been then used as starting point to develop distributed methodologies for a microgrid optimal control scenario. We develop an ad-hoc distributed strategy for a stochastic set-up with renewable energy sources, and show a case study with samples generated using Generative Adversarial Networks (GANs). We then introduce a software toolbox named ChoiRbot, based on the novel Robot Operating System 2, and show how it facilitates simulations and experiments in distributed multi-robot scenarios. Finally, we consider a Pickup-and-Delivery Vehicle Routing Problem for which we design a distributed method inspired to the approach of general MILPs, and show the efficacy through simulations and experiments in ChoiRbot with ground and aerial robots.

Distributed collision-free traffic management via vertex cover for multi-vehicle systems

In this thesis, we state the collision avoidance problem as a vertex covering problem, then we consider a distributed framework in which a team of cooperating Unmanned Vehicles (UVs) aim to solve this optimization problem cooperatively to guarantee collision avoidance between group members. For this purpose, we implement a distributed control scheme based on a robust Set-Theoretic Model Predictive Control ( ST-MPC) strategy, where the problem involves vehicles with independent dynamics but with coupled constraints, to capture required cooperative behavior.

Doehlert Design-desirability Function Multi-criteria Optimal Separation Of 17 Phenolic Compounds From Extra-virgin Olive Oil By Capillary Zone Electrophoresis.

In Brazil, the consumption of extra-virgin olive oil (EVOO) is increasing annually, but there are no experimental studies concerning the phenolic compound contents of commercial EVOO. The aim of this work was to optimise the separation of 17 phenolic compounds already detected in EVOO. A Doehlert matrix experimental design was used, evaluating the effects of pH and electrolyte concentration. Resolution, runtime and migration time relative standard deviation values were evaluated. Derringer's desirability function was used to simultaneously optimise all 37 responses. The 17 peaks were separated in 19min using a fused-silica capillary (50μm internal diameter, 72cm of effective length) with an extended light path and 101.3mmolL(-1) of boric acid electrolyte (pH 9.15, 30kV). The method was validated and applied to 15 EVOO samples found in Brazilian supermarkets.

Auxin And Physical Constraint Exerted By The Perianth Promote Androgynophore Bending In Passiflora Mucronata L. (passifloraceae).

The androgynophore column, a distinctive floral feature in passion flowers, is strongly crooked or bent in many Passiflora species pollinated by bats. This is a floral feature that facilitates the adaptation to bat pollination. Crooking or bending of plant organs are generally caused by environmental stimulus (e.g. mechanical barriers) and might involve the differential distribution of auxin. Our aim was to study the role of the perianth organs and the effect of auxin in bending of the androgynophore of the bat-pollinated species Passiflora mucronata. Morpho-anatomical characterisation of the androgynophore, including measurements of curvature angles and cell sizes both at the dorsal (convex) and ventral (concave) sides of the androgynophore, was performed on control flowers, flowers from which perianth organs were partially removed and flowers treated either with auxin (2,4-dichlorophenoxyacetic acid; 2,4-D) or with an inhibitor of auxin polar transport (naphthylphthalamic acid; NPA). Asymmetric growth of the androgynophore column, leading to bending, occurs at a late stage of flower development. Removing the physical constraint exerted by perianth organs or treatment with NPA significantly reduced androgynophore bending. Additionally, the androgynophores of plants treated with 2,4-D were more curved when compared to controls. There was a larger cellular expansion at the dorsal side of the androgynophores of plants treated with 2,4-D and in both sides of the androgynophores of plants treated with NPA. This study suggests that the physical constraint exerted by perianth and auxin redistribution promotes androgynophore bending in P. mucronata and might be related to the evolution of chiropterophily in the genus Passiflora.

Behavior Of Listeria Monocytogenes In A Multi-species Biofilm With Enterococcus Faecalis And Enterococcus Faecium And Control Through Sanitation Procedures.

The formation of mono-species biofilm (Listeria monocytogenes) and multi-species biofilms (Enterococcus faecium, Enterococcus faecalis, and L. monocytogenes) was evaluated. In addition, the effectiveness of sanitation procedures for the control of the multi-species biofilm also was evaluated. The biofilms were grown on stainless steel coupons at various incubation temperatures (7, 25 and 39°C) and contact times (0, 1, 2, 4, 6 and 8days). In all tests, at 7°C, the microbial counts were below 0.4 log CFU/cm(2) and not characteristic of biofilms. In mono-species biofilm, the counts of L. monocytogenes after 8days of contact were 4.1 and 2.8 log CFU/cm(2) at 25 and 39°C, respectively. In the multi-species biofilms, Enterococcus spp. were present at counts of 8 log CFU/cm(2) at 25 and 39°C after 8days of contact. However, the L. monocytogenes in multi-species biofilms was significantly affected by the presence of Enterococcus spp. and by temperature. At 25°C, the growth of L. monocytogenes biofilms was favored in multi-species cultures, with counts above 6 log CFU/cm(2) after 8days of contact. In contrast, at 39°C, a negative effect was observed for L. monocytogenes biofilm growth in mixed cultures, with a significant reduction in counts over time and values below 0.4 log CFU/cm(2) starting at day 4. Anionic tensioactive cleaning complemented with another procedure (acid cleaning, disinfection or acid cleaning+disinfection) eliminated the multi-species biofilms under all conditions tested (counts of all micro-organisms<0.4 log CFU/cm(2)). Peracetic acid was the most effective disinfectant, eliminating the multi-species biofilms under all tested conditions (counts of the all microorganisms <0.4 log CFU/cm(2)). In contrast, biguanide was the least effective disinfectant, failing to eliminate biofilms under all the test conditions.