A novel approach for detecting multiple rumor sources in networks with partial observations

Locating source of information diffusion in networks has very important applications such as locating the sources of epidemics, news/rumors in social networks or online computer virus. In this paper, we consider detecting multiple rumor sources from a deterministic point of view by modeling it as the set resolving set (SRS) problem. Let G be a network on n nodes. A node subset K is an SRS of G if all detectable node sets are distinguishable by K. The problem of multiple rumor source detection (MRSD) in the network can be modeled as finding an SRS K with the smallest cardinality. In this paper, we propose a polynomial-time greedy algorithm for finding a minimum SRS in a general network, achieving performance ratio \(O(\ln n)\). This is the first work establishing a relation between the MRSD problem and a deterministic concept of SRS, and a first work to give the minimum SRS problem a polynomial-time performance-guaranteed approximation algorithm. Our framework suggests a robust and efficient approach for estimating multiple rumor sources independent of diffusion models in networks.     

A production engineering approach to robot selection

The successful introduction of robots into an industrial enterprise means real commitment, engineering support, and detailed involvement in the planning of an integrated manufacturing system. In particular, the production engineer is clearly seen in this context to be the system designer. He must therefore be in a position to specify the performance of all man and machine components within the system such that productivity is maximised. Robot types are reviewed, and analogies between man and machine are used to introduce the RTM concept. Finally, a simple method is given for estimating robot throughput times from elementary velocity profiles. The fall-off in throughput due to the effect of many small robot movements is emphasised.     

A heuristic approach to long-haul freight transportation with multiple objective functions

This paper studies a long-haul freight transportation problem stimulated by a real-life application, whose underlying vehicle routing problem is a multi-objective one, where travel time and route cost are to be minimized together with the maximization of a transportation mean sharing index, related to the capability of the transportation system of generating economy scale solutions. In terms of constraints, besides vehicle capacity and time windows, transportation jobs have to obey additional constraints related to mandatory nodes (e.g., logistic platform nearest to the origin or the destination) and forbidden nodes (e.g., logistic platforms not compatible with the operations required). Based on the network definition, routes can be multimodal. To solve this problem, we propose a heuristic algorithm that can be applied in the tactical and the operational planning phase, and present the results of an extensive experimentation.     

Supplier selection with multiple criteria in volume discount environments

Supplier selection is a multi-criteria decision making problem which includes both qualitative and quantitative factors. In order to select the best suppliers it is necessary to make a trade-off between these tangible and intangible factors some of which may conflict. When business volume discounts exist, this problem becomes more complicated as, in these circumstances, buyer should decide about two problems: which suppliers are the best and how much should be purchased from each selected supplier. In this article an integrated approach of analytical hierarchy process improved by rough sets theory and multi-objective mixed integer programming is proposed to simultaneously determine the number of suppliers to employ and the order quantity allocated to these suppliers in the case of multiple sourcing, multiple products, with multiple criteria and with supplier's capacity constraints. In this context, suppliers offer price discounts on total business volume, not on the quantity or variety of products purchased from them. A solution methodology is presented to solve the multi-objective model, and the model is illustrated using two numerical examples.     

Multi-site aggregate production planning with multiple objectives: A goal programming approach

This paper addresses the problem of aggregate production planning (APP) for a multinational lingerie company in Hong Kong. The multi-site production planning problem considers the production loading plans among manufacturing factories subject to certain restrictions, such as production import/export quotas imposed by regulatory requirements of different nations, the use of manufacturing factories/locations with regard to customers' preferences, as well as production capacity, workforce level, storage space and resource conditions of the factories. In this paper, a multi-objective model is developed to solve the production planning problems, in which the profit is maximized but production penalties resulting from going over/under quotas and the change in workforce level are minimized. To enhance the practical implications of the proposed model, different managerial production loading plans are evaluated according to changes in future policy and situation. Numerical results demonstrate the robustness and effectiveness of the developed model.     

An application of multiple objective linear programming to media selection

A multiple objective linear programming (MOLP) method utilizing interval criterion weights is applied to the problem of media selection. Using this technique, it is possible to analyze a problem more explicitly in terms of the several objectives inherent in many media selection situations. In order to illustrate the interval criterion weights approach, a multiple objective hierarchical media selection model is presented and its computer results discussed. In addition to being able to deal more directly with different decision criteria, a distinguishing feature of the mathematical analysis applied here is that its output enables the media-planner to be presented with a small cluster of candidate media schedules (rather than just one). Then, from this list, the media-planner should be in a position to qualitatively make a final choice as a close approximation to his optimal solution.     

A zero-one goal programming approach for information system project selection

This paper presents a multi-objective model that can be used to help information systems (IS) managers decide which IS projects should be selected for development and implementation in a constrained resource environment. Developed to overcome the problems observed in currently used IS selection procedures, the model presented in this paper can be used to make decisions when IS selection goals are conflicting and measured in incommensurable units. To illustrate the use of this multi-objective approach to model IS project selection, a corporate resource allocation problem is developed and solved. Comparative results with currently used scoring and ranking methods reveals the superiority of the proposed multi-objective model.     

A novel portfolio selection model in a hybrid uncertain environment

The future returns of each securities cannot be correctly reflected by the securities data in the past, therefore the statistical techniques and the experts’ judgement and experience are combined together to estimate the security returns in the future. In this paper, the returns of each securities are assumed to be fuzzy random variables, then following the ideas of mean variance model a new portfolio selection model in a hybrid uncertain environment is proposed. Moreover, the λ-mean variance efficient frontiers and λ-mean variance efficient portfolios are defined, and the properties of λ-mean variance efficient portfolios located on different λ-mean variance efficient frontiers are discussed. Finally, a numerical example is presented to illustrate the proposed portfolio selection model. On the basis of the results, we can conclude that the proposed model can provide the more flexible results.     

Rough set-based approach to feature selection in customer relationship management

In this paper, application of the rough set theory (RST) to feature selection in customer relationship management (CRM) is introduced. Compared to other methods, the RST approach has the advantage of combining both qualitative and quantitative information in the decision analysis, which is extremely important for CRM. To derive the decision rules from historical data for identifying features that contribute to CRM, both the mathematical formulation and the heuristic algorithm are developed in this paper. The proposed algorithm is comprised of both equal and unequal weight cases of the feature content with the limitation of the mathematical models. This algorithm is able to derive the rules and identify the most significant features simultaneously, which is unique and useful in solving CRM problems. A case study of a video game system purchase is validated by historical data, and the results showed the practical viability of the RST approach for predicting customer purchasing behavior. This paper forms the basis for solving many other similar problems that occur in the service industry.     

A qualitative perspective to deriving weights from pairwise comparison matrices

Deriving weights from pairwise comparison matrices (PCM) is a highly researched topic. The analytic hierarchy process (AHP) traditionally uses the eigenvector method for the purpose. Numerous other methods have also been suggested. A distinctive feature of all these methods is that they associate a quantitative meaning to the judgemental information given by the decision-maker. In contrast, the verbal scale used in AHP to capture judgements does not associate such a quantitative meaning. Though this issue of treating judgements qualitatively is recognized in the extant literature on multi-criteria decision making, unfortunately, there is no research effort so far in the AHP literature. Deriving motivation from the application of data envelopment analysis (DEA) for deriving weights, it is proposed in this paper that DEA models developed to deal with a mix of qualitative and quantitative factors can be used to derive weights from PCMs by treating judgements as qualitative factors. The qualitative DEA model is discussed and illustrated in this paper.     

A classification approach based on the outranking model for multiple criteria ABC analysis

The multiple criteria ABC analysis is widely used in inventory management, and it can help organizations to assign inventory items into different classes with respect to several evaluation criteria. Many approaches have been proposed in the literature for addressing such a problem. However, most of these approaches are fully compensatory in multiple criteria aggregation. This means that an item scoring badly on one or more key criteria could be placed in good classes because these bad performances could be compensated by other criteria. Thus, it is necessary to consider the non-compensation in the multiple criteria ABC analysis. To the best of our knowledge, the ABC classification problem with non-compensation among criteria has not been studied sufficiently. We thus propose a new classification approach based on the outranking model to cope with such a problem in this paper. However, the relational nature of the outranking model makes the search for the optimal classification solution a complex combinatorial optimization problem. It is very time-consuming to solve such a problem using mathematical programming techniques when the inventory size is large. Therefore, we combine the clustering analysis and the simulated annealing algorithm to search for the optimal classification. The clustering analysis groups similar inventory items together and builds up the hierarchy of clusters of items. The simulated annealing algorithm searches for the optimal classification on different levels of the hierarchy. The proposed approach is illustrated by a practical example from a Chinese manufacturer. Furthermore, we validate the performance of the approach through experimental investigation on a large set of artificially generated data at the end of the paper.     

A Lagrangian relaxation approach for the multiple sequence alignment problem

We present a branch-and-bound (bb) algorithm for the multiple sequence alignment problem (MSA), one of the most important problems in computational biology. The upper bound at each bb node is based on a Lagrangian relaxation of an integer linear programming formulation for MSA. Dualizing certain inequalities, the Lagrangian subproblem becomes a pairwise alignment problem, which can be solved efficiently by a dynamic programming approach. Due to a reformulation w.r.t. additionally introduced variables prior to relaxation we improve the convergence rate dramatically while at the same time being able to solve the Lagrangian problem efficiently. Our experiments show that our implementation, although preliminary, outperforms all exact algorithms for the multiple sequence alignment problem. Furthermore, the quality of the alignments is among the best computed so far.     

A general modeling approach to online optimization with lookahead

A vast number of real world problems are coined by an information release over time and the related need for repetitive decision making over time. Optimization problems arising in this context are called online since decisions have to be made although not all data is known. Due to technological advances, algorithms may also resort to a limited preview (lookahead) on future events. We first embed the paradigm of online optimization with lookahead into the theory of optimization and develop a concise understanding of lookahead. We further find that the effect of lookahead can be decomposed into an informational and a processual component. Based on analogies to discrete event systems, we then formulate a generic modeling framework for online optimization with lookahead and derive a classification scheme which facilitates a thorough categorization of different lookahead concepts. After an assessment of performance measurement approaches with relevance to practical needs, we conduct a series of computational experiments which illustrate how the general concept of lookahead applies to specific instantiations and how a knowledge pool on lookahead effects in applications can be built up using the general classification scheme.     

Single vs. multiple objective supplier selection in a make to order environment

The problem of allocation of orders for custom parts among suppliers in make to order manufacturing is formulated as a single- or multi-objective mixed integer program. Given a set of customer orders for products, the decision maker needs to decide from which supplier to purchase custom parts required for each customer order. The selection of suppliers is based on price and quality of purchased parts and reliability of on time delivery. The risk of defective or unreliable supplies is controlled by the maximum number of delivery patterns (combinations of suppliers delivery dates) for which the average defect rate or late delivery rate can be unacceptable. Furthermore, the quantity or business volume discounts offered by the suppliers are considered. Numerical examples are presented and some computational results are reported.     

A multicriteria sorting approach based on data envelopment analysis for R&D project selection problem

In this paper, multiple criteria sorting methods based on data envelopment analysis (DEA) are developed to evaluate research and development (R&D) projects. The weight intervals of the criteria are obtained from Interval Analytic Hierarchy Process and employed as the assurance region constraints of models. Based on data envelopment analysis, two threshold estimation models, and five assignment models are developed for sorting. In addition to sorting, these models also provide ranking of the projects. The developed approach and the well-known sorting method UTADIS are applied to a real case study to analyze the R&D projects proposed to a grant program executed by a government funding agency in 2009. A five level R&D project selection criteria hierarchy and an assisting point allocation guide are defined to measure and quantify the performance of the projects. In the case study, the developed methods are observed to be more stable than UTADIS.     

Consumer preference analysis: A data-driven multiple criteria approach integrating online information

Multiple criteria approaches can assist the product manager to know the consumer preferences in the context of e-commerce. Consumer preference analysis explains what aspects of a product affect and how they affect a consumer’s purchasing decision. This issue plays an important role in e-commerce platforms from its relevance in marketing decisions such as advertisements, recommendations and promotions. In this regard, we propose a data-driven multiple criteria decision aiding (MCDA) approach to integrate online information, such as explicit (e.g., reviews and ratings) and implicit (e.g., clicks and purchases) feedback from consumers. However, MCDA approaches present a critical challenge that even an experienced product manager could find it difficult to pre-define the criteria on which a product is evaluated. To address this issue, our proposed approach first utilizes text-mining techniques to assist the product manager identify the criteria, and then determines and collects the relative importance of the criteria and their values. Given the criteria information, we use a sampling process to provide two indices, the consumer preference index and rank acceptability index. The first index helps in prioritizing the pairwise comparisons of products, while the second one helps in deriving a default ranking list for first-time-registered consumers. We record the products viewed by consumers and generate their preference information in the form of pairwise comparisons for analyses within an aggregation-disaggregation paradigm. We also provide a representative value function to help the product manager gain insight into the preferences. Finally, we describe how a real-world application including the product manager and consumers exploits the proposed approach on an e-commerce platform to take a large step toward aiding more realistic and data-driven multiple criteria decision making.     

A computational approach to the multi-period many-to-one matching with ties

The many-to-one matching problem is commonly referred as the hospitals/residents problem which assigns each resident a hospital in an efficient and fair way. This paper considers a multi-period hospitals/residents problem that consists of assigning positions to overlapping generations of residents. From one period to another, residents can either retain their current positions or can choose a more preferred one. In this situation, a fairness criterion is introduced with the condition of the individual rationality for the matching. Moreover, it has been proven that the matching satisfying such criterion always exists and can be obtained by iteratively eliminating Pareto improvement cycles and unjustified claim cycles from any acceptable matching. This paper presents a novel algorithm to compute a matching with minimal unjustified claims under the premise of satisfying the individual rationality and the Pareto efficiency. The complexity of the proposed algorithm is bounded by \(O(Q^{3}n^{3})\) in each period, where n and Q are the number of the residents and the total number of positions of the hospitals in the corresponding period, respectively.