Search

This study introduces a hybrid meta-heuristic for generating feasible course timetables in large-scale scenarios. We conducted tests using our university's instances. The current commercial software often struggles to meet constraints and takes hours to find satisfactory solutions. Our methodology combines adaptive large neighbourhood search, guided local search, variable neighbourhood search, and an innovative instance decomposition technique. Constraint violations from various groups are treated as objective functions to minimize. The search focuses on time slots with the most violations, and if no improvements are observed after a certain number of iterations, the most challenging constraint groups receive new weights to guide the search towards non-dominated solutions, even if the total sum of violations increases. In cases where this approach fails, a shaking phase is employed. The decomposition mechanism works by iteratively introducing curricula to the problem and finding new feasible solutions while considering an expanding set of lectures. Assignments from each iteration can be adjusted in subsequent iterations. Our methodology is tested on real-world instances from our university and random subdivisions. For subdivisions with 400 curricula timetables, decomposition reduced solution times by up to 27%. In real-world instances with 1,288 curricula timetables, the reduction was 18%. Clustering curricula with more common lectures and professors during increments improved solution times by 18% compared to random increments. Using our methodology, viable solutions for real-world instances are found in an average of 21 minutes, whereas the commercial software takes several hours.

We address the thesis defence scheduling problem, a critical academic scheduling management process, which has been overshadowed in the literature by its counterparts, course timetabling and exam scheduling. Specifically, the single defence assignment type of thesis defence scheduling problems, where each committee is assigned to a single defence, scheduled for a specific day, hour and room. We formulate a multi-objective mixed-integer linear programming model, which aims to be a general representation of the problem mentioned above, and that can, therefore, be applied to a broader set of cases than other models present in the literature, which have a focus on the characteristics of their universities. We introduce a new decision variable, propose constraint formulations that are not policy specific, and offer new takes on the more common objectives seen in the literature. We also include new objective functions based on our experience with the problem at our university. We also propose a two-stage solution approach. The first stage is employed to find the number of schedulable defences, enabling the optimisation of instances with unschedulable defences. The second stage is an implementation of the augmented e-constraint method, which allows for the search of a set of different and non-dominated solutions while skipping redundant iterations. A novel instance generator for thesis scheduling problems is presented. Its main benefit is the generation of the availability of committee members and rooms in availability and unavailability blocks, resembling their real-world counterparts. A set of 96 randomly generated instances of varying sizes is solved and analysed. The proposed method can find the optimal number of schedulable defences and present non-dominated solutions within the set time limits for every tested instance., Comment: 45 pages, 12 figures

Recently, it has been shown that the enumeration of Minimal Correction Subsets (MCS) of Boolean formulas allows solving Multi-Objective Boolean Optimization (MOBO) formulations. However, a major drawback of this approach is that most MCSs do not correspond to Pareto-optimal solutions. In fact, one can only know that a given MCS corresponds to a Pareto-optimal solution when all MCSs are enumerated. Moreover, if it is not possible to enumerate all MCSs, then there is no guarantee of the quality of the approximation of the Pareto frontier. This paper extends the state of the art for solving MOBO using MCSs. First, we show that it is possible to use MCS enumeration to solve MOBO problems such that each MCS necessarily corresponds to a Pareto-optimal solution. Additionally, we also propose two new algorithms that can find a (1 + {\varepsilon})-approximation of the Pareto frontier using MCS enumeration. Experimental results in several benchmark sets show that the newly proposed algorithms allow finding better approximations of the Pareto frontier than state-of-the-art algorithms, and with guaranteed approximation ratios.

The Covid-19 pandemic has caused impressive damages and disruptions in social, economic, and health systems (among others), and posed unprecedented challenges to public health and policy/decision-makers concerning the design and implementation of measures to mitigate its strong negative impacts. The Portuguese health authorities are currently using some decision analysis-like techniques to assess the impact of this pandemic and implementing measures for each county, region, or the whole country. Such decision tools led to some criticism and many stakeholders asked for novel approaches, in particular those having in consideration dynamical changes in the pandemic behavior arising, e.g., from new virus variants or vaccines. A multidisciplinary team formed by researchers of the Covid-19 Committee of Instituto Superior T\'ecnico at Universidade de Lisboa (CCIST analysts team) and medical doctors from the Crisis Office of the Portuguese Medical Association (GCOM experts team) gathered efforts and worked together in order to propose a new tool to help politicians and decision-makers in the combat of the pandemic. This paper presents the main steps and elements, which led to the construction of a pandemic impact assessment composite indicator, applied to the particular case of {\sc{Covid-19}} in Portugal. A multiple criteria approach based on an additive multi-attribute value theory (MAVT) aggregation model was used to construct the pandemic assessment composite indicator (PACI). The parameters of the additive model were built through a sociotechnical co-constructive interactive process between CCIST and GCOM team members. The deck of cards method was the technical tool adopted to help in building the value functions and the assessment of the criteria weights., Comment: 47 pages, 18 Figures

Dealing with multi-objective problems by using generation methods has some interesting advantages since it provides the decision-maker with the complete information about the set of non-dominated points (Pareto front) and a clear overview of the problem. However, providing many solutions to the decision-maker might also be overwhelming. As an alternative approach, presenting a representative set of solutions of the Pareto front may be advantageous. Choosing such a representative set is by itself also a multi-objective problem that must consider the number of solutions to present, the uniformity, and/or the coverage of the representation, to guarantee its quality. This paper proposes three algorithms for the representation problem for multi-objective integer linear programming problems with two or more objective functions, each one of them dealing with each dimension of the problem (cardinality, coverage, and uniformity). Such algorithms are all based on the $\epsilon$-constraint approach. In addition, the paper also presents strategies to overcome poor estimations of the Pareto front bounds. The algorithms were tested on the ability to efficiently generate the whole Pareto front or its representation. The uniformity and cardinality algorithms proved to be very efficient both in binary and integer problems, being amongst the best in the literature. Both coverage and uniformity algorithms provide good quality representations on their targeted objective, while the cardinality algorithm appears to be the most flexible, privileging uniformity for lower cardinality representations and coverage on higher cardinality.

This paper addresses the general problem of designing ordinal classification methods based on comparing actions with limiting boundaries of ordered classes (categories). The fundamental requirement of the method consists of setting a relational system (D,S), where S and D are reflexive and transitive relations, respectively, S should be compatible with the order of the set of classes, and D is a subset of S. An asymmetric preference relation P is defined from S. Other requirements are imposed on the actions which compose the limiting boundaries between adjacent classes, in such a way that each class is closed below and above. The paper proposes S-based and P-based assignment procedures. Each of them is composed of two complementary assignment procedures, which correspond through the transposition operation and should be used conjointly. The methods work under several basic conditions on the set of limiting boundaries. Under other more demanding separability requirements, each procedure fulfills the set of structural properties established for other outranking-based ordinal classification methods. Our proposal avoids the conflict between the required correspondence through the transposition operation and the assignment of limiting actions to the classes to which they belong. We thus propose very diverse S and P-based ordinal classification approaches with desirable properties, which can be designed by using decision models with the capacity to build preference relations fulfilling the basic requirements to S and D., Comment: 32 pages, 5 tables

The Paris Memorandum of Understanding on Port State Control (Paris MoU) is responsible for controlling substandard shipping in European waters and, consequently, increasing the standards of safety, pollution prevention, and onboard living and working conditions. Since 2011, the Memorandum adopted a system of points, named the "Ship Risk Profile" (SRP), under which each ship is assigned a risk profile according to its score on a set of criteria. Being a multiple criteria decision aiding (MCDA) tool at its core, comprising criteria, weights, and risk categories, limited research has been performed on the SRP from an MCDA perspective. The purpose of this paper is to propose an MCDA approach for ship risk classification through the Deck of Cards Method (DCM). The DCM is particularly suitable within this context as it allows, intuitively for the decision-maker, to model preference among different criteria and among different levels on criteria scales. First, a framework is built, based on the criteria established in the SRP. Second, the DCM is used to build the MCDA model, including the definition of the criteria value functions and criteria weights. Finally, the proposed MCDA model is applied to a dataset of ships and the results are discussed. Robust results have been obtained with the proposed approach, making it a potential alternative to the current SRP., Comment: 32 pages, 2 figures

Assessing the technical efficiency of a set of observations requires that the associated data composed of inputs and outputs are perfectly known. If this is not the case, then biased estimates will likely be obtained. Data Envelopment Analysis (DEA) is one of the most extensively used mathematical models to estimate efficiency. It constructs a piecewise linear frontier against which all observations are compared. Since the frontier is empirically defined, any deviation resulting from low data quality (imperfect knowledge of data or IKD) may lead to efficiency under/overestimation. In this study, we model IKD and, then, apply the so-called Hit \& Run procedure to randomly generate admissible observations, following some prespecified probability density functions. Sets used to model IKD limit the domain of data associated with each observation. Any point belonging to that domain is a candidate to figure out as the observation for efficiency assessment. Hence, this sampling procedure must run a sizable number of times (infinite, in theory) in such a way that it populates the whole sets. The DEA technique is used during the execution of each iteration to estimate bootstrapped efficiency scores for each observation. We use some scenarios to show that the proposed routine can outperform some of the available alternatives. We also explain how efficiency estimations can be used for statistical inference. An empirical case study based on the Portuguese public hospitals database (2013-2016) was addressed using the proposed method.

Parity check matrices (PCMs) are used to define linear error correcting codes and ensure reliable information transmission over noisy channels. The set of codewords of such a code is the null space of this binary matrix. We consider the problem of minimizing the number of one-entries in parity-check matrices. In the maximum-likelihood (ML) decoding method, the number of ones in PCMs is directly related to the time required to decode messages. We propose a simple matrix row manipulation heuristic which alters the PCM, but not the code itself. We apply simulated annealing and greedy local searches to obtain PCMs with a small number of one entries quickly, i.e. in a couple of minutes or hours when using mainstream hardware. The resulting matrices provide faster ML decoding procedures, especially for large codes., Comment: This work was supported by Funda\c{c}\~ao para a Ci\^encia e Tecnologia (FCT) ref. UID/CEC/50021/2019; European Union's Horizon 2020, Marie Sk{\l}odowska-Curie Actions grant agreement No 690941; The DAAD-CRUP Luso-German bilateral cooperation 2017-2018 research project MONO-EMC; The DFG (project-ID: RU 1524/2-3). Jos{\'e} Rui Figueira acknowledges FCT grant SFRH/BSAB/139892/2018

A variant of the classical knapsack problem is considered in which each item is associated with an integer weight and a qualitative level. We define a dominance relation over the feasible subsets of the given item set and show that this relation defines a preorder. We propose a dynamic programming algorithm to compute the entire set of non-dominated rank cardinality vectors and we state two greedy algorithms, which efficiently compute a single efficient solution.

In this paper we present (to the best of our knowledge) the first outranking method to assign a score to each alternative. It is a method of the Electre family, and we will call it Electre-Score. Contrarily to the Multi-Attribute Value Theory methods, Electre-Score does not construct a value function for each criterion, and then proceeds to the aggregation into a single value. It rather, makes use of the outranking relations to make a comparison with reference sets of actions (to which a score is assigned) and proposes a score range to each alternative, instead of a single value. This is a more robust way of proceeding given the fragility of a single score. The sets of limiting profiles are defined with the help of Electre Tri-nB and the reference scores are assigned to them through the application of the deck of cards technique. The fact of being able to use outranking relations, makes it also possible to take into account the imperfect knowledge of data and avoids systematic compensatory effects. Some fundamental theoretical results guaranteeing the consistency of the method and an illustrative example are also provided in this paper.

CAT-SD (CATegorization by Similarity-Dissimilarity) is a recently developed method for handling nominal classification problems in the context of Multiple Criteria Decision Aiding (MCDA). This paper describes the design and implementation of this method, as well as an application dealing with a recruitment process in the Special Forces of the Portuguese Army. In addition, it proposes interaction protocols to elicit the preference parameters of the method to facilitate the construction of a decision model when the analyst guides the decision maker. CAT-SD has been implemented in DecSpace, a user-friendly on-line platform for supporting decision aiding processes using one or more MCDA methods. The study related to the Portuguese Army Special Forces recruitment presents and demonstrates how these protocols and a tool like DecSpace can facilitate the process of applying the method in real-world scenarios.

This paper deals with an improved version of the deck of the cards method to render the construction of the ratio and interval scales more `accurate'. The improvement comes from the fact that we can account for a richer and finer preference information provided by the decision-makers, which permits a more accurate modelling of the strength of preference between two consecutive levels of a scale. Instead of considering only the number of blank cards between consecutive positions in the ranking of objects such as criteria and scale levels, we consider also the number of blank cards between non consecutive positions in the ranking. This information is collected in a pairwise comparison table that it is not necessarily built with precise values. We can consider also missing information and imprecise information provided in the form of ranges. Since the information provided by the decision-makers is not necessarily consistent, we propose also some procedures to help the decision-maker to make consistent his evaluations in a co-constructive way interacting with an analyst and reflecting and revising her/his judgments. The method is illustrated through and example in which, generalizing the SWING method, interacting criteria are aggregated through the Choquet integral.

We propose a new method for analyzing a set of parameters in a multiple criteria ranking method. Unlike the existing techniques, we do not use any optimization technique, instead incorporating and extending a Segmenting Description approach. While considering a value-based preference disaggregation method, we demonstrate the usefulness of the introduced algorithm in a multi-purpose decision analysis exploiting a system of inequalities that models the Decision Maker's preferences. Specifically, we discuss how it can be applied for verifying the consistency between the revealed and estimated preferences as well as for identifying the sources of potential incoherence. Moreover, we employ the method for conducting robustness analysis, i.e., discovering a set of all compatible parameter values and verifying the stability of suggested recommendation in view of multiplicity of feasible solutions. In addition, we make clear its suitability for generating arguments about the validity of outcomes and the role of particular criteria. We discuss the favorable characteristics of the Segmenting Description approach which enhance its suitability for use in Multiple Criteria Decision Aiding. These include keeping in memory an entire process of transforming a system of inequalities and avoiding the need for processing the inequalities contained in the basic system which is subsequently enriched with some hypothesis to be verified. The applicability of the proposed method is exemplified on a numerical study., Comment: 28 pages

This paper presents a new methodology that combines a multiple criteria sorting or ranking method with a project portfolio selection procedure. The multicriteria method permits to compare projects in terms of their priority assessed on the basis of a set of both qualitative and quantitative criteria. Then, a feasible set of projects, i.e. a portfolio, is selected according to the priority defined by the multiple criteria method. In addition, the portfolio must satisfy a set of resources constraints, e.g. budget available, as well as some logical constraints, e.g. related to projects to be selected together or projects mutually exclusive. The proposed portfolio selection methodology can be applied in different contexts. We present an application in the urban planning domain where our approach allows to select a set of urban projects on the basis of their priority, budgetary constraints and urban policy requirements. Given the increasing interest of historical cities to reuse their cultural heritage, we applied and tested our methodology in this context. In particular, we show how the methodology can support the prioritization of the interventions on buildings with some historical value in the historic city center of Naples (Italy), taking into account several points of view.

Cat-SD is a multiple criteria decision aiding method for dealing with nominal classification problems. Actions are assessed according to multiple criteria and assigned to one or more categories. A set of reference actions is used for defining each category. The assignment of an action to a given category depends on the comparison of the action to each reference set according to likeness thresholds. Distinct sets of criteria weights, interaction coefficients, and likeness thresholds can be defined per category. We propose to apply Multiple Criteria Hierarchy Process (MCHP) to Cat-SD. An adapted MCHP is proposed to take into account possible interaction effects between criteria structured in a hierarchical way. On the basis of the known deck of cards method, we also consider an imprecise elicitation of parameters permitting to take into account interactions and antagonistic effects between criteria. The elicitation procedure we are proposing can be applied to any Electre method. With the purpose of exploring the assignments obtained by Cat-SD considering possible sets of parameters, we propose to apply the Stochastic Multicriteria Acceptability Analysis (SMAA). The SMAA methodology allows to draw statistical conclusions on the classification of the actions. The proposed method, SMAA-hCat-SD, helps the decision maker to check the effects of the variation of parameters on the classification at different levels of the hierarchy. We propose also a procedure, based on the concept of loss function, to obtain a final classification fulfilling some requirements given by the decision maker and taking into account the hierarchy of criteria and the probabilistic assignments obtained applying SMAA. Also this procedure can be applied to any classification Electre method.

We investigate the single-source-single-destination "shortest" paths problem in acyclic graphs with ordinal weighted arc costs. We define the concepts of ordinal dominance and efficiency for paths and their associated ordinal levels, respectively. Further, we show that the number of ordinally non-dominated paths vectors from the source node to every other node in the graph is polynomially bounded and we propose a polynomial time labeling algorithm for solving the problem of finding the set of ordinally non-dominated paths vectors from source to sink., Comment: 24 pages, 8 figures, 2 tables