Academic literature on the topic 'Fair combinatorial optimization'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Fair combinatorial optimization.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Journal articles on the topic "Fair combinatorial optimization"
1
Bourdache, Nadjet, and Patrice Perny. "Active Preference Learning Based on Generalized Gini Functions: Application to the Multiagent Knapsack Problem." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 7741–48. http://dx.doi.org/10.1609/aaai.v33i01.33017741.
Full textAbstract:
We consider the problem of actively eliciting preferences from a Decision Maker supervising a collective decision process in the context of fair multiagent combinatorial optimization. Individual preferences are supposed to be known and represented by linear utility functions defined on a combinatorial domain and the social utility is defined as a generalized Gini Social evaluation Function (GSF) for the sake of fairness. The GSF is a non-linear aggregation function parameterized by weighting coefficients which allow a fine control of the equity requirement in the aggregation of individual utilities. The paper focuses on the elicitation of these weights by active learning in the context of the fair multiagent knapsack problem. We introduce and compare several incremental decision procedures interleaving an adaptive preference elicitation procedure with a combinatorial optimization algorithm to determine a GSF-optimal solution. We establish an upper bound on the number of queries and provide numerical tests to show the efficiency of the proposed approach.
2
Wang, Kai, Haoyu Liu, Zhipeng Hu, Xiaochuan Feng, Minghao Zhao, Shiwei Zhao, Runze Wu, Xudong Shen, Tangjie Lv, and Changjie Fan. "EnMatch: Matchmaking for Better Player Engagement via Neural Combinatorial Optimization." Proceedings of the AAAI Conference on Artificial Intelligence 38, no. 8 (March 24, 2024): 9098–106. http://dx.doi.org/10.1609/aaai.v38i8.28760.
Full textAbstract:
Matchmaking is a core task in e-sports and online games, as it contributes to player engagement and further influences the game's lifecycle. Previous methods focus on creating fair games at all times. They divide players into different tiers based on skill levels and only select players from the same tier for each game. Though this strategy can ensure fair matchmaking, it is not always good for player engagement. In this paper, we propose a novel Engagement-oriented Matchmaking (EnMatch) framework to ensure fair games and simultaneously enhance player engagement. Two main issues need to be addressed. First, it is unclear how to measure the impact of different team compositions and confrontations on player engagement during the game considering the variety of player characteristics. Second, such a detailed consideration on every single player during matchmaking will result in an NP-hard combinatorial optimization problem with non-linear objectives. In light of these challenges, we turn to real-world data analysis to reveal engagement-related factors. The resulting insights guide the development of engagement modeling, enabling the estimation of quantified engagement before a match is completed. To handle the combinatorial optimization problem, we formulate the problem into a reinforcement learning framework, in which a neural combinatorial optimization problem is built and solved. The performance of EnMatch is finally demonstrated through the comparison with other state-of-the-art methods based on several real-world datasets and online deployments on two games.
3
MOULIN, HERVÉ. "COST SHARING IN NETWORKS: SOME OPEN QUESTIONS." International Game Theory Review 15, no. 02 (June 2013): 1340001. http://dx.doi.org/10.1142/s021919891340001x.
Full textAbstract:
The fertile application of cooperative game techniques to cost sharing problems on networks has so far concentrated on the Stand Alone core test of fairness and/or stability, and ignored many combinatorial optimization problems where this core can be empty. I submit there is much room for an axiomatic discussion of fair division in the latter problems, where Stand Alone objections are not implementable. But the computational complexity of optimal solutions is still a very severe obstacle to this approach.
4
Adubi, Stephen A., Olufunke O. Oladipupo, and Oludayo O. Olugbara. "Evolutionary Algorithm-Based Iterated Local Search Hyper-Heuristic for Combinatorial Optimization Problems." Algorithms 15, no. 11 (October 31, 2022): 405. http://dx.doi.org/10.3390/a15110405.
Full textAbstract:
Hyper-heuristics are widely used for solving numerous complex computational search problems because of their intrinsic capability to generalize across problem domains. The fair-share iterated local search is one of the most successful hyper-heuristics for cross-domain search with outstanding performances on six problem domains. However, it has recorded low performances on three supplementary problems, namely knapsack, quadratic assignment, and maximum-cut problems, which undermines its credibility across problem domains. The purpose of this study was to design an evolutionary algorithm-based iterated local search (EA-ILS) hyper-heuristic that applies a novel mutation operator to control the selection of perturbative low-level heuristics in searching for optimal sequences for performance improvement. The algorithm was compared to existing ones in the hyper-heuristics flexible (HyFlex) framework to demonstrate its performance across the problem domains of knapsack, quadratic assignment, and maximum cut. The comparative results have shown that the EA-ILS hyper-heuristic can obtain the best median objective function values on 22 out of 30 instances in the HyFlex framework. Moreover, it has achieved superiority in its generalization capability when compared to the reported top-performing hyper-heuristic algorithms.
5
Maleš, Uroš, Dušan Ramljak, Tatjana Jakšić Krüger, Tatjana Davidović, Dragutin Ostojić, and Abhay Haridas. "Controlling the Difficulty of Combinatorial Optimization Problems for Fair Proof-of-Useful-Work-Based Blockchain Consensus Protocol." Symmetry 15, no. 1 (January 3, 2023): 140. http://dx.doi.org/10.3390/sym15010140.
Full textAbstract:
The wide range of Blockchain (BC) applications and BC’s ubiquity come from the fact that BC, as a collection of records linked to each other, is strongly resistant to alteration, protected using cryptography, and maintained autonomously. All these benefits come with a cost, which in BC is expressed by a very high use of energy needed to execute consensus protocols. Traditionally, consensus protocols based on Proof-of-Work (PoW) ensure fairness, but are not very useful. The paradigm proposed in the recent literature, known as Proof-of-Useful-Work (PoUW), assumes the completion of additional useful work for the same amount of resources (energy) used. However, the majority of the proposed PoUW approaches do not adequately consider fairness in balancing and controlling the difficulty of the work miners need to perform. A minority of the studies that do address fairness in miners’ work utilize PoW as a tool to ensure it. Therefore, a general framework to provide a structure for understanding the difficulty of useful work and how it can be used to fine-tune the complexity of miners’ effort in PoUW-based consensus protocols is proposed in this paper. The main characteristic of the proposed framework is that controlling the difficulty and fairness of miners’ work in PoUW-based consensus protocols is achieved exclusively through the useful work. The modules of the framework are discussed, and many research challenges and opportunities are articulated. The benefits of the proposed approach are illustrated taking as an example two optimization algorithms for a variant of the scheduling problem. In addition, the steps that should be taken to make this general framework applicable to any PoUW-based consensus protocols are identified.
6
Wang, Zhenzhong, Qingyuan Zeng, Wanyu Lin, Min Jiang, and Kay Chen Tan. "Generating Diagnostic and Actionable Explanations for Fair Graph Neural Networks." Proceedings of the AAAI Conference on Artificial Intelligence 38, no. 19 (March 24, 2024): 21690–98. http://dx.doi.org/10.1609/aaai.v38i19.30168.
Full textAbstract:
A plethora of fair graph neural networks (GNNs) have been proposed to promote algorithmic fairness for high-stake real-life contexts. Meanwhile, explainability is generally proposed to help machine learning practitioners debug models by providing human-understandable explanations. However, seldom work on explainability is made to generate explanations for fairness diagnosis in GNNs. From the explainability perspective, this paper explores the problem of what subgraph patterns cause the biased behavior of GNNs, and what actions could practitioners take to rectify the bias? By answering the two questions, this paper aims to produce compact, diagnostic, and actionable explanations that are responsible for discriminatory behavior. Specifically, we formulate the problem of generating diagnostic and actionable explanations as a multi-objective combinatorial optimization problem. To solve the problem, a dedicated multi-objective evolutionary algorithm is presented to ensure GNNs' explainability and fairness in one go. In particular, an influenced nodes-based gradient approximation is developed to boost the computation efficiency of the evolutionary algorithm. We provide a theoretical analysis to illustrate the effectiveness of the proposed framework. Extensive experiments have been conducted to demonstrate the superiority of the proposed method in terms of classification performance, fairness, and interpretability.
7
Rokbani, Nizar, Pavel Kromer, Ikram Twir, and Adel M. Alimi. "A Hybrid Hierarchical Heuristic-ACO With Local Search Applied to Travelling Salesman Problem, AS-FA-Ls." International Journal of System Dynamics Applications 9, no. 3 (July 2020): 58–73. http://dx.doi.org/10.4018/ijsda.2020070104.
Full textAbstract:
The combinatorial optimization problem is attracting research because they have a wide variety of applications ranging from route planning and supply chain optimization to industrial scheduling and the IoT. Solving such problems using heuristics and bio-inspired techniques is an alternative to exact solutions offering acceptable solutions at fair computational costs. In this article, a new hierarchical hybrid method is proposed as a hybridization of Ant Colony Optimization (ACO), Firefly Algorithm (FA), and local search (AS-FA-Ls). The proposed methods are compared to similar techniques on the traveling salesman problem, (TSP). ACO is used in a hierarchical collaboration schema together with FA which is used to adapt ACO parameters. A local search strategy is used which is the 2 option method to avoid suboptimal solutions. A comparative review and experimental investigations are conducted using the TSP benchmarks. The results showed that AS-FA-Ls returned better results than the listed works in the following cases: berlin52, st70, eil76, rat99, kroA100, and kroA200. Computational investigations allowed determining a set of recommended parameters to be used with ACO for the TSP instances of the study.
8
Lujak, Marin, Stefano Giordani, Andrea Omicini, and Sascha Ossowski. "Decentralizing Coordination in Open Vehicle Fleets for Scalable and Dynamic Task Allocation." Complexity 2020 (July 16, 2020): 1–21. http://dx.doi.org/10.1155/2020/1047369.
Full textAbstract:
One of the major challenges in the coordination of large, open, collaborative, and commercial vehicle fleets is dynamic task allocation. Self-concerned individually rational vehicle drivers have both local and global objectives, which require coordination using some fair and efficient task allocation method. In this paper, we review the literature on scalable and dynamic task allocation focusing on deterministic and dynamic two-dimensional linear assignment problems. We focus on multiagent system representation of open vehicle fleets where dynamically appearing vehicles are represented by software agents that should be allocated to a set of dynamically appearing tasks. We give a comparison and critical analysis of recent research results focusing on centralized, distributed, and decentralized solution approaches. Moreover, we propose mathematical models for dynamic versions of the following assignment problems well known in combinatorial optimization: the assignment problem, bottleneck assignment problem, fair matching problem, dynamic minimum deviation assignment problem, Σk-assignment problem, the semiassignment problem, the assignment problem with side constraints, and the assignment problem while recognizing agent qualification; all while considering the main aspect of open vehicle fleets: random arrival of tasks and vehicles (agents) that may become available after assisting previous tasks or by participating in the fleet at times based on individual interest.
9
Li, Xia, and Buhong Wang. "Thinned Virtual Array for Cramer Rao Bound Optimization in MIMO Radar." International Journal of Antennas and Propagation 2021 (January 15, 2021): 1–13. http://dx.doi.org/10.1155/2021/1408498.
Full textAbstract:
By transmitting multiple independent waveforms at the transmit side and processing echoes of spatial targets at the receive side, Multiple Input Multiple Output (MIMO) radar enjoys virtual array aperture expansion and more degree of freedom (DOF), both of which favors the application of direction finding or estimation of direction of arrival (DOA). The expanded virtual aperture provides higher angular resolution which also promotes the precision of DOA estimation, and the extra DOF brought by waveform diversity can be leveraged to focus energy in certain spatial region for better direction-finding capacity. However, beamspace methods which match certain beampatterns suffer from deteriorated performance and complexity in implementation, and the advantage of virtual array aperture is limited by its virtual element redundancy. As an important performance indicator of DOA estimation, Cramer–Rao Bound (CRB) is closely connected to the array configuration of the system. To reduce the complexity of the system and improve CRB performance at the same time, in this paper, the virtual array of MIMO radar is designed directly by selecting outputs from matched filters at the receive side. For the sake of fair comparison, both scenarios with and without priori directions are considered to obtain optimized virtual array configuration, respectively. The original combinatorial problems are approximated by sequential convex approximations methods which produce solutions with efficiency. Numerical results demonstrate that the proposed method can provide thinned virtual arrays with excellent CRB performance.
10
Khaled, Smail, and Djebbar Bachir. "Electromagnetism-like mechanism algorithm for hybrid flow-shop scheduling problems." Indonesian Journal of Electrical Engineering and Computer Science 32, no. 3 (December 1, 2023): 1614. http://dx.doi.org/10.11591/ijeecs.v32.i3.pp1614-1620.
Full textAbstract:
<span>Given the interest and complexity, of the hybrid flow shops (HFS) problem in industry, he has been extensively considered, the HFS, is a complex combinatorial problem supported in many original world applications. We consider a hybrid flow shop FH4(P3, P2)||C<sub>max</sub> to applied in this paper. In this papers we attempt to optimize the makespan which refers to the last task completion time by an adequate meta-heuristic algorithm based on electromagnetism mechanism (EM). We also present analysis on the performance of the EM-algorithm adapted to HFS scheduling problems. The electromagnetism-like mechanism method gave us efficient and fair results comparing to particle swarm and genetic algorithm.</span>
Dissertations / Theses on the topic "Fair combinatorial optimization"
1
Vo, Thi Quynh Trang. "Algorithms and Machine Learning for fair and classical combinatorial optimization." Electronic Thesis or Diss., Université Clermont Auvergne (2021-...), 2024. http://www.theses.fr/2024UCFA0035.
Full textAbstract:
L'optimisation combinatoire est un domaine des mathématiques dans lequel un problème consiste à trouver une solution optimale dans un ensemble fini d'objets. Elle a des applications cruciales dans de nombreux domaines. Le branch-and-cut est l'un des algorithmes les plus utilisés pour résoudre exactement des problèmes d'optimisation combinatoire. Dans cette thèse, nous nous concentrons sur les aspects informatiques du branch-and-cut et plus particulièrement, sur deux aspects importants de l'optimisation combinatoire: l'équité des solutions et l'intégration de l'apprentissage automatique. Dans la partie I, nous étudions deux approches courantes pour traiter la question de l'équité dans l'optimisation combinatoire, qui a fait l'objet d'une attention particulière au cours des dernières décennies. La première approche est l'optimisation combinatoire équilibrée, qui trouve une solution équitable en minimisant la différence entre les plus grands et les plus petits composants utilisés. En raison des difficultés à délimiter ces composants, aucun cadre général exact basé sur la programmation linéaire en nombres entiers mixtes (MILP) n'a été proposé pour l'optimisation combinatoire équilibrée. Pour combler cette lacune, nous présentons au chapitre 3 une nouvelle classe de plans de coupe locaux adaptés aux problèmes d'optimisation combinatoire équilibrée pour l'algorithme du branch-and-cut. Nous démontrons l'efficacité de la méthode proposée dans la cadre du problème du voyageur de commerce équilibré. Notamment, nous introduisons des algorithmes pour trouver des bornes et des mécanismes pour la détermination des variables afin d'accélérer un peu plus les performances. Une deuxième approche pour traiter l'équité est l'optimisation combinatoire Ordered Weighted Average (OWA), qui utilise l'opérateur OWA dans la fonction objectif. En raison de l'opérateur d'ordonnancement, l'optimisation combinatoire OWA est non linéaire, même si ses contraintes d'origine sont linéaires. Deux formulations MILP de tailles différentes ont été introduites dans la littérature pour linéariser l'opérateur OWA. Cependant, la formulation la plus performante pour l'optimisation combinatoire OWA reste incertaine, car l'intégration des méthodes de linéarisation peut introduire des difficultés supplémentaires. Dans le chapitre 4, nous fournissons des comparaisons théoriques et empiriques des deux formulations MILP pour l'optimisation combinatoire OWA. En particulier, nous prouvons que les formulations sont équivalentes en termes de relaxation de programmation linéaire. Nous montrons empiriquement que pour les problèmes d'optimisation combinatoire OWA, la formulation avec le plus de variables peut être résolue plus rapidement avec le branch-and-cut. Dans la partie II, nous développons des méthodes d'application de l'apprentissage automatique pour améliorer les problèmes de décision fondamentaux du branch-and-cut, en mettant l'accent sur la génération de coupes. Ce dernier problème se réfère à la décision de générer des coupes ou des branches à chaque nœud de l'arbre de recherche. Nous démontrons empiriquement que cette décision a un impact significatif sur les performances du branch-and-cut, en particulier pour les coupes combinatoires qui exploitent les faces de la coque convexe des solutions réalisables. Nous proposons ensuite un cadre général combinant l'apprentissage supervisé et l'apprentissage par renforcement afin d'apprendre des stratégies efficaces pour générer des coupes combinatoires dans la méthode branch-and-cut. Notre cadre comporte deux composantes : un détecteur de coupes pour prédire l'existence de coupes et un évaluateur de coupes pour choisir entre la génération de coupes et le branchement. Enfin, nous fournissons des résultats expérimentaux montrant que la méthode proposée est plus performante que les stratégies couramment utilisées pour la génération de coupes, même sur des instances plus grandes que celles utilisées pour l'apprentissageCombinatorial optimization is a field of mathematics that searches for an optimal solution in a finite set of objects. It has crucial applications in many fields, including applied mathematics, software engineering, theoretical computer science, and machine learning. extit{Branch-and-cut} is one of the most widely-used algorithms for solving combinatorial optimization problems exactly. In this thesis, we focus on the computational aspects of branch-and-cut when studying two critical dimensions of combinatorial optimization: extit{the fairness of solutions} and extit{the integration of machine learning}.In Partef{part:1} (Chaptersef{chap:bnc-btsp} andef{chap:owa}), we study two common approaches to deal with the issue of fairness in combinatorial optimization, which has gained significant attention in the past decades. The first approach is extit{balanced combinatorial optimization}, which finds a fair solution by minimizing the difference between the largest and smallest components used. Due to the difficulties in bounding these components, to the best of our knowledge, no general exact framework based on mixed-integer linear programming (MILP) has been proposed for balanced combinatorial optimization. To address this gap, in Chapteref{chap:bnc-btsp}, we present a branch-and-cut algorithm and a novel class of local cutting planes tailored for balanced combinatorial optimization problems. We demonstrate the effectiveness of the proposed framework in the Balanced Traveling Salesman Problem. Additionally, we introduce bounding algorithms and mechanisms to fix variables to accelerate performance further.The second approach to handling the issue of fairness is extit{Ordered Weighted Average (OWA) combinatorial optimization}, which integrates the OWA operator into the objective function. Due to the ordering operator, OWA combinatorial optimization is nonlinear, even if its original constraints are linear. Two MILP formulations of different sizes have been introduced in the literature to linearize the OWA operator. However, which formulation performs best for OWA combinatorial optimization remains uncertain, as integrating the linearization methods may introduce additional difficulties. In Chapteref{chap:owa}, we provide theoretical and empirical comparisons of the two MILP formulations for OWA combinatorial optimization. In particular, we prove that the formulations are equivalent in terms of the linear programming relaxation. We empirically show that for OWA combinatorial optimization problems, the formulation with more variables can be solved faster with branch-and-cut.In Partef{part:2} (Chapteref{chap:mlbnc}), we develop methods for applying machine learning to enhance fundamental decision problems in branch-and-cut, with a focus on cut generation. Cut generation refers to the decision of whether to generate cuts or to branch at each node of the search tree. We empirically demonstrate that this decision significantly impacts branch-and-cut performance, especially for combinatorial cuts that exploit the facial structure of the convex hull of feasible solutions. We then propose a general framework combining supervised and reinforcement learning to learn effective strategies for generating combinatorial cuts in branch-and-cut. Our framework has two components: a cut detector to predict cut existence and a cut evaluator to choose between generating cuts and branching. Finally, we provide experimental results showing that the proposed method outperforms commonly used strategies for cut generation, even on instances larger than those used for training
2
Gliesch, Alex Zoch. "A genetic algorithm for fair land allocation." reponame:Biblioteca Digital de Teses e Dissertações da UFRGS, 2018. http://hdl.handle.net/10183/174950.
Full textAbstract:
O objetivo de projetos de reforma agrária é redistribuir terras de grandes latifúndios para terrenos menores, com destino à agricultura familiar. Um dos principais problemas do Instituto Nacional de Colonização e Reforma Agrária (INCRA) é subdividir uma parcela grande de terra em lotes menores que são balanceados com relação a certos atributos. Este problema é difícil por que precisa considerar diversas restrições legais e éticas. As soluções atuais são auxiliadas por computador, mas manuais, demoradas e suscetíveis a erros, tipicamente produzindo lotes retangulares de áreas similares mas que são injustos com relação a critérios como aptidão do solo ou acesso a recursos hidrográficos. Nesta dissertação, nós propomos um algoritmo genético para gerar subdivisões justas de forma automática. Nós apresentamos um algoritmo construtivo guloso randomizado baseado em locação-alocação para gerar soluções iniciais, assim como operadores de mutação e recombinação que consideram especificidades do problema. Experimentos com 5 instâncias reais e 25 instâncias geradas artificialmente confirmam a efetividade dos diferentes componentes do método proposto, e mostram que ele gera soluções mais balanceadas que as atualmente usadas na prática.The goal of agrarian reform projects is the redistribution of farmland from large latifundia to smaller, often family farmers. One of the main problems the Brazilian National Institute of Colonization and Agrarian Reform (INCRA) has to solve is to subdivide a large parcel of land into smaller lots that are balanced with respect to certain attributes. This problem is difficult since it considers several constraints originating from legislation as well as ethical considerations. Current solutions are computer-assisted, but manual, time-consuming and error-prone, leading to rectangular lots of similar areas which are unfair with respect to soil aptitude and access to hydric resources. In this thesis, we propose a genetic algorithm to produce fair land subdivisions automatically. We present a greedy randomized constructive heuristic based on location-allocation to generate initial solutions, as well as mutation and recombination operators that consider specifics of the problem. Experiments on 5 real-world and 25 artificial instances confirm the effectiveness of the different components of our method, and show that it leads to fairer solutions than those currently applied in practice.
Book chapters on the topic "Fair combinatorial optimization"
1
Armaselu, Bogdan, and Ovidiu Daescu. "Algorithms for Fair Partitioning of Convex Polygons." In Combinatorial Optimization and Applications, 53–65. Cham: Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-12691-3_5.
Full text
2
Jia, Xinrui, Kshiteej Sheth, and Ola Svensson. "Fair Colorful k-Center Clustering." In Integer Programming and Combinatorial Optimization, 209–22. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-45771-6_17.
Full text
3
Nguyen, Viet Hung, and Paul Weng. "An Efficient Primal-Dual Algorithm for Fair Combinatorial Optimization Problems." In Combinatorial Optimization and Applications, 324–39. Cham: Springer International Publishing, 2017. http://dx.doi.org/10.1007/978-3-319-71150-8_28.
Full text
4
Hansen, Thomas Dueholm, and Orestis A. Telelis. "Improved Bounds for Facility Location Games with Fair Cost Allocation." In Combinatorial Optimization and Applications, 174–85. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-02026-1_16.
Full text
5
Blum, Christian, and Pedro Pinacho-Davidson. "Application of Negative Learning Ant Colony Optimization to the Far from Most String Problem." In Evolutionary Computation in Combinatorial Optimization, 82–97. Cham: Springer Nature Switzerland, 2023. http://dx.doi.org/10.1007/978-3-031-30035-6_6.
Full text
6
Blum, Christian, and Paola Festa. "A Hybrid Ant Colony Optimization Algorithm for the Far From Most String Problem." In Evolutionary Computation in Combinatorial Optimisation, 1–12. Berlin, Heidelberg: Springer Berlin Heidelberg, 2014. http://dx.doi.org/10.1007/978-3-662-44320-0_1.
Full text
7
"Combinatorial Materials and Catalysts Development: Where Are We and How Far Can We Go?" In Combinatorial and High-Throughput Discovery and Optimization of Catalysts and Materials, 23–36. CRC Press, 2006. http://dx.doi.org/10.1201/9781420005387-7.
Full text
8
Li, Chu Min, and Felip Manyà. "Chapter 23. MaxSAT, Hard and Soft Constraints." In Frontiers in Artificial Intelligence and Applications. IOS Press, 2021. http://dx.doi.org/10.3233/faia201007.
Full textAbstract:
MaxSAT solving is becoming a competitive generic approach for solving combinatorial optimization problems, partly due to the development of new solving techniques that have been recently incorporated into modern MaxSAT solvers, and to the challenge problems posed at the MaxSAT Evaluations. In this chapter we present the most relevant results on both approximate and exact MaxSAT solving, and survey in more detail the techniques that have proven to be useful in branch and bound MaxSAT and Weighted MaxSAT solvers. Among such techniques, we pay special attention to the definition of good quality lower bounds, powerful inference rules, clever variable selection heuristics and suitable data structures. Moreover, we discuss the advantages of dealing with hard and soft constraints in the Partial MaxSAT formalims, and present a summary of the MaxSAT Evaluations that have been organized so far as affiliated events of the International Conference on Theory and Applications of Satisfiability Testing.
9
Kaiwartya, Omprakash, Pawan Kumar Tiwari, Sushil Kumar, and Mukesh Prasad. "Dynamic Vehicle Routing Solution in the Framework of Nature-Inspired Algorithms." In Designing and Implementing Global Supply Chain Management, 36–50. IGI Global, 2016. http://dx.doi.org/10.4018/978-1-4666-9720-1.ch003.
Full textAbstract:
Vehicle Routing Problem (VRP), a well-known combinatorial optimization problem had been presented by Dantzing and Hamser in 1959. The problem has taken its inspiration from the transport field. In real field environment, a lot of variants of the problem exist that actually belongs to the class of NP-hard problem. Dynamic Vehicle routing problem (DVRP) is one of the variant of VRP that varies with respect to time. In DVRP, new customer orders appear over time and new route must be reconfigured at any instantaneous time. Although, some exact algorithms such as dynamic programming methods, branch and bound etc. can be applied to find the optimal route of a smaller size VRP. But, These Algorithms fail to give the solution of existed model of VRP in real field environment under given real time constraints. Courier services, dial a ride services and express mail delivery etc. are the few examples of real field environment problems that can be formulated in the form of DVRP. In this chapter, A novel variants of DVRP named as DVRP with geographic ranking (DVRP-GR) has been proposed. In DVRP-GR, geographical ranking, customer ranking, service time, expected reachability time, customer satisfaction level have been optimized. A solution of DVRP-GR using seed based particle swarm optimization (S-DVRS-PSO) has been also proposed. The simulations have been performed using customized simulator developed in C++ environment. The data sets used in the simulations are OMK-01, OMK-02 and OMK-03 generated in real vehicular environment. The solution of the proposed algorithm has been compared with the randomized solution technique. Analysis of the simulation results confirms the effectiveness of the proposed solution in terms of various parameters considered viz. number of vehicles, expected reachability time, profit and customer satisfaction.
Conference papers on the topic "Fair combinatorial optimization"
1
Golrezaei, Negin, Rad Niazadeh, Kumar Kshitij Patel, and Fransisca Susan. "Online Combinatorial Optimization with Group Fairness Constraints." In Thirty-Third International Joint Conference on Artificial Intelligence {IJCAI-24}. California: International Joint Conferences on Artificial Intelligence Organization, 2024. http://dx.doi.org/10.24963/ijcai.2024/44.
Full textAbstract:
As digital marketplaces and services continue to expand, it is crucial to maintain a safe and fair environment for all users. This requires implementing fairness constraints into the sequential decision-making processes of these platforms to ensure equal treatment. However, this can be challenging as these processes often need to solve NP-complete problems with exponentially large decision spaces at each time step. To overcome this, we propose a general framework incorporating robustness and fairness into NP-complete problems, such as optimizing product ranking and maximizing sub-modular functions. Our framework casts the problem as a max-min game between a primal player aiming to maximize the platform's objective and a dual player in charge of group fairness constraints. We show that one can trace the entire Pareto fairness curve by changing the thresholds on the fairness constraints. We provide theoretical guarantees for our method and empirically evaluate it, demonstrating its effectiveness.
2
Martin, Hugo, and Patrice Perny. "BiOWA for Preference Aggregation with Bipolar Scales: Application to Fair Optimization in Combinatorial Domains." In Twenty-Eighth International Joint Conference on Artificial Intelligence {IJCAI-19}. California: International Joint Conferences on Artificial Intelligence Organization, 2019. http://dx.doi.org/10.24963/ijcai.2019/252.
Full textAbstract:
We study the biOWA model for preference aggregation and multicriteria decision making from bipolar rating scales. A biOWA is an ordered doubly weighted averaging extending standard ordered weighted averaging (OWA) and allowing a finer control of the importance attached to positive and negative evaluations in the aggregation. After establishing some useful properties of biOWA to generate balanced Pareto-optimal solutions, we address fair biOWA-optimization problems in combinatorial domains. We first consider the use of biOWA in multi-winner elections for aggregating graded approval and disapproval judgements. Then we consider the use of biOWA for solving robust path problems with costs expressing gains and losses. A linearization of biOWA is proposed, allowing both problems to be solved by MIP. A path-ranking algorithm for biOWA optimization is also proposed. Numerical tests are provided to show the practical efficiency of our models.
3
Xu, Huanle, Yang Liu, Wing Cheong Lau, and Rui Li. "Combinatorial Multi-Armed Bandits with Concave Rewards and Fairness Constraints." In Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20}. California: International Joint Conferences on Artificial Intelligence Organization, 2020. http://dx.doi.org/10.24963/ijcai.2020/354.
Full textAbstract:
The problem of multi-armed bandit (MAB) with fairness constraint has emerged as an important research topic recently. For such problems, one common objective is to maximize the total rewards within a fixed round of pulls, while satisfying the fairness requirement of a minimum selection fraction for each individual arm in the long run. Previous works have made substantial advancements in designing efficient online selection solutions, however, they fail to achieve a sublinear regret bound when incorporating such fairness constraints. In this paper, we study a combinatorial MAB problem with concave objective and fairness constraints. In particular, we adopt a new approach that combines online convex optimization with bandit methods to design selection algorithms. Our algorithm is computationally efficient, and more importantly, manages to achieve a sublinear regret bound with probability guarantees. Finally, we evaluate the performance of our algorithm via extensive simulations and demonstrate that it outperforms the baselines substantially.
4
Comlek, Yigitcan, Liwei Wang, and Wei Chen. "Mixed-Variable Global Sensitivity Analysis With Applications to Data-Driven Combinatorial Materials Design." In ASME 2023 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. American Society of Mechanical Engineers, 2023. http://dx.doi.org/10.1115/detc2023-110756.
Full textAbstract:
Abstract Global Sensitivity Analysis (GSA) is the study of the influence of any given inputs on the outputs of a model. In the context of engineering design, GSA has been widely used to understand both individual and collective contributions of design variables on the design objectives. So far, global sensitivity studies have often been limited to design spaces with only quantitative (numerical) design variables. However, many engineering systems also contain, if not only, qualitative (categorical) design variables in addition to quantitative design variables. In this paper, we integrate the novel Latent Variable Gaussian Process (LVGP) with Sobol’ analysis to develop the first metamodel-based mixed-variable GSA method. Through two analytical case studies, we first validate and demonstrate the effectiveness of our proposed method for mixed-variable problems. Furthermore, while the new metamodel-based mixed-variable GSA method can benefit various engineering design applications, we employ our method with multi-objective Bayesian optimization (BO) to accelerate the Pareto front design exploration in many-level combinatorial design spaces. Specifically, we implement a sensitivity-aware design framework for metal-organic framework (MOF) materials that are constructed only from qualitative design variables and show the benefits of our method for expediting the exploration of novel MOF candidates from a many-level large combinatorial design space.
5
Dai, Zuo, and Jianzhong Cha. "A Hybrid Approach of Heuristic and Neural Network for Packing Problems." In ASME 1994 Design Technical Conferences collocated with the ASME 1994 International Computers in Engineering Conference and Exhibition and the ASME 1994 8th Annual Database Symposium. American Society of Mechanical Engineers, 1994. http://dx.doi.org/10.1115/detc1994-0119.
Full textAbstract:
Abstract Artificial Neural Networks, particularly the Hopfield-Tank network, have been effectively applied to the solution of a variety of tasks formulated as large scale combinatorial optimization problems, such as Travelling Salesman Problem and N Queens Problem [1]. The problem of optimally packing a set of geometries into a space with finite dimensions arises frequently in many applications and is far difficult than general NP-complete problems listed in [2]. Until now within accepted time limit, it can only be solved with heuristic methods for very simple cases (e.g. 2D layout). In this paper we propose a heuristic-based Hopfield neural network designed to solve the rectangular packing problems in two dimensions, which is still NP-complete [3]. By comparing the adequacy and efficiency of the results with that obtained by several other exact and heuristic approaches, it has been concluded that the proposed method has great potential in solving 2D packing problems.
6
Petkov, Hristo, Colin Hanley, and Feng Dong. "DAG-WGAN: Causal Structure Learning with Wasserstein Generative Adversarial Networks." In 11th International Conference on Embedded Systems and Applications (EMSA 2022). Academy and Industry Research Collaboration Center (AIRCC), 2022. http://dx.doi.org/10.5121/csit.2022.120611.
Full textAbstract:
The combinatorial search space presents a significant challenge to learning causality from data. Recently, the problem has been formulated into a continuous optimization framework with an acyclicity constraint, allowing for the exploration of deep generative models to better capture data sample distributions and support the discovery of Directed Acyclic Graphs (DAGs) that faithfully represent the underlying data distribution. However, so far no study has investigated the use of Wasserstein distance for causal structure learning via generative models. This paper proposes a new model named DAG-WGAN, which combines the Wasserstein-based adversarial loss, an auto-encoder architecture together with an acyclicity constraint. DAGWGAN simultaneously learns causal structures and improves its data generation capability by leveraging the strength from the Wasserstein distance metric. Compared with other models, it scales well and handles both continuous and discrete data. Our experiments have evaluated DAG-WGAN against the state-of-the-art and demonstrated its good performance.
7
Huang, Mingyu, and Ke Li. "Exploring Structural Similarity in Fitness Landscapes via Graph Data Mining: A Case Study on Number Partitioning Problems." In Thirty-Second International Joint Conference on Artificial Intelligence {IJCAI-23}. California: International Joint Conferences on Artificial Intelligence Organization, 2023. http://dx.doi.org/10.24963/ijcai.2023/621.
Full textAbstract:
One of the most common problem-solving heuristics is by analogy. For a given problem, a solver can be viewed as a strategic walk on its fitness landscape. Thus if a solver works for one problem instance, we expect it will also be effective for other instances whose fitness landscapes essentially share structural similarities with each other. However, due to the black-box nature of combinatorial optimization, it is far from trivial to infer such similarity in real-world scenarios. To bridge this gap, by using local optima network as a proxy of fitness landscapes, this paper proposed to leverage graph data mining techniques to conduct qualitative and quantitative analyses to explore the latent topological structural information embedded in those landscapes. In our experiments, we use the number partitioning problem as the case and our empirical results are inspiring to support the overall assumption of the existence of structural similarity between landscapes within neighboring dimensions. Besides, experiments on simulated annealing demonstrate that the performance of a meta-heuristic solver is similar on structurally similar landscapes.
8
Jiang, Chunheng, Jianxi Gao, and Malik Magdon-Ismail. "Inferring Degrees from Incomplete Networks and Nonlinear Dynamics." In Twenty-Ninth International Joint Conference on Artificial Intelligence and Seventeenth Pacific Rim International Conference on Artificial Intelligence {IJCAI-PRICAI-20}. California: International Joint Conferences on Artificial Intelligence Organization, 2020. http://dx.doi.org/10.24963/ijcai.2020/457.
Full textAbstract:
Inferring topological characteristics of complex networks from observed data is critical to understand the dynamical behavior of networked systems, ranging from the Internet and the World Wide Web to biological networks and social networks. Prior studies usually focus on the structure-based estimation to infer network sizes, degree distributions, average degrees, and more. Little effort attempted to estimate the specific degree of each vertex from a sampled induced graph, which prevents us from measuring the lethality of nodes in protein networks and influencers in social networks. The current approaches dramatically fail for a tiny sampled induced graph and require a specific sampling method and a large sample size. These approaches neglect information of the vertex state, representing the dynamical behavior of the networked system, such as the biomass of species or expression of a gene, which is useful for degree estimation. We fill this gap by developing a framework to infer individual vertex degrees using both information of the sampled topology and vertex state. We combine the mean-field theory with combinatorial optimization to learn vertex degrees. Experimental results on real networks with a variety of dynamics demonstrate that our framework can produce reliable degree estimates and dramatically improve existing link prediction methods by replacing the sampled degrees with our estimated degrees.
9
Liao, Yanfen, Jiejin Cai, and Xiaoqian Ma. "Study and Application on Real Time Optimum Operation for Plant Units." In ASME 2005 Power Conference. ASMEDC, 2005. http://dx.doi.org/10.1115/pwr2005-50311.
Full textAbstract:
The optimum unit commitment is to determine an optimal scheme which can minimize the system operating cost during a period while the load demand, operation constrains of the individual unit are simultaneously satisfied. Since it is characterized as a nonlinear, large scale, discrete, mixed-integer combinatorial optimization problem with constrains, it is always hard to find out the theoretical optimal solution. In this paper, a method combining the priority-order with dynamic comparison is brought out to obtain an engineering optimal solution, and is validated in a power plant composed of three 200MW and two 300MW units. Through simulating the on-line running datum from the DCS system in the power plant, the operating cost curves are obtained in different units, startup/shut-down mode and load demand. According to these curves, an optimum unit commitment model is established based on equal incremental rate principle principle. Make target function be minimum gross coal consumption, the results show that compared with the duty-chief-mode that allocates the load based on operators’ experience, the units’ mean gross coal consumption rate is reduced about 0.5g/(kW·h) when operating by this unit commitment model, and its economic profit is far more than the load economic allocation model that doesn’t considered the units’ start-up/shut-down.
10
Barros, E. G. D., S. P. Szklarz, J. Hopman, K. Hopstaken, J. P. Gonçalves da Silva, O. P. Bjørlykke, V. Rios, J. Videla, R. Oliveira, and R. G. Hanea. "Well Swapping and Conversion Optimization Under Uncertainty Based on Extended Well Priority Parametrization." In Offshore Technology Conference Brasil. OTC, 2023. http://dx.doi.org/10.4043/32960-ms.
Full textAbstract:
Abstract Offshore field development activities are commonly constrained by the capacity of production facilities available at the platform. It is a challenge for practitioners to find the best development and operational strategies to maximize field production in the presence of such constraints. Additional difficulties are raised when the often large geological uncertainties inherent to field development activities need to be accounted for throughout the search for the best strategy. In this work we present how computer-assisted optimization can help practitioners tackle these challenges. In this work, we focus on the particular problem of selecting the optimal subset(s) of wells to be subject to certain operational actions taking place throughout the field production life-cycle. We leverage robust and efficient field development optimization framework (EVEReST) based on stochastic gradients and its flexibility for customization to new types of decisions. We extend the mathematical parametrization based on a single set of well priorities, so far used to optimize time-static drilling order and well selection optimization. We apply it to multiple sets of well priorities which facilitate the formulation of the large combinatorial time-dynamic well subset selection optimization problem in terms of continuous control variables more suitable for gradient-based optimization techniques. The extended method is applied to two different real-life field case studies based on an offshore heavy oil field. In the first case, we use the well priorities to determine how to optimally select and swap the 14 producers (out of a total of 18) to be put on stream to satisfy constraints on the available variable speed drivers (VSDs) to provide power to the ESP pumps required to operate the producers. In the second case study, we tackle the problem of converting producers into polymer injectors for EOR purposes. Firstly, simulation scenarios indicate that such conversion has a positive impact on the overall project business case. However, deciding which 2 wells (out of a total of 5) to convert into polymer injectors, combined with when and how much polymer to inject while respecting the limits of available capacity of polymer injection facilities, leads to a complex optimization problem. In both case studies, optimization found improved and non-trivial strategies, resulting in significant increases in the economic objective function (+107 million USD and +318 million USD in terms of NPV) and providing new insights to asset engineers into the operations of the field. This showcases the strengths of the EVEReST framework to tackle real-life optimization problems accounting for complex constraints and uncertainties which are critical to deliver solutions of practical value to the asset teams.