Search

Seminars are offered to students for education in various disciplines. The seminars may be limited in terms of the maximum number of participants, e.g., to have lively interactions. Due to capacity limitations, those seminars are often offered several times to serve the students' demands. Still, some seminars are more popular than others and it may not be possible to grant access to all interested students due to capacity limitations. In this paper, a simple, but efficient random selection using key objectives (SEKO) assignment strategy is proposed which achieves the following goals: (i) efficiency by utilizing all available seminar places, (ii) satisfying all students by trying to assign at least one seminar to each student, and (iii) fairness by considering the number of assigned seminars per student. We formulate various theoretical optimization models using integer linear programming (ILP) and compare their solutions to the SEKO assignment based on a real-world data set. The real-world data set is also used as the basis for generating large data sets to investigate the scalability in terms of demand and number of seminars. Furthermore, the first-in first-out (FIFO) assignment, as a typical implementation of fair assignments in practice, is compared to SEKO in terms of utilization and fairness. The results show that the FIFO assignment suffers in realworld situations regarding fairness, while the SEKO assignment is close to the optimum and scales regarding computational time in contrast to the ILP. [ABSTRACT FROM AUTHOR]

Robotic Process Automation has emerged in recent years as an important field by allowing faster and more secure processes through a reduction in the risks or errors but also an increase in the productivity rates of many industries. In this specific paper, the RPA problem aims at assigning financial transactions to software robots to minimize the total costs, induced by the licenses and utilization time. The problem is represented as a bipartite graph and the effective resistance of the graph, which is analog to an electrical circuit, is used to order the edges of a heuristic method to assign the transactions to robots. Preliminary results, based on real data from a bank, are compared to the optimal solution obtained by a linear integer programming model. They show that the heuristic method allows to obtain results quicker and that they are near the optimal solution. [ABSTRACT FROM AUTHOR]

The assignment problem is one of the core combinatorial optimization problems in the optimization branch, and the theory and applications of fractional programming have made great strides in recent years. Usually, the possible coefficient values of linear fractional programming and real-world problems are frequently only known to the decision in vague or uncertain terms. Hence, it would be more acceptable to interpret the coefficients for as fuzzy numerical information. In this paper, a fuzzy bi-objective fractional assignment (FBOFAP) has been formulated. A problem has been defined. Here, triangular shapes are used to indicate the parameters. The fuzzy problem is turned into a typical crisp problem through α-cut using a fuzzy number and then the compromise solution is generated by fuzzy programming. [ABSTRACT FROM AUTHOR]

We generalize the well-known primal-dual algorithm proposed by Chambolle and Pock for saddle point problems and relax the condition for ensuring its convergence. The relaxed convergenceguaranteeing condition is effective for the generic convex setting of saddle point problems, and we show by the canonical convex programming problem with linear equality constraints that the relaxed condition is optimal. It also allows us to discern larger step sizes for the resulting subproblems, and thus provides a simple and universal way to improve numerical performance of the original primal-dual algorithm. In addition, we present a structure-exploring heuristic to further relax the convergence-guaranteeing condition for some specific saddle point problems, which could yield much larger step sizes and hence significantly better performance. Effectiveness of this heuristic is numerically illustrated by the classic assignment problem. [ABSTRACT FROM AUTHOR]

Assignment problems (AP) are well-known topics in engineering and management science and are used frequently to analyze problems. A linear programming problem form was used in transforming assignment problem for crisp problem and in solving as per Hungarian methodology. Assigning n objects over m objects is an exciting problem that arises in different situations. Here we explore the optimal ways for assigning in n objects over m other objects. Numerous numerical applications are needed in production planning, Sales proportions, airline operators, etc. The existing Hungarian methods and maximized (or minimized) assignment methods have been solved using these methods. Entry details in the cost matrix are not always clear. This parameter is uncertain in many applications, and these uncertain parameters are represented by intervals. To solve interval linear assignment problems, we present interval Hungarian method and interval analysis concept. [ABSTRACT FROM AUTHOR]

One critical problem in Indonesia's national joint courses program, initiated by the ministry of education and culture of Indonesia, is the lecturer-course assignment problem. Although the lecturer-course assignment problem has been studied widely as part of the education timetabling problem, no existing lecturer-course assignment model suits this circumstance. The new cases in this program are as follows. First, this program is conducted online. Second, the participants are students and lecturers from different universities. Based on this problem, this work proposes a novel lecturer-course assignment model that suits this program. The lecturers' preferred courses and timeslots become hard constraints. The model has three objectives: (1) maximizing the educational quality, (2) maximizing the lecturers' time preference, and (3) minimizing the number of unserved classes. This model is developed by using integer linear programming and optimized by using cloud theory-based simulated annealing. This proposed model is then compared with the four previous lecturers-course assignment models. The first model concerns about minimizing the number of unserved classes, while the second model focuses on maximizing the education quality. The maximum number of classes per course for every lecturer is considered in the third model while balancing the lecturer’s load (teach, research, community service) is the feature of the fourth model. The research concludes that the proposed model is appropriate for lecture-course assignment in Indonesia’s national joint courses program compared to the previous models. Based on the simulation result, the proposed model performs moderately in education quality and several unserved classes. Meanwhile, the proposed model is the best in the timeslot preference aspect by creating a 25% to 28% higher total timeslot score than other previous models. [ABSTRACT FROM AUTHOR]

In recent researches, it is emphasized that the problem of hunger has come up with the rapidly increasing population all over the world and therefore the importance of agricultural production is increasing. However, the spatial loss and structural deterioration of agricultural production in agricultural lands is an important problem. The most important issue in agricultural production is to ensure the highest yield in the right production area, with the right products and cultural practices. In this study, crop pattern models are created with 26 crops by a mixed-integer mathematical programming model using climate data and soil properties on 11 sample farmlands in the TR72 region of Turkey. The region investigated in this study has a continental climate, while winters are cold, summers are hot and average temperatures are 10.8 ° C. The aim is to ensure that the land is used correctly and to prevent loss of agricultural land quality and to create an exemplary model that will increase the economic gain. As a result of the study, it is determined which species can be produced in which parcel and how crop rotation can be applied. [ABSTRACT FROM AUTHOR]

A new approach to the synthesis of a multistage heat exchange network is proposed based on the principle of fixation of variables. This principle enables one to reduce a discrete-continuous programming problem to a sequence of linear and nonlinear programming problems. For their formalization, a new variant of the superstructure of a heat exchange network is put forward which includes all the possible flow patterns of material and heat streams. A computational experiment has proven that this problem is multiextremal. The vertical decomposition of the superstructure decreases the number of local minima of an economic criterion and reduces the computational difficulty of the synthesis problem, which is useful for modeling large-scale engineering systems. The performance of the proposed algorithm is demonstrated by a number of model examples in comparison with that of the efficient SYNHEAT software. [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]

Cross-docks serve as distribution centers where shipments from different vendors are first consolidated according to their destinations, and then delivered to the retailers directly, with little or no storage in between. A critical problem encountered in the operation of cross-docks is the assignment of receiving and shipping doors, which greatly influences the labor or machinery cost of transferring the shipments between inbound and outbound transports. We show that the cross-dock door assignment problem (CDAP) is strictly non-deterministic polynomial-time complete. Although some deterministic algorithms have been reported to handle small-scale problems, the solutions to the middle- and large-scale CDAPs progressed at a slow pace. In this paper, we develop a nature-inspired dual-colony ant algorithm for CDAP, in which the two colonies of ants cooperatively search the optimal assignments of receiving and shipping doors to minimize the transferring costs of shipments. A collaborative local search strategy is designed and incorporated into the algorithm to enhance the search efficiency. Experiments have been conducted on a number of problem instances with different cross-dock sizes and freight flow patterns. The results show that the proposed algorithm is very competitive and can provide better solutions than the state-of-the-art heuristic algorithms. [ABSTRACT FROM AUTHOR]

Abstract Many technical systems like manufacturing plants or software applications generate large event sequences. Knowing the temporal relationship between events is important for gaining insights into the status and behavior of the system. This paper proposes a novel approach for identifying the time lag between different event types. This identification task is formulated as a binary integer optimization problem that can be solved efficiently and close to optimality by means of a linear programming approximation. The performance of the proposed approach is demonstrated on synthetic and real-world event sequences. [ABSTRACT FROM AUTHOR]

This paper presents a new multiple criteria optimization model of an assignment problem with imprecise coefficients. Besides, minimizing the total cost, total time of finishing jobs, and maximization of the overall achieved quality, we introduce a new criterion that minimizes the number of workers employed to finish all jobs. It contributes significantly in multi-job assignment to adjust the number of workers assigned to at least one job for balancing work allocation among the workers. Furthermore, we employ new diversification constraints to obtain a reasonable tradeoff between the number of workers employed and number of jobs assigned. A new interactive possibilistic programming approach is developed for trapezoidal possibility distributions, which uses $\alpha$ -level sets to incorporate confidence levels of the decision maker in his fuzzy judgments leading to $\alpha$ -efficient solutions. Numerical experiments are conducted using data coming from a manpower planning problem to demonstrate working of the proposed multiple criteria assignment model and effectiveness of the fuzzy interactive approach. [ABSTRACT FROM AUTHOR]

The assignment problem is an archetypal combinatorial optimization problem. This paper presents a neural network based on a dynamic model for solving the assignment problem. The main idea is to replace the assignment problem with a linear programming problem. On the basis of the Karush- Kuhn-Tucker optimality conditions, the equilibrium point of the proposed neural network is proved to be equivalent to the optimal solution of the original problem. It is also shown that the proposed neural network model is stable in the sense of Lyapunov and it is globally convergent to an exact optimal solution of the assignment problem. Block diagram of the proposed model is given. Several illustrative examples are provided to show the feasibility and the efficiency of the proposed method in this paper. [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]

Underlay device-to-device (D2D) communication in cellular networks has been considered as a promising technique that can improve the spectral efficiency of cellular systems and meet the growing demand for wireless local services. In underlay D2D, it is of primary importance to manage the mutual interference between cellular links and D2D links through effective resource allocation. While most of previous works on D2D resource allocation are developed based on the knowledge of the channel state information (CSI) on the interference channels as well as the desired channels, it is hard to obtain full CSI in practice. Accordingly, we consider D2D resource allocation schemes based on distance between nodes. In particular, we formulate two optimization problems for D2D resource allocation using the outage probability computed based on the distance information as cost functions. One is a linear sum assignment problem (LSAP) and the other is a linear bottleneck assignment problem (LBAP). By applying the graph theory, we provide efficient algorithms for solving the optimization problems. Numerical results are provided to show the effectiveness of the proposed optimization as compared to previously proposed distance-based resource allocation algorithms. [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]

We consider the bilevel assignment problem in which each decision maker (i.e., the leader and the follower) has its own objective function and controls a distinct set of edges in a given bipartite graph. The leader acts first by choosing some of its edges. Subsequently, the follower completes the assignment process. The edges selected by the leader and the follower are required to constitute a perfect matching. In this paper we propose an exact solution approach, which is based on a branch-and-bound framework and exploits structural properties of the assignment problem. Extensive computational experiments with linear sum and linear bottleneck objective functions are conducted to demonstrate the performance of the developed methods. While the considered problem is known to be NP-hard in general, we also describe some restricted cases that can be solved in polynomial time. [ABSTRACT FROM AUTHOR]

The pattern matching with wildcards and length constraints problem is an interesting problem in the literature whose computational complexity is still open. There are polynomial time exact algorithms for its special cases. There are heuristic algorithms, and online algorithms that do not guarantee an optimal solution to the original problem. We consider two special cases of the problem for which we develop offline solutions. We give an algorithm for one case with provably better worst case time complexity compared to existing algorithms. We present the first exact algorithm for the second case. This algorithm uses integer linear programming (ILP) and it takes polynomial time under certain conditions. [ABSTRACT FROM AUTHOR]

The linear bottleneck assignment problem (LBAP), which is a variation of the classical assignment problem (CAP), seeks to minimize the longest completion time rather than the sum of the completion times when a number of jobs are to be assigned to the same number of workers. Several procedures have been proposed in the current literature to convert the LBAP into an equivalent CAP and then apply the Hungarian method to solve it efficiently. However, their applicability is limited because some of the elements in the transformed assignment matrix for the CAP can be too large to be handled by most computer programs. In this paper, we suggest a turnpike approach to alleviate the problem so that the conversion methodology will become more useful in practice. A numerical example is provided to demonstrate the superiority of the new algorithm to the existing ones. [ABSTRACT FROM AUTHOR]

In this paper, we propose a new possibilistic programming approach to solve a fuzzy multiobjective assignment problem in which the objective function coefficients are characterized by triangular possibility distributions. The proposed solution approach simultaneously minimizes the best scenario, the likeliest scenario, and the worst scenario for the imprecise objective functions using \alpha-level sets. The \alpha-level sets are used to define the confidence level of the fuzzy judgments of the decision maker. Additionally, we provide a systematic framework in which the decision maker controls the search direction by updating both the membership values and aspiration levels until a set of satisfactory solutions is obtained. Numerical examples, with dataset from realistic situations, are provided to demonstrate the effectiveness of the proposed approach. [ABSTRACT FROM AUTHOR]

In the Tutor Allocation Problem, the objective is to assign a set of tutors to a set of workshops in order to maximize tutors' preferences. The problem is solved every year by many universities, each having its own specific set of constraints. In this work, we study the tutor allocation in the School of Mathematics at the University of Edinburgh, and solve it with an integer linear programming model. We tested the model on the 2019/2020 case, obtaining a significant improvement with respect to the manual assignment in use and we showed that such improvement could be maintained while optimizing other key metrics such as load balance among groups of tutors and total number of courses assigned. Further tests on randomly created instances show that the model can be used to address cases of broad interest. We also provide meaningful insights on how input parameters, such as the number of workshop locations and the length of the tutors' preference list, might affect the performance of the model and the average number of preferences satisfied. • The assignment of tutors to workshops is a practical problem faced by universities. • We propose a mathematical model for a real case of the problem. • The implemented algorithm finds an optimal solution for the real case. • We introduce a set of additional constraints to make the allocation fairer. • Further computational experiments demonstrate the model scalability. [ABSTRACT FROM AUTHOR]

Abstract: This note shows that the data envelopment analysis (DEA) models formulated by Chen and Lu [L.H. Chen, H.W. Lu, An extended assignment problem considering multiple inputs and outputs, Appl. Math. Modell. 31 (2007) 2239–2248] are not correct. The enveloping form of the Chen and Lu formulation is studied and a simple example is presented to demonstrate the differences between the efficiency scores resulted of the Chen and Lu formulation, and the true ones. [Copyright &y& Elsevier]

Abstract: We study the problem of optimizing nonlinear objective functions over bipartite matchings. While the problem is generally intractable, we provide several efficient algorithms for it, including a deterministic algorithm for maximizing convex objectives, approximative algorithms for norm minimization and maximization, and a randomized algorithm for optimizing arbitrary objectives. [Copyright &y& Elsevier]

Alternative optimal solutions can give more choice for practical decision making. Therefore, the provision of methods for finding alternative optimal solutions is an important component part of the solution techniques for optimization models. The aim of this paper is to present a branch-and-bound algorithm for finding all optimal solutions of the linear assignment problem. Numerical experimental results are also given. [ABSTRACT FROM AUTHOR]

Abstract: The existing assignment problems for assigning n jobs to n individuals are limited to the considerations of cost or profit incurred by each possible assignment. However, in real applications, various inputs and outputs are usually concerned in an assignment problem, such as a general decision-making problem. This paper develops a procedure for resolving assignment problems with multiple incommensurate inputs and outputs for each possible assignment. The concept of the relative efficiency in using various resources, instead of cost or profit, is adopted for each possible assignment of the problem. Data envelopment analysis (DEA) is employed in this paper to measure the efficiency of one assignment relative to that of the others according to a set of decision-making units. A composite efficiency index, consisting of two kinds of relative efficiencies under different comparison bases, is defined to serve as the performance measurement of each possible assignment in the problem formulation. A mathematical programming model for the extended assignment problem is proposed, which is then expressed as a classical integer linear programming model to determine the assignments with the maximum efficiency. A numerical example is used to demonstrate the approach. [Copyright &y& Elsevier]

Information of sensitivity analysis, in a linear programming problem, is usually more important than the optimal solution itself. However, traditional sensitivity analysis, which perturbs exactly one coefficient and then determines the range preserving the optimality of the current optimal base, is impractical for the assignment problem. An optimal basic solution of the assignment problem is inherently degenerate, so it may be that the optimal base has changed but the optimal assignment remains unchanged. Furthermore, elements of a column (or row) in a cost matrix of assignment problem are usually closely related and change simultaneously, not uniquely. This paper focuses on two kinds of sensitivity analyses for the assignment problem. One is to determine the sensitivity range, over which the current optimal assignment or all the optimal assignments remain optimal, while perturbing the elements of one column (or row) in a cost matrix of the assignment problem simultaneously but dependently. The other is to perturb elements of one column (or row) in a cost matrix of the assignment problem simultaneously but independently. Numerical illustrations are presented to demonstrate that the approaches are useful in practice. [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]

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]

To date, there has been a lack of efficient and practical distributed- and shared-memory parallelizations of the data association problem for multitarget tracking. Filling this gap is one of the primary focuses of the present work. We begin by describing our data association algorithm in terms of an Interacting Multiple Model (1MM) state estimator embedded into an optimization framework, namely, a two-dimensional (2D) assignment problem (i.e., weighted bipartite matching). Contrary to conventional wisdom, we show that the data association (or optimization) problem is not the major computational bottleneck; instead, the interface to the optimization problem, namely, computing the rather numerous gating tests and 1MM state estimates, covariance calculations, and likelihood function evaluations (used as cost coefficients in the 2D assignment problem), is the primary source of the workload. Hence, for both a general-purpose shared-memory MIMD (Multiple Instruction Multiple Data) multiprocessor system and a distributed-memory Intel Paragon high-performance computer, we developed parallelizations of the data association problem that focus on the interface problem. For the former, a coarse-grained dynamic parallelization was developed that realizes excellent performance (i.e., superlinear speedups) independent of numerous factors influencing problem size (e.g., many models in the 1MM, dense/cluttered environments, contentious target-measurement data, etc.). For the latter, an SPMD (Single Program Multiple Data) parallelization was developed that realizes near-linear speedups using relatively simple dynamic task allocation algorithms. Using a real measurement database based on two FAA air traffic control radars, we show that the parallelizations developed in this work offer great promise in practice. [ABSTRACT FROM AUTHOR]

'Where there is abundance of mystery and confusion in every direction, the truth seldom remains hidden for long. It's a matter of having plenty of angles to go at it from. Only the utterly simple crimes - the simplex crimes, you may say - have the trick of remaining baffling.' - Sir John (from Michael Innes, The Open House (A Sir John Appleby Mystery), Penguin Books, 1974). A dual simplex method for the assignment problem leaves open to choice the activity ( i,j) of row i and column j that is to be dropped in pivoting so long as x < 0. A choice ( i,j) over columns j having at least 3 basic activities that minimizes x is shown to converge in at most () pivots, and at most O( n) time, and it is argued that on average the number of pivots is at most n log n. [ABSTRACT FROM AUTHOR]

Vande Vate (1989) described the polytope whose extreme points are the stable (core) matchings in the Marriage Problem. Rothblum (1989) simplified and extended this result. This paper explores a corresponding linear program, its dual and consequences of the fact that the dual solutions have an unusually direct relation to the primal solutions. This close relationship allows us to provide simple proofs both of Vande Vate and Rothblum's results and of other important results about the core of marriage markets. These proofs help explain the structure shared by the marriage problem (without sidepayments) and the assignment game (with sidepayments). The paper further explores "fractional" matchings, which may be interpreted as lotteries over possible matches or as time-sharing arrangements. We show that those fractional matchings in the Stable Marriage Polytope form a lattice with respect to a partial ordering that involves stochastic dominance. Thus, all expected utility functions corresponding to the same ordinal preferences will agree on the relevant comparisons. Finally, we provide linear programming proofs of slightly stronger versions of known incentive compatibility results. [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]