Search

The assignment problem is a problem that takes many forms in optimization and graph theory, and by changing some of the constraints or interpreting them differently and adding other constraints, it can be converted to routing, distribution, and scheduling problems. Showing such correlations is one of the aims of this paper. For some of the derived problems having exponential time complexity, the question arises of their solvability for larger instances. Instead of the traditional approach based on the use of approximate or stochastic heuristic methods, we focus here on the direct use of mixed integer programming models in the GAMS environment, which is now capable of solving instances much larger than in the past and does not require complex parameter settings or statistical evaluation of the results as in the case of stochastic heuristics because the computational core of software tools, nested in GAMS, is deterministic in nature. The source codes presented may be an aid because this tool is not yet as well known as the MATLAB Optimisation Toolbox. Benchmarks of the permutation flow shop scheduling problem with the informally derived MIP model and the traveling salesman problem are used to present the limits of the software's applicability. [ABSTRACT FROM AUTHOR]

In microfinance, with more loans, there is a high risk of increasing overdue loans by overloading the resources available to take actions on the repayment. So, three experiments were conducted to search for a distribution of the loans through the officers available to maximize the probability of recovery. Firstly, the relation between the loan and some characteristics of the officers was analyzed. The results were not that strong with F1 scores between 0 and 0.74, with a lot of variation in the scores of the good predictions. Secondly, the loan is classified as paid/unpaid based on what prediction could result of the analysis of the characteristics of the loan. The Support Vector Machine had potential to be a solution with a F1 score average of 0.625; however, when predicting the unpaid loans, it showed to be random with a score of 0.55. Finally, the experiment focused on segmentation of the overdue loans in different groups, from where it would be possible to know their prioritization. The visualization of three clusters in the data was clear through Principal Component Analysis. To reinforce this good visualization, the final silhouette score was 0.194, which reflects that is a model that can be trusted. This way, an implementation of clustering loans into three groups, and a respective prioritization scale would be the best strategy to organize and assign the loans to maximize recovery. [ABSTRACT FROM AUTHOR]

This paper presents a model-driven multiobjective avionics system optimization method developed over six years at its final destination, the application in real-world integrated modular avionics systems. It documents the methods, the application scenario, and the results of large-scale optimization studies carried out for the Airbus A350 peripheral acquisition system. The results predict that a significantly lighter system could be possible. [ABSTRACT FROM AUTHOR]

A sonobuoy is an underwater acoustic sensor primarily deployed by airdrop. An acoustic sensor plays a significant role in conducting anti-submarine warfare for detecting underwater sounds. As a future underwater acoustic sensor, sonobuoy is expected to have an ability of self-movement, i.e., autonomous sonobuoy. In this study, we consider an optimal linear array deployment of autonomous sonobuoys when detecting an unknown underwater sound, assuming that the initial locations of sonobuoys are random in a specified operational area. Deploying sonobuoys from the initial locations onto a specific line requires to first determine the line and positions on that line. Under the interval equivalence between two adjacent sonobuoys, we propose two lines, one that is perpendicular from the underwater sound source location and the other based on the linear regression analysis using the initial locations of sonobuoys. With these two lines onto which sonobuoys will be deployed, we provide two optimization models, total distance minimization and maximum distance minimization, which turn out to be assignment and bottleneck assignment problems, respectively, with nonlinear cost coefficients in the objectives. Due to non-convexity of the objectives, we solve these problems for a fixed interval repetitively as a linear program and integer program, respectively. Computational results show that regression-based line provides higher solution qualities for both problems. Finally, we suggest an approximate interval in a heuristic manner, which guarantees a highly near-optimality as the number of sonobuoys increases. Our results may support a decision-making and provide practitioners with insight on more variety of effective use of autonomous sonobuoys. [ABSTRACT FROM AUTHOR]

This paper proposes an uncertain random assignment problem in which random variables coexist with uncertain variables. Critical values of uncertain random variables are used to rank uncertain random variables. An uncertain random simulation algorithm is developed in order to obtain chance distributions and critical values of uncertain random variables. An α -optimistic model is presented. A combined optimization approach is designed to solve the α -optimistic model. This approach incorporates uncertain random simulation into branch and bound algorithm. Finally, an example application of the approach is presented. [ABSTRACT FROM AUTHOR]

The passenger traffic is the most sensitive field in terms of the passengerś perception of the transport line layout. Every drawback will show soon and be transferred into the whole range of the provided services. The aim in the passenger traffic is to remove any obstacles that prevent the passengers from obtaining the continuous, available and high quality transport and to develop such activities to meet the requirements of the passengers as much as possible. [ABSTRACT FROM AUTHOR]

Semidefinite optimization is a strong tool in the study of NP-hard combinatorial optimization problems. On the one hand, semidefinite optimization problems are in principle solvable in polynomial time (with fixed precision), on the other hand, their modeling power allows to naturally handle quadratic constraints. Contrary to linear optimization with the efficiency of the Simplex method, the algorithmic treatment of semidefinite problems is much more subtle and also practically quite expensive. This survey-type article is meant as an introduction for a non-expert to this exciting area. The basic concepts are explained on a mostly intuitive level, and pointers to advanced topics are given. We provide a variety of semidefinite optimization models on a selection of graph optimization problems and give a flavour of their practical impact. [ABSTRACT FROM AUTHOR]

This paper applies combinatorial optimization techniques to improve the downlink transmission to multiple users in a network with N cells, where intercell interference is a performance-limiting factor. A fair distribution of the signal-to-interference-plus-noise ratio (SINR) is desirable. A well-known technique to get a fair (balanced) SINR is max–min unicast beamforming (MBF). However, in a multicell network, there are conditions where MBF can result in a low balanced SINR. This happens if, e.g., two users are geographically close together and served by two base stations (BSs) from, e.g., two different interfering sectors. Then, the mutual interference among the two links will be large, and the balanced SINR among all jointly optimized links decreases. Therefore, the users must be scheduled such that these situations are avoided. In this paper, smart selection of active beams to avoid intercell interference is called beam scheduling and leads to a combinatorial optimization problem. This paper proposes a graph-theory-based problem that is closely related to the beam scheduling problem. The proposed algorithms maximize the sum rate or the minimum SINR among all users and slots. For the two-cell case, an optimal algorithm exists. In the N > \2-cell case, the beam scheduling problem is proven to be NP-hard. Based on the close relation between the beam scheduling problem and the multidimensional assignment problem (MAP), this paper presents suboptimal algorithms for N > \2 to maximize either the sum rate or the minimum SINR among all users and slots. The performance gain in terms of the mean sum rate or the minimum SINR is significant compared with random scheduling. [ABSTRACT FROM PUBLISHER]

We consider a generalization of the well-known capacitated facility location problem with single source constraints in which customer demand contains a flexible dimension. This work focuses on providing fast and practically implementable optimization-based heuristic solution methods for very large scale problem instances. We offer a unique approach that utilizes a high-quality efficient heuristic within a neighborhood search to address the combined assignment and fixed-charge structure of the underlying optimization problem. We also study the potential benefits of combining our approach with a so-called very large-scale neighborhood search (VLSN) method. As our computational test results indicate, our work offers an attractive solution approach that can be tailored to successfully solve a broad class of problem instances for facility location and similar fixed-charge problems. [ABSTRACT FROM AUTHOR]

We consider the problem of multi-robot task-allocation when robots have to deal with uncertain utility estimates. Typically an allocation is performed to maximize expected utility; we consider a means for measuring the robustness of a given optimal allocation when robots have some measure of the uncertainty (e.g. a probability distribution, or moments of such distributions). We introduce the interval Hungarian algorithm, a new algorithm that extends the classic Kuhn—Munkres Hungarian algorithm to compute the maximum interval of deviation, for each entry in the assignment matrix, which will retain the same optimal assignment. The algorithm has a worst-case time complexity of O(n4); we also introduce a parallel variant with O(n3) running time, which is able to exploit the concurrent computing capabilities of distributed multi-robot systems. This provides an efficient measurement of the tolerance of the allocation to the uncertainties and dynamics, for both a specific interval and a set of interrelated intervals. We conduct experiments both in simulation and with physical robots to validate the approach and to gain insight into the effect of location uncertainty on allocations for multi-robot multi-target navigation tasks. [ABSTRACT FROM AUTHOR]

Abstract: In this article, a new multiobjective optimization model, MUST, is proposed to facilitate the staff-to-job assignment in consulting engineering firms. In addition to the typical objective of maximizing profits, other human resource related objectives are also incorporated to balance workloads, avoid excessive overtime, and eliminate demoralizing idleness while giving preference to projects with specified priorities. The present optimization problem is of significant complexity (nonlinear, non-smooth, and combinatorial) and has been proved NP- and #P-complete. To handle all the difficulties, MUST incorporates a particle swarm optimization algorithm to approximate the tradeoff surface consisting of non-dominated solutions. The application of MUST is demonstrated through a numerical case of assigning six engineering teams to fifteen incoming projects. It has been shown that non-dominated solutions generated by MUST help decision makers choose the compromised assignment plan which is otherwise hard and time-consuming to obtain. The comparisons with SPEA2 and LINGO verify the effectiveness and efficiency of MUST. [Copyright &y& Elsevier]

In the assignment problem units of supply are assigned on a one-to-one basis to units of demand so as to minimize the sum of the cost associated with each supply-to-demand matched pair. Defined on a network, the supplies and demands are located at vertices and the cost of a supply-to-demand matched pair is the distance between them. This paper considers a two-stage stochastic program for locating the units of supply based upon only a probabilistic characterization of demand. The objective of the first-stage location problem is to minimize the expected cost of the second-stage assignment problem. Principal results include showing that the problem is NP-hard on a general network, has a simple solution procedure on a line network, and is solvable by a low order polynomial greedy procedure on a tree network. Potential applications are discussed. [ABSTRACT FROM AUTHOR]

In this paper, a two-phase method is presented for selection of machines to be kept on the shop floor and assignment of parts to be manufactured on these machines. In the first phase, dynamic programming or a heuristic procedure identifies a set of feasible solutions to a knapsack problem. In the second phase, implicit enumeration technique or a greedy algorithm solves an assignment problem. The proposed method is written in language C and runs on a parallel virtual machine called PVM-W95. The results obtained from the parallel implementation on several examples which are found in the literature, as well as examples generated at random, were used to establish a comparison with the sequential algorithm and to perform a speedup analysis. [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]

Latin hypercube sampling is often used to estimate the distribution function of a complicated function of many random variables. In so doing, it is typically necessary to choose a permutation matrix which minimizes the correlation among the cells in the hypercube layout. This problem can be formulated as a generalized, multi-dimensional assignment problem. For the two-dimensional case, we provide a polynomial algorithm. For higher dimensions, we offer effective heuristic and bounding procedures. [ABSTRACT FROM AUTHOR]

The assignment problem (AP) is a discrete and combinatorial problem where agents are assigned to perform tasks for efficiency maximization or cost (time) minimization. AP is a part of human resource project management (HRPM). The AP optimization model, with deterministic parameters describing agent–task performance, can be easily solved, but it is characteristic of standard, well-known projects realized in a quiet environment. When considering new (innovation or innovative) projects or projects performed in very turbulent times, the parameter estimation becomes more complex (in extreme cases, even the use of the probability calculus is not recommended). Therefore, we suggest an algorithm combining binary programming with scenario planning and applying the optimism coefficient, which describes the manager's nature (attitude towards risk). The procedure is designed for one-shot decisions (i.e., for situations where the selected alternative is performed only once) and pure strategies (the execution of a weighted combination of several decision variants is not possible). [ABSTRACT FROM AUTHOR]