Search

In this article, we focus on a periodic resource allocation problem applied on a dynamical system which comes from a biological system. More precisely, we consider a system with N$$ N $$ resources and N$$ N $$ activities, each activity use the allocated resource to evolve up to a given time T>0$$ T>0 $$ where a control (represented by a given permutation) will be applied on the system to reallocate the resources. The goal is to find the optimal control strategies which optimize the cost or the benefit of the system. This problem can be illustrated by an industrial biological application, namely, the optimization of a mixing strategy to enhance the growth rate in a microalgal raceway system. A mixing device, such as a paddle wheel, is considered to control the rearrangement of the depth of the algae cultures, hence the light perceived at each lap. We prove that if the dynamics of the system is periodic, then the period corresponds to one reallocation whatever the order of the involved permutation matrix is. A nonlinear optimization problem for one reallocation process is then introduced. Since N!$$ N! $$ permutations need to be tested in the general case, it can be numerically solved only for a limited number of N$$ N $$. To overcome this difficulty, we introduce a second optimization problem which provides a suboptimal solution of the initial problem, but whose solution can be determined explicitly. A sufficient condition to characterize cases where the two problems have the same solution is given. Some numerical experiments are performed to assess the benefit of optimal strategies in various settings. [ABSTRACT FROM AUTHOR]

We address a novel ride‐sharing model aiming to improve the quality of carpool services, by means of incorporation of passengers' efforts. In densely populated areas, locating and picking up passengers are often time costly. These phenomena, which are rarely considered in literature, will hurdle the service efficiency of ride‐sharing businesses by a significant amount, and contribute to the performance gap between theoretical estimation and practical performance. We notice that major platforms, such as DiDi, Uber, and Lyft are all starting innovative ways to encourage passengers to take efforts to walk to the assigned stations. We present a static optimization model for the planning stage of the service and establish an estimation of the carpooling rate for each station together with robustness consideration. In addition, we provide simple and efficient optimization algorithms with theoretical performance guarantee. At the same time, we conduct simulation studies based on both random generated data and open accessible data from DiDi. By applying our model and algorithm to the data of DiDi, we can achieve carpooling rates of 90% while passengers are located within an average radius of 250 m spending an extra waiting time of less than 3 min for their shared rides during rush hour. [ABSTRACT FROM AUTHOR]

We study a multi-stage dynamic assignment interdiction (DAI) game in which two agents, a user and an attacker, compete in the underlying bipartite assignment graph. The user wishes to assign a set of tasks at the minimum cost, and the attacker seeks to interdict a subset of arcs to maximize the user's objective. The user assigns exactly one task per stage, and the assignment costs and interdiction impacts vary across stages. Before any stage commences in the game, the attacker can interdict arcs subject to a cardinality constraint. An interdicted arc can still be used by the user, but at an increased assignment cost. The goal is to find an optimal sequence of assignments, coupled with the attacker's optimal interdiction strategy. We prove that this problem is strongly NP-hard, even when the attacker can interdict only one arc. We propose an exact exponential-state dynamic-programming algorithm for this problem as well as lower and upper bounds on the optimal objective function value. Our bounds are based on classical interdiction and robust optimization models, and on variations of the DAI game. We examine the efficiency of our algorithms and the quality of our bounds on a set of randomly generated instances. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 373-387, 2017 [ABSTRACT FROM AUTHOR]

The moist available potential energy (MAPE) of a domain of air is defined as the maximum amount of kinetic energy that can be released through reversible adiabatic motions of its air parcels. The MAPE can be calculated using a parcel-moving algorithm that finds the minimum enthalpy state for a given set of thermodynamic assumptions. However, the parcel-moving algorithms proposed previously do not always find the minimum enthalpy state. In this article, we apply the Munkres algorithm to find the exact minimum enthalpy state and compare this exact algorithm with four inexact algorithms, including a new divide-and-conquer algorithm. The divide-and-conquer algorithm performs well in practice, while being simpler and faster than the Munkres algorithm, and it is recommended for future calculation of MAPE when the exact result is not required. [ABSTRACT FROM AUTHOR]

ABSTRACT This article describes a practical methodology for assigning students to groups where the goal is to create diversity within the groups while taking into consideration the preferences of the students. A motivating application of this work is the assignment of students to first-year seminars. In this common scenario, students select and rank a small subset of seminars from the list of those available. The academic institution then attempts to assign students to a seminar on their list, while maintaining course capacities. Faculty are interested in having seminars that are balanced with regards to gender and the number of international students, while students are interested in being assigned to one of their higher ranked seminars. In this article, we develop a simple multi-objective convex quadratic program that can determine assignments that are well balanced and satisfy the highest preferences of the students. The advantage of our approach is that the model can be submitted directly to a standard optimization software package, eliminating the need for a specialized algorithm. [ABSTRACT FROM AUTHOR]

A post-hoc individual patient matching procedure was recently proposed within the context of parallel group randomized clinical trials (RCTs) as a method for estimating treatment effect. In this paper, we consider a post-hoc individual patient matching problem within a parallel group RCT as a multi-objective decision-making problem focussing on the trade-off between the quality of individual matches and the overall percentage of matching. Using acute stroke trials as a context, we utilize exact optimization and simulation techniques to investigate a complex relationship between the overall percentage of individual post-hoc matching, the size of the respective RCT, and the quality of matching on variables highly prognostic for a good functional outcome after stroke, as well as the dispersion in these variables. It is empirically confirmed that a high percentage of individual post-hoc matching can only be achieved when the differences in prognostic baseline variables between individually matched subjects within the same pair are sufficiently large and that the unmatched subjects are qualitatively different to the matched ones. It is concluded that the post-hoc individual matching as a technique for treatment effect estimation in parallel-group RCTs should be exercised with caution because of its propensity to introduce significant bias and reduce validity. If used with appropriate caution and thorough evaluation, this approach can complement other viable alternative approaches for estimating the treatment effect. Copyright © 2013 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

We consider a transportation problem where the cost matrix satisfies the Monge property. The problem has supply nodes N1(| N1| = n1), demand nodes N2(| N2| = n2), supply s i ≥ 0 for i∈ N1, and demand d j ≥ 0 for j∈ N2( n = n1 + n2, m = n1 n2). When the total supply is equal to the total demand, the problem can be solved in O( n) time using the northwest corner rule (Hoffman [10]). This algorithm and run-time, however, do not extend to the unbalanced case, where the total supply is not equal to the total demand. The fastest strongly polynomial run-time for the unbalanced transportation problem with Monge costs is O( nlog n( m + nlog n)), and for the unbalanced assignment problem (unit supplies and demands) with Monge costs is O( n( m + nlog n)). In this article, we describe a simple algorithm that solves the unbalanced transportation problem with Monge costs in O( mn1) time and the unbalanced assignment problem with Monge costs in O( m) time using elementary data structures. We also develop a faster implementation of the algorithm that utilizes a heap, a self-balancing binary search tree, and dynamic trees, and solves the transportation problem with Monge costs in O( mlog n1) time. Our algorithms improve the run-times for: (i) the unbalanced transportation problem with Monge costs by a factor of nlog n/log n1 or better and (ii) the unbalanced assignment problem with Monge costs by a factor of n or better. © 2013 Wiley Periodicals, Inc. NETWORKS, 2013 [ABSTRACT FROM AUTHOR]

• Measures of diversity within populations, and distance between populations, are compared for organisms with an asexual or mixed mode of reproduction. Examples are drawn from studies of plant pathogenic fungi based on binary traits including presence/absence of DNA bands or virulence/avirulence to differential hosts. • Commonly used measures of population diversity or genetic distance consider either genotype frequencies or allele frequencies. Kosman's diversity and distance measures are the most suitable for populations with an asexual or mixed mode of reproduction, because by considering genetic patterns of all individuals they take into account not just the genotype frequencies but also the genetic similarities between genotypes in the populations. • The Kosman distance and diversity measures for populations can be calculated using different measures of dissimilarity between individuals (the simple mismatch, Jaccard and Dice coefficients of dissimilarity). Kosman's distances based on the simple mismatch and Jaccard dissimilarities are metrics. • Comparisons of diversity indices for hypothetical examples as well as for actual data sets are presented to demonstrate that inferences from diversity analysis of populations can be driven by techniques of diversity and distance assessments and not only data driven. [ABSTRACT FROM AUTHOR]

In this paper, the author proposes a data structure and approximate solution for solving a large-scale generalized assignment problem, being a constraint satisfaction problem. To find a desired solution from among many executable solutions, the proposed algorithm sets a priority order for resources and repeatedly solves an integer programming problem in order to reduce the nonexecutable sum of constraints. This study is an analysis of what type of data structure may be effective in raising the cache memory hit rate when a two-dimensional matrix 0–1 assignment variable xij, which frequently crops up in the field of operations research, has large-scale sparsity. The proposed algorithm constructs multiple search trees, makes searches and examines which resource assignments must be changed, and retains information from the search as an arc. Two-fold “garbage collection” is performed to avoid the fragmentation of the memory necessary for the search, when performing a state space search using multiple search trees. Furthermore, a data structure necessary for the searches, in order to apply the proposed algorithm to a real large-scale problem, is described. © 2007 Wiley Periodicals, Inc. Syst Comp Jpn, 38(3): 83–91, 2007; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/scj.10272 [ABSTRACT FROM AUTHOR]

Determining true genetic dissimilarity between individuals is an important and decisive point for clustering and analysing diversity within and among populations, because different dissimilarity indices may yield conflicting outcomes. We show that there are no acceptable universal approaches to assessing the dissimilarity between individuals with molecular markers. Different measures are relevant to dominant and codominant DNA markers depending on the ploidy of organisms. The Dice coefficient is the suitable measure for haploids with codominant markers and it can be applied directly to (0,1)-vectors representing banding profiles of individuals. None of the common measures, Dice, Jaccard, simple mismatch coefficient (or the squared Euclidean distance), is appropriate for diploids with codominant markers. By transforming multiallelic banding patterns at each locus into the corresponding homozygous or heterozygous states, a new measure of dissimilarity within locus was developed and expanded to assess dissimilarity between multilocus states of two individuals by averaging across all codominant loci tested. There is no rigorous well-founded solution in the case of dominant markers. The simple mismatch coefficient is the most suitable measure of dissimilarity between banding patterns of closely related haploid forms. For distantly related haploid individuals, the Jaccard dissimilarity is recommended. In general, no suitable method for measuring genetic dissimilarity between diploids with dominant markers can be proposed. Banding patterns of diploids with dominant markers and polyploids with codominant markers represent individuals’ phenotypes rather than genotypes. All dissimilarity measures proposed and developed herein are metrics. [ABSTRACT FROM AUTHOR]

Given a finite set of alternatives, the sorting (or assignment) problem consists in the assignment of each alternative to one of the predefined categories. In this paper, we are interested in multiple criteria sorting problems and, more precisely, in the existing method ELECTRE TRI. This method requires the elicitation of preferential parameters (importance coefficients, thresholds, profiles, etc.) in order to construct the decision-maker's (DM) preference model. A direct elicitation of these parameters being sometimes difficult, Mousseau and Slowinski proposed an interactive aggregation–disaggregation approach that infer ELECTRE TRI parameters indirectly from holistic information, i.e. assignment examples. In this approach, the determination of ELECTRE TRI parameters that best restore the assignment examples is formulated through a non-linear optimization program. Also in this direction, Mousseau et al. considered the subproblem of the determination of the importance coefficients only (the thresholds and category limits being fixed). This subproblem leads to solve a linear program (rather that non-linear in the global inference model). We pursue the idea of partial inference model by considering the complementary subproblem which determines the category limits (the importance coefficients being fixed). With some simplification, it also leads to solve a linear program. Together with the result of Mousseau et al., we have a couple of complementary models which can be combined in an interactive approach inferring the parameters of an ELECTRE TRI model from assignment examples. In each interaction, the DM can revise his/her assignment examples, to give additional information and to choose which parameters to fix before the optimization phase restarts. Copyright © 2002 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

Conference organizers often face the following problem: Given a collection of submitted papers, select a subset to be presented at the conference. The bulk of the work often amounts to assembling a pool of reviewers and then sending each submitted paper to several reviewers. We present in this paper a technique for finding a good assignment of papers to reviewers. An important feature of the solution we find is that each paper is sent to at least one reviewer who is "as expert as possible" for that paper. A major component of the problem is modeled as a bottleneck version of a capacitated transshipment problem. [ABSTRACT FROM AUTHOR]

We have studied the problem of assign elements to an ordered sequence of stations such that the precedence relations are satisfied. At this time, we can obtain the best evaluation value decided under certain constrained conditions to the assignment. This kind of problem includes the line balancing problem. In addition, this can be adjusted to various problems by changing the constrained condition and objective function. These problems can be shown as sequential partitions of the nodes of a directed acyclic graph into subsets. We especially consider the problem of finding a minimum total cost of the cut edge under the restriction of the size of block. In this paper, we propose the general framework for sequential partitions of directed acyclic graphs. We also describe an efficient algorithm that can be used to reduce computational requirements and, possibly, storage. We estimate that the complexity of the algorithm is the polynomial order, if structure of directed acyclic graphs is near parallel. © 1997 Scripta Technica, Inc. Electr Eng Jpn, 121(2): 54–62, 1997 [ABSTRACT FROM AUTHOR]

This paper espouses the application of orthogonal array experiment to solve a class of engineering optimization problems encountered in systems engineering and architecting. It also illustrates the applicability of orthogonal array experiment in systems engineering and architecting with two examples: verification and validation of the performance of a bandwidth allocation algorithm and architecting of a system of systems to respond to small boat attacks by terrorists. The orthogonal array experiment approach does not call for linearization of nonlinear engineering optimization problems; using orthogonal arrays, it solves them directly by carrying out the smallest possible number of experiments and determining their solutions from the results of the experiments. The orthogonal array experiment method has been found to be effective and efficient for these problems. The feasibility of applying the orthogonal array experiment approach to these problems suggests its potential application to other optimization problems encountered in systems engineering and architecting. © 2010 Wiley Periodicals, Inc. Syst Eng 14: 208-222, 2011 [ABSTRACT FROM AUTHOR]