Staff assignment with lexicographically ordered acceptance levels

Staff assignment is a compelling exercise that affects most companies and organizations in the service industries. Here, we introduce a new real-world staff assignment problem that was reported to us by a Swiss provider of commercial employee scheduling software. The problem consists of assigning employees to work shifts subject to a large variety of critical and noncritical requests, including employees’ personal preferences. Each request has a target value, and deviations from the target value are associated with integer acceptance levels. These acceptance levels reflect the relative severity of possible deviations, e.g., for the request of an employee to have at least two weekends off, having one weekend off is preferable to having no weekend off and thus receives a higher acceptance level. The objective is to minimize the total number of deviations in lexicographical order of the acceptance levels. Staff assignment approaches from the literature are not applicable to this problem. We provide a binary linear programming formulation and propose a matheuristic for large-scale instances. The matheuristic employs effective strategies to determine the subproblems and focuses on finding good feasible solutions to the subproblems rather than proving their optimality. Our computational analysis based on real-world data shows that the matheuristic scales well and outperforms commercial employee scheduling software.     

Long-term information collection with energy harvesting wireless sensors: a multi-armed bandit based approach

This paper reports on the development of a multi-agent approach to long-term information collection in networks of energy harvesting wireless sensors. In particular, we focus on developing energy management and data routing policies that adapt their behaviour according to the energy that is harvested, in order to maximise the amount of information collected given the available energy budget. In so doing, we introduce a new energy management technique, based on multi-armed bandit learning, that allows each agent to adaptively allocate its energy budget across the tasks of data sampling, receiving and transmitting. By using this approach, each agent can learn the optimal energy budget settings that give it efficient information collection in the long run. Then, we propose two novel decentralised multi-hop algorithms for data routing. The first proveably maximises the information throughput in the network, but can sometimes involve high communication cost. The second algorithm provides near-optimal performance, but with reduced computational and communication costs. Finally, we demonstrate that, by using our approaches for energy management and routing, we can achieve a 120% improvement in long-term information collection against state-of-the-art benchmarks.     

Improved differential evolution based on multi-armed bandit for multimodal optimization problems

Applied Intelligence - The main aim of multimodal optimization problems (MMOPs) is to find and deal with multiple optimal solutions using an objective function. MMOPs perform the exploration and...     

认知无线网络中基于无休止多臂赌博机模型的多用户频谱接入机制

针对如何协调多个认知用户择机接入多段空闲频域信道的问题,提出了一种基于无休止多臂赌博机(RMAB)模型的动态频谱接入机制。首先,考虑到实际环境下认知用户的信道感知误差,推导出能有效处理感知误差的Whittle索引值算法,该算法通过历史经验积累给予每个信道一定的信任值,并综合考虑在当前信任值下选择每个信道的立即收益与未来收益的多少,选择出需要感知接入的信道;其次,对于多个认知用户接入相同信道时产生冲突的问题,提出了基于多标拍卖的协调机制,通过多标拍卖的方式处理认知用户之间的冲突。仿真结果表明,在相同的环境中,所提出的频谱接入机制与未处理误差的或者未采用多标拍卖的接入机制相比,认知用户获得的吞吐量更大。     

Multi-objective evolutionary algorithms based on the summation of normalized objectives and diversified selection

Most multi-objective evolutionary algorithms (MOEAs) use the concept of dominance in the search process to select the top solutions as parents in an elitist manner. However, as MOEAs are probabilistic search methods, some useful information may be wasted, if the dominated solutions are completely disregarded. In addition, the diversity may be lost during the early stages of the search process leading to a locally optimal or partial Pareto-front. Beside this, the non-domination sorting process is complex and time consuming. To overcome these problems, this paper proposes multi-objective evolutionary algorithms based on Summation of normalized objective values and diversified selection (SNOV-DS). The performance of this algorithm is tested on a set of benchmark problems using both multi-objective evolutionary programming (MOEP) and multi-objective differential evolution (MODE). With the proposed method, the performance metric has improved significantly and the speed of the parent selection process has also increased when compared with the non-domination sorting. In addition, the proposed algorithm also outperforms ten other algorithms.     

Machine learning and nonparametric bandit theory

In its most basic form, bandit theory is concerned with the design problem of sequentially choosing members from a given collection of random variables so that the regret, i.e., R_n=Σ_j (μ*-μ_j)ET_n(j), grows as slowly as possible with increasing n. Here μ_j is the expected value of the bandit arm (i.e., random variable) indexed by j, T_n(j) is the number of times arm j has been selected in the first n decision stages, and μ^*=sup_j μ_j. The present paper contributes to the theory by considering the situation in which observations are dependent. To begin with, the dependency is presumed to depend only on past observations of the same arm, but later, we allow that it may be with respect to the entire past and that the set of arms is infinite. This brings queues and, more generally, controlled Markov processes into our purview. Thus our “black-box” methodology is suitable for the case when the only observables are cost values and, in particular, the probability structure and loss function are unknown to the designer. The conclusion of the analysis is that under lenient conditions, using algorithms prescribed herein, risk growth is commensurate with that in the simplest i.i.d. cases. Our methods represent an alternative to stochastic-approximation/perturbation-analysis ideas for tuning queues     

A theory of satisficing decisions and control

The existence of an optimal control policy and the techniques for finding it are grounded fundamentally in a global perspective. These techniques can be of limited value when the global behaviour of the system is difficult to characterize, as it may be when the system is nonlinear, when the input is constrained, or when only partial information is available regarding system dynamics or the environment. Satisficing control theory is an alternative approach that is compatible with the limited rationality associated with such systems. This theory is extended by the introduction of the notion of strong satisficing to provide a systematic procedure for the design of satisficing controls. The power of the satisficing approach is illustrated by applications to representative control problems     

Multiclass classification with bandit feedback using adaptive regularization

We present a new multiclass algorithm in the bandit framework, where after making a prediction, the learning algorithm receives only partial feedback, i.e., a single bit indicating whether the predicted label is correct or not, rather than the true label. Our algorithm is based on the second-order Perceptron, and uses upper-confidence bounds to trade-off exploration and exploitation, instead of random sampling as performed by most current algorithms. We analyze this algorithm in a partial adversarial setting, where instances are chosen adversarially, while the labels are chosen according to a linear probabilistic model which is also chosen adversarially. We show a regret of $\mathcal{O}(\sqrt{T}\log T)$ , which improves over the current best bounds of $\mathcal{O}(T^{2/3})$ in the fully adversarial setting. We evaluate our algorithm on nine real-world text classification problems and on four vowel recognition tasks, often obtaining state-of-the-art results, even compared with non-bandit online algorithms, especially when label noise is introduced.     

Robust satisficing and the probability of survival

Concepts of robustness are sometimes employed when decisions under uncertainty are made without probabilistic information. We present a theorem that establishes necessary and sufficient conditions for non-probabilistic robustness to be equivalent to the probability of satisfying the specified outcome requirements. When this holds, probability is enhanced (or maximised) by enhancing (or maximising) robustness. Two further theorems establish important special cases. These theorems have implications for success or survival under uncertainty. Applications to foraging and finance are discussed.     

An interactive satisficing approach for multi-objective optimization with uncertain parameters

Uncertain variables are used to describe the phenomenon where uncertainty appears in a complex system. For modeling the multi-objective decision-making problems with uncertain parameters, a class of uncertain optimization is suggested for the decision systems in Liu and Chen (2013), http://orsc.edu.cn/online/131020 which is called the uncertain multi-objective programming. In order to solve the proposed uncertain multi-objective programming, an interactive uncertain satisficing approach involving the decision-maker’s flexible demands is proposed in this paper. It makes an improvement in contrast to the noninteractive methods. Finally, a numerical example about the capital budget problem is given to illustrate the effectiveness of the proposed model and the relevant solving approach.     

Algorithm portfolio selection as a bandit problem with unbounded losses

We propose a method that learns to allocate computation time to a given set of algorithms, of unknown performance, with the aim of solving a given sequence of problem instances in a minimum time. Analogous meta-learning techniques are typically based on models of algorithm performance, learned during a separate offline training sequence, which can be prohibitively expensive. We adopt instead an online approach, named GAMBLETA, in which algorithm performance models are iteratively updated, and used to guide allocation on a sequence of problem instances. GAMBLETA is a general method for selecting among two or more alternative algorithm portfolios. Each portfolio has its own way of allocating computation time to the available algorithms, possibly based on performance models, in which case its performance is expected to improve over time, as more runtime data becomes available. The resulting exploration-exploitation trade-off is represented as a bandit problem. In our previous work, the algorithms corresponded to the arms of the bandit, and allocations evaluated by the different portfolios were mixed, using a solver for the bandit problem with expert advice, but this required the setting of an arbitrary bound on algorithm runtimes, invalidating the optimal regret of the solver. In this paper, we propose a simpler version of GAMBLETA, in which the allocators correspond to the arms, such that a single portfolio is selected for each instance. The selection is represented as a bandit problem with partial information, and an unknown bound on losses. We devise a solver for this game, proving a bound on its expected regret. We present experiments based on results from several solver competitions, in various domains, comparing GAMBLETA with another online method.     

Optimal stopping problems for multiarmed bandit processes with arms' independence

This paper deals with the optimal stopping problem for multiarmed bandit processes. Under the assumption of independence of arms we show that optimal strategies and stopping times are expressed by the dynamic allocation indices for each arm. This paper reduces this problem to several independent one-parameter optimal stopping problems. On the basis of these results, we characterize optimal strategies and stopping times. Moreover, this paper also extends those to the case allowing time constraints. In the case where arm's state evolve according to Markov chains with finite state, linear programming calculation of optimal strategies and stopping times is discussed.     

Controller design with multiple objectives

In this paper we study multi-objective control problems that give rise to equivalent convex optimization problems. We develop a uniform treatment of such problems by showing their equivalence to linear programming problems with equality constraints and an appropriate positive cone. We present some specialized results on duality theory, and we apply them to the study of three multi-objective control problems: the optimal l₁ control with time-domain constraints on the response to some fixed input, the mixed H₂/l₁ -control problem, and the l₁ control with magnitude constraint on the frequency response. What makes these problems complicated is that they are often equivalent to infinite-dimensional optimization problems. The characterization of the duality relationship between the primal and dual problem allows us to derive several results. These results establish connections with special convex problems (linear programming or linear matrix inequality problems), uncover finite-dimensional structures in the optimal solution, when possible, and provide finite-dimensional approximations to any degree of accuracy when the problem does not appear to have a finite-dimensional structure. To illustrate the theory and highlight its potential, several numerical examples are presented     

Path planning with multiple objectives

Most path planners are designed to generate a single path that is optimal in terms of some criterion such as path length or travel time. However, for realistic terrain navigation we wish to find a path that is reasonable to execute in a given environment. Therefore we must consider several factors, such as safety, time, and energy consumption. In this article the authors investigate how to find a set of paths (as opposed to a single path) so as to permit various choices concerning multiple criteria. They present simulation results to demonstrate the feasibility of the approach and discuss an extension to navigation in time-varying scenes     

Supplier selection in electronic marketplaces using satisficing and fuzzy AHP

Supplier selection is a critical and demanding task for companies that participate in electronic marketplaces to find suppliers and to execute electronically their transactions. This paper is aimed to suggest a fresh approach for decision support enabling effective supplier selection processes in electronic marketplaces. We introduce an evaluation method with two stages: initial screening of the suppliers through the enforcement of hard constraints on the selection criteria and final supplier evaluation through the application of a modified variant of the Fuzzy Preference Programming (FPP) method. The proposed method alleviates the information overload effect that is inherent in the environment of electronic marketplaces, facilitates an easier elicitation of user preferences through the reduction of necessary user input (i.e. pairwise comparisons) and reduces computational complexity, in terms of the number of linear programs to be solved, in comparison with the original FPP method. The FPP method is adopted and modified accordingly in order to tackle the issue of inconsistency/uncertainty of human preference models. Our approach is demonstrated with the example of a hypothetical metal manufacturing company that finds and selects suppliers in the environment of an electronic marketplace.     

Handling multiple objectives with biogeography-based optimization

Biogeography-based optimization (BBO) is a new evolutionary optimization method inspired by biogeography. In this paper, BBO is extended to a multi-objective optimization, and a biogeography-based multi-objective optimization (BBMO) is introduced, which uses the cluster attribute of islands to naturally decompose the problem. The proposed algorithm makes use of nondominated sorting approach to improve the convergence ability effciently. It also combines the crowding distance to guarantee the diversity of Pareto optimal solutions. We compare the BBMO with two representative state-of-the-art evolutionary multi-objective optimization methods, non-dominated sorting genetic algorithm-II (NSGA-II) and archive-based micro genetic algorithm (AMGA) in terms of three metrics. Simulation results indicate that in most cases, the proposed BBMO is able to find much better spread of solutions and converge faster to true Pareto optimal fronts than NSGA-II and AMGA do.     

Influence diagrams with multiple objectives and tradeoff analysis

Influence diagrams have been important models for decision problems because of their ability to both model a problem rigorously at its mathematical level and depict its high-level structure graphically. Once the structure and numerical details of an influence diagram have been specified, it can be evaluated to determine the optimal decision policy. However, when evaluating multiple objectives, in the past this determination was based on the assumption that utility functions that commensurate the objectives are available. This paper extends the structure and solution algorithm for influence diagrams to allow for the inclusion of noncommensurate objectives using multiobjective tradeoff analysis instead of utility theory. This eliminates the need to specify any preference information before the influence diagram is solved. The proposed multiobjective-based methodology is also useful for decision makers who either do not want to accept the assumptions of utility theory for a particular problem, or are confronted with a problem in which it is neither practical nor viable to construct a utility function. Additionally, this paper establishes the relationship between multiobjective influence diagrams and multiobjective decision trees. This relationship is important because it allows a decisionmaker to utilize the advantages of both representations. An example problem is presented to introduce both the extended multiobjective influence diagram methodology and the relationship linking multiobjective decision trees to multiobjective influence diagrams.     

Multi-objective scheduling with fuzzy due-date

In this paper, we examine the characteristic features of multi-objective scheduling problems formulated with the concept of fuzzy due-date. By computer simulations, we show that various scheduling criteria can be expressed by modifying the shape of membership functions of fuzzy due-dates. We also show the difficulty in handling the minimum satisfaction grade as a scheduling criterion. This difficulty is caused by the fact that the minimum satisfaction grade is zero for almost all schedules. This makes many search algorithms inefficient. We suggest an idea to cope with this difficulty.