Multiple Criteria Decision Making (MCDM) is all about making choices in the presence of multiple conflicting criteria. MCDM has become one of the most important and fastest growing subfields of ...Operations Research/Management Science. As modern MCDM started to emerge about 50 years ago, it is now a good time to take stock of developments. This book aims to present an informal, nontechnical history of MCDM, supplemented with many pictures. It covers the major developments in MCDM, from early history until now. It also covers fascinating discoveries by Nobel Laureates and other prominent scholars.
•There may not exist uniform prices in day-ahead electricity markets.•Market operators aim for partial-equilibrium solutions.•Pricing variables are associated with the surplus maximization ...problem.•Pricing cuts improve solution quality and computational performance substantially.•The new algorithm leads to important surplus improvements.
We study the day-ahead electricity market clearing problem under the prevailing market design in the European electricity markets. We revisit the Benders decomposition algorithm that has been used to solve this problem. We develop new valid inequalities that substantially improve the performance of the algorithm. We generate instances that mimic the characteristics of past bids of the Turkish day-ahead electricity market and conduct experiments. We use two leading mixed-integer programming solvers, IBM ILOG Cplex and Gurobi, in order to assess the impact of employed solver on the algorithm performance. We compare the performances of our algorithm, the primal-dual algorithm, and the Benders decomposition algorithm using the existing cuts from the literature. The extensive experiments we conduct demonstrate that the price-based cuts we develop improve the performance of the Benders decomposition algorithm and outperform the primal-dual algorithm.
•We develop a preference-based MOEA to converge to reference points.•The decision maker may change reference points throughout the algorithm.•The algorithm quickly adapts to changes in the reference ...points.•We develop specific mechanisms for route planning of unmanned air vehicles (UAVs).•This is the first preference-based MOEA developed for UAV route planning.
We study the multi-objective route planning problem of an unmanned air vehicle (UAV) moving in a continuous terrain. In this problem, the UAV starts from a base, visits all targets and returns to the base in a continuous terrain that is monitored by radars. We consider two objectives: minimizing total distance and minimizing radar detection threat. This problem has infinitely many Pareto-optimal points and generating all those points is not possible. We develop a general preference-based multi-objective evolutionary algorithm to converge to preferred solutions. Preferences of a decision maker (DM) are elicited through reference point(s) and the algorithm converges to regions of the Pareto-optimal frontier close to the reference points. The algorithm allows the DM to change his/her reference point(s) whenever he/she so wishes. We devise mechanisms to prevent the algorithm from producing dominated points at the final population. We also develop mechanisms specific to the UAV route planning problem and test the algorithm on several UAV routing problems as well as other well-known problem instances. We demonstrate that our algorithm converges to preferred regions on the Pareto-optimal frontier and adapts to changes in the reference points quickly.
We develop exact algorithms for multi-objective integer programming (MIP) problems. The algorithms iteratively generate nondominated points and exclude the regions that are dominated by the ...previously-generated nondominated points. One algorithm generates new points by solving models with additional binary variables and constraints. The other algorithm employs a search procedure and solves a number of models to find the next point avoiding any additional binary variables. Both algorithms guarantee to find all nondominated points for any MIP problem. We test the performance of the algorithms on randomly-generated instances of the multi-objective knapsack, multi-objective shortest path and multi-objective spanning tree problems. The computational results show that the algorithms work well.
•Representative sets are found for multi-objective mixed integer programs.•A desired level of quality is guaranteed in representing the nondominated frontier.•The methods are computationally ...efficient based on extensive computational tests.
In this paper, we develop algorithms to find small representative sets of nondominated points that are well spread over the nondominated frontiers for multi-objective mixed integer programs. We evaluate the quality of representations of the sets by a Tchebycheff distance-based coverage gap measure. The first algorithm aims to substantially improve the computational efficiency of an existing algorithm that is designed to continue generating new points until the decision maker (DM) finds the generated set satisfactory. The algorithm improves the coverage gap value in each iteration by including the worst represented point into the set. The second algorithm, on the other hand, guarantees to achieve a desired coverage gap value imposed by the DM at the outset. In generating a new point, the algorithm constructs territories around the previously generated points that are inadmissible for the new point based on the desired coverage gap value. The third algorithm brings a holistic approach considering the solution space and the number of representative points that will be generated together. The algorithm first approximates the nondominated set by a hypersurface and uses it to plan the locations of the representative points. We conduct computational experiments on randomly generated instances of multi-objective knapsack, assignment, and mixed integer knapsack problems and show that the algorithms work well.
•An exact algorithm is developed for multi-objective mixed integer programs.•Small representative sets guaranteeing a prespecified precision are found.•Problem-specific information is utilised to ...select points from dense regions.•The algorithm is efficient based on extensive computational tests.
In this paper, we consider generating a representative subset of nondominated points at a prespecified precision in multi-objective mixed-integer programs (MOMIPs). The number of nondominated points grows exponentially with problem size and finding all nondominated points is typically hard in MOMIPs. Representing the nondominated set with a small subset of nondominated points is important for a decision maker to get an understanding of the layout of solutions. The shape and density of the nondominated points over the objective space may be critical in obtaining a set of solutions that represent the nondominated set well. We develop an exact algorithm that generates a representative set guaranteeing a prespecified precision. Our experiments on a variety of problems demonstrate that our algorithm outperforms existing approaches in terms of both the cardinality of the representative set and computation times.
We address the route planning problem of an unmanned air vehicle (UAV) tasked with collecting information from a radar-monitored environment for a reconnaissance mission. The UAV takes off from a ...home base, visits a set of targets, and finishes its movement at a final base. Collectable information at a target depends on the time the target is visited by the UAV. There are multiple trajectory alternatives between the target pairs with different travel time and threat attributes. A route plan involves the selection of the targets to visit, the order of visit to the targets, and the trajectories to follow between the targets. Multiple routing objectives, information collection, mission duration and mission safety, are considered to present the trade-offs among the objectives to the route planner. The problem is classified as a multi-objective orienteering problem with time-dependent prizes and multiple connection options. A mixed integer programming model that can be used for small-sized problems is formulated. Larger problems are addressed with a hybrid algorithm involving heuristics and exact approaches. A case study based on a terrain in the State of Colorado is presented. Finally, some practical issues for the UAV route planning problem is discussed.
•Routing a UAV for reconnaissance under radar surveillance.•Multiple objectives, time-dependent prizes, and multiple connections are considered.•A new type of orienteering problem is introduced.•An MIP model and a hybrid solution algorithm including a heuristic are developed.•A case study based on the terrain properties of the State of Colorado is presented.
•Finds all efficient routes of an UAV considering distance and threat objectives.•The UAV can move to any point in the continuous space.•Characterizes efficient trajectories between target pairs by a ...fitted curve.•Outperforms discretized case in solution quality and computational effort.
We consider the route planning problem of an unmanned air vehicle (UAV) in a continuous space that is monitored by radars. The UAV visits multiple targets and returns to the base. The routes are constructed considering the total distance traveled and the total radar detection threat objectives. The UAV is capable of moving to any point in the terrain. This leads to infinitely many efficient trajectories between target pairs and infinitely many efficient routes to visit all targets. We use a two stage approach in solving the complex problem of finding all efficient routes. In the first stage, we structure the nondominated frontiers of the efficient trajectories between all target pairs. For this, we first identify properties shared by efficient trajectories between target pairs that are protected by a radar. This helps to structure the nondominated frontier between any target pair by identifying at most four specific efficient trajectories. We develop a search-based algorithm that finds these efficient trajectories effectively. For the second stage, we develop a mixed integer nonlinear program that exploits the structured nondominated frontiers between target pairs to construct the efficient routes. We compare the nondominated front we generate in the continuous space with its counterpart in a terrain discretized with three different grid fidelities. The continuous space representation outperforms all discrete representations in terms of solution quality and computational times.
Preference functions have been widely used to scalarize multiple objectives. Various forms such as linear, quasiconcave, or general monotone have been assumed. In this article, we consider a general ...family of functions that can take a variety of forms and has properties that allow for estimating the form efficiently. We exploit these properties to estimate the form of the function and converge towards a preferred solution(s). We develop the theory and algorithms to efficiently estimate the parameters of the function that best represent a decision maker's preferences. This in turn facilitates fast convergence to preferred solutions. We demonstrate on a variety of experiments that the algorithms work well both in estimating the form of the preference function and converging to preferred solutions.
In this paper, we present an exact algorithm to find all extreme supported nondominated points of multiobjective mixed integer programs. The algorithm uses a composite linear objective function and ...finds all the desired points in a finite number of steps by changing the weights of the objective functions in a systematic way. We develop further variations of the algorithm to improve its computational performance and demonstrate our algorithm's performance on multiobjective assignment, knapsack, and traveling salesperson problems with three and four objectives.
PDF
