Article
Management
Pablo San Segundo, Fabio Furini, David Alvarez, Panos M. Pardalos
Summary: Given a graph, the maximum clique problem (MCP) asks for determining a complete subgraph with the largest possible number of vertices. We propose a new exact algorithm, called CliSAT , to solve the MCP to proven optimality. This problem is of fundamental importance in graph theory and combinatorial optimization due to its practical relevance for a wide range of applications.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2023)
Article
Management
Bo Jin, Shunji Tanaka
Summary: This study develops an efficient algorithm for solving a practical variant of the container relocation problem, and demonstrates its superior performance through computational experiments.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2023)
Article
Management
Shunji Tanaka, Stefan Voss
Summary: This study introduces a novel exact algorithm for the restricted block relocation problem and demonstrates its effectiveness through computational experiments.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2022)
Article
Mathematics, Applied
D. I. V. Y. A. Padmanabhan, Selin Damla Ahipasaoglu, A. R. J. U. N. Ramachandra, K. A. R. T. H. I. K. Natarajan
Summary: In this paper, the tightest possible bounds on the probability of the optimal value of a combinatorial optimization problem exceeding a given number are computed based on the marginal distributions of the objective. The complexity of computing the bounds is analyzed, and instances where the bounds can be computed in polynomial time are identified. The results complement existing results for computing the probability with independent random variables.
SIAM JOURNAL ON OPTIMIZATION
(2022)
Article
Computer Science, Information Systems
Burak Bartan, Mert Pilanci
Summary: We study distributed optimization methods for computationally challenging problems when forming the Hessian is difficult and communication is a bottleneck. We use randomized sketches to reduce the problem dimensions, preserve privacy, and improve straggler resilience in asynchronous distributed systems. We provide novel approximation guarantees and tight concentration results for sketching methods and extend the analysis to parameter averaging accuracy. We also develop unbiased parameter averaging methods for randomized second order optimization with sketched Hessian, and provide closed-form formulas to minimize bias for sketched Newton directions.
IEEE TRANSACTIONS ON INFORMATION THEORY
(2023)
Article
Management
Danilo Tedeschi, Marina Andretta
Summary: Planar Maximum Covering Location by Ellipses is an optimization problem where the goal is to choose the location of ellipses in order to cover demand points, maximizing a function based on the value of covered points. New exact algorithms were proposed for two versions of this problem - one with ellipses parallel to the coordinate axes and another with freely rotatable ellipses. These algorithms were able to find optimal solutions for previously published instances as well as new larger instances.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2021)
Article
Computer Science, Information Systems
Hanae Errousso, Jihane El Ouadi, El Arbi Abdellaoui Alaoui, Siham Benhadou
Summary: The imbalance of parking demand is a major cause of traffic congestion and pollution. We propose two models for parking space allocation, using mathematical methods and metaheuristic algorithms. Our solution significantly improves the satisfaction rate of parking demand, reduces walking distance, and demonstrates effectiveness in the eyes of urban stakeholders.
JOURNAL OF KING SAUD UNIVERSITY-COMPUTER AND INFORMATION SCIENCES
(2022)
Article
Management
Walid Ben-Ameur, Jose Neto
Summary: This article proposes new bounds for the subset selection problem, which aims to minimize the residual sum of squares while considering the constraint on the maximum number of non-zero variables. The study introduces new convex relaxations that provide both upper and lower bounds and compares them with existing methods in the literature. The performance of these methods is demonstrated through computational experiments.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2022)
Article
Computer Science, Artificial Intelligence
Yu Du, Gary Kochenberger, Fred Glover, Haibo Wang, Mark Lewis, Weihong Xie, Takeshi Tsuyuguchi
Summary: Finding good solutions to clique partitioning problems is computationally challenging. The choice of modeling structure has a significant impact on obtaining practical solutions from exact solvers. Commercial solvers like CPLEX, GUROBI, and XPRESS combined with the right model can greatly improve solution computation for modest-sized problems. This paper explores and compares the use of three commercial solvers on clique partitioning problems and finds that the quadratic model outperforms the classic linear model as problem size increases.
INTERNATIONAL JOURNAL OF INFORMATION TECHNOLOGY & DECISION MAKING
(2022)
Article
Management
Asyl L. Hawa, Rhyd Lewis, Jonathan M. Thompson
Summary: This paper investigates a packing problem related to the one-dimensional bin packing problem. It presents an exact polynomial-time algorithm for the Constrained Ordering Problem and introduces an evolutionary algorithm for the multi-bin version of the problem.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2022)
Article
Automation & Control Systems
Lintao Ye, Zhi-Wei Liu, Ming Chi, Vijay Gupta
Summary: We discussed the problem of maximizing a monotone nondecreasing set function under multiple constraints, and proposed two greedy algorithms with provable approximation guarantees. The first algorithm has better time complexity by exploiting the structure of a special class of problem instances. The second algorithm is suitable for general problems. We characterized the approximation guarantees of the two algorithms using the concepts of submodularity ratio and curvature, and discussed applications to specific problems in the literature. The theoretical results were validated using numerical examples.
Article
Computer Science, Information Systems
Rafael A. Melo, Celso C. Ribeiro, Jose A. Riveaux
Summary: This paper formally introduces the minimum quasi-clique partitioning problem and proposes four integer programming formulations and a heuristic algorithm to solve the problem. Computational experiments show that the formulations employing the principles of representatives outperform others. The results also indicate that instances with medium values of y are more challenging.
INFORMATION SCIENCES
(2022)
Article
Multidisciplinary Sciences
Daniel Lemire, Colin Bartlett, Owen Kaser
Summary: The paragraph discusses techniques for optimizing software by replacing integer division with more convenient calculations, such as transforming n divided by d into c*n (or c*n + c) divided by m, where c and m are chosen to approximate the reciprocal c/m to 1/d.
Article
Automation & Control Systems
Irina Subotic, Adrian Hauswirth, Florian Dorfler
Summary: Inspired by classical sensitivity results for nonlinear optimization, new quantitative bounds are derived to characterize the solution map and dual variables of a parametrized nonlinear program. The results are important for studying time-varying optimization problems in various applications, including power systems, robotics, signal processing, and more. Additionally, a new continuous-time running algorithm for time-varying constrained optimization is introduced.
IEEE TRANSACTIONS ON AUTOMATIC CONTROL
(2022)
Article
Management
Fabio Furini, Ivana Ljubic, Pablo San Segundo, Yanlu Zhao
Summary: The Edge Interdiction Clique Problem aims to minimize the size of the maximum clique in a graph by removing a subset of at most k edges. A new ILP formulation and branch-and-cut algorithm have been proposed to address this problem, which has shown significant improvement over existing approaches through extensive testing.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2021)
Article
Management
Jintong Ren, Jin-Kao Hao, Feng Wu, Zhang-Hua Fu
Summary: The paper proposes an effective hybrid search algorithm based on the memetic framework to solve the problem of maximizing profits in the multiple traveling repairman problem. The algorithm integrates multiple features, including generating high-quality solutions, reducing complexity, and ensuring accurate evaluation. Experimental results show that the proposed algorithm outperforms other algorithms on most benchmark instances.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2023)
Article
Computer Science, Interdisciplinary Applications
Zhen Shang, Jin-Kao Hao, Songzheng Zhao, Yang Wang, Fei Ma
Summary: In this study, an effective multi-wave tabu search algorithm is proposed for solving the boolean quadratic programming problem with generalized upper bound constraints (BQP-GUB). The algorithm performs a sequence of search waves, alternating between the forward and reverse phases, with the transition between waves determined by a hybrid perturbation phase. Experimental results show that the proposed algorithm is able to improve lower bounds for 6 instances and achieve solutions matching the best results in the literature for most instances within competitive time.
COMPUTERS & OPERATIONS RESEARCH
(2023)
Article
Computer Science, Artificial Intelligence
Zequn Wei, Jin-Kao Hao
Summary: This paper presents an iterated hyperplane search approach for the budgeted maximum coverage problem. The algorithm searches on specific areas identified by cardinality-constrained hyperplanes. It combines three procedures - tabu search, hyperplane search, and perturbation - to ensure diversification of the search. The competitiveness of the algorithm is demonstrated on 30 benchmark instances.
EXPERT SYSTEMS WITH APPLICATIONS
(2023)
Article
Computer Science, Artificial Intelligence
Lixin Tang, Zuocheng Li, Jin-Kao Hao
Summary: This article investigates a symmetry-breaking approach based on the permutation group theory and proposes a memetic algorithm to solve the single-row facility layout problem (SRFLP). The algorithm uses a problem-specific crossover operator and a simulated annealing procedure to generate meaningful offspring solutions. Experimental results show that the algorithm performs well on benchmark and large-scale instances.
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION
(2023)
Article
Computer Science, Hardware & Architecture
Pengfei He, Jin-Kao Hao, Qinghua Wu
Summary: This study presents a hybrid genetic algorithm that addresses both the orienteering problem (OP) and prize-collecting traveling salesman problem (PCTSP). The algorithm combines an extended edge-assembly crossover operator to generate promising offspring solutions, and an effective local search to improve each offspring solution. Additionally, the algorithm is enhanced by diversification-oriented mutation and population-diversity management. Extensive experiments show that the method is competitively on par with the best existing methods in terms of solution quality and computational efficiency, with additional insights provided on the roles of the key components of the proposed method.
Article
Computer Science, Artificial Intelligence
Wen Sun, Jin-Kao Hao, Zihao Wu, Wenlong Li, Qinghua Wu
Summary: In a directed graph G = (V, E), a feedback vertex set is a subset C that, when removed, makes the graph G acyclic. The feedback vertex set problem aims to find the minimum cardinality subset C*. This problem has various applications but is known to be NP-hard, posing computational challenges. To tackle this problem, the article proposes an iterated dynamic thresholding search algorithm that combines local optimization, dynamic thresholding search, and perturbation. Computational experiments on 101 benchmark graphs show that the algorithm outperforms state-of-the-art algorithms, achieving record-breaking best solutions for 24 graphs, equally best results for 75 graphs, and worse best results for only two graphs. The article also examines the impact of key components on the algorithm's performance.
PEERJ COMPUTER SCIENCE
(2023)
Article
Computer Science, Interdisciplinary Applications
Olivier Goudet, Jin-Kao Hao
Summary: This paper presents a massively parallel evolutionary algorithm for the partial Latin square extension problem based on graph coloring. The algorithm utilizes a large population and modern GPUs to perform intensive exploitation of the search space. Experimental results show its high competitiveness compared to other methods.
COMPUTERS & OPERATIONS RESEARCH
(2023)
Article
Management
Qinghua Wu, Mu He, Jin-Kao Hao, Yongliang Lu
Summary: This paper studies a variant of the orienteering problem known as the clustered orienteering problem. In this problem, customers are grouped into clusters and a profit is associated with each cluster, collected only when all customers in the cluster are served. The proposed evolutionary algorithm, incorporating a backbone-based crossover operator and a destroy-and-repair mutation operator, outperforms existing algorithms on benchmark instances and sets new records on some instances. It also demonstrates scalability on large instances and has shown superiority over three state-of-the-art COP algorithms. The algorithm is also successfully applied to a dynamic version of the COP considering stochastic travel time.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Computer Science, Interdisciplinary Applications
Yangming Zhou, Jiaqi Li, Jin-Kao Hao, Fred Glover
Summary: This study proposes a reduce-solve-combine memetic search approach to solve the critical node detection problem in an undirected graph. The new approach outperforms state-of-the-art algorithms and discovers new upper bounds on the problem. The investigation of key algorithmic modules further reveals the importance of the proposed ideas and strategies.
INFORMS JOURNAL ON COMPUTING
(2023)
Proceedings Paper
Computer Science, Software Engineering
Jean Pinsolle, Olivier Goudet, Cyrille Enderli, Jin-Kao Hao
Summary: This paper addresses the problem of separating a sequence of signals received from different emitters at different time steps. It proposes a new memetic algorithm that uses a likelihood-based crossover to explore the space of possible partitions efficiently. The algorithm is evaluated on synthetic data generated with Markov processes and on electronic warfare datasets.
EVOLUTIONARY COMPUTATION IN COMBINATORIAL OPTIMIZATION, EVOCOP 2023
(2023)
Proceedings Paper
Computer Science, Software Engineering
Cyril Grelier, Olivier Goudet, Jin-Kao Hao
Summary: This study proposes a hyper-heuristic approach to online learning that combines Monte Carlo Tree Search with multiple local search operators selected dynamically. Different operator policies, including proportional bias, one-armed bandit, and neural network, are investigated. Experiments on well-known benchmarks of the Weighted Vertex Coloring Problem demonstrate the advantages and limitations of each dynamic selection strategy.
EVOLUTIONARY COMPUTATION IN COMBINATORIAL OPTIMIZATION, EVOCOP 2023
(2023)
Article
Computer Science, Interdisciplinary Applications
Xiangjing Lai, Jin-Kao Hao, Renbin Xiao, Fred Glover
Summary: This paper presents a perturbation-based thresholding search algorithm for packing N identical circles in a square and N identical spheres in a cube. The algorithm combines a two-phase search strategy, perturbation operators, and container adjustment to achieve high performance. Experimental results show significant improvements compared with state-of-the-art results for both circle and sphere packing problems.
INFORMS JOURNAL ON COMPUTING
(2023)
Article
Computer Science, Hardware & Architecture
Pengfei He, Jin-Kao Hao, Qinghua Wu
Summary: This paper presents an effective and scalable hybrid genetic algorithm for solving the Hamiltonian p-median problem. The algorithm uses edge-assembly crossover and multiple neighborhood local search to generate and improve solutions. Experimental results show the superior performance of the method on different benchmark instances and evaluate its scalability. The study also analyzes the contributions of key components of the algorithm.
Article
Computer Science, Artificial Intelligence
Xiangjing Lai, Jin-Kao Hao, Renbin Xiao, Zhang-Hua Fu
Summary: This paper focuses on the global optimization problem of finding the minimum-energy configuration of particles on a unit sphere. The authors propose a population-based optimization algorithm that combines several strategies to solve this problem. Computational results show that the proposed algorithm is competitive and improves upon the best-known results in the literature.
EXPERT SYSTEMS WITH APPLICATIONS
(2024)
Article
Management
Mingjie Li, Jin-Kao Hao, Qinghua Wu
Summary: This study investigates the significance of cross-dock door assignment problem in supply chain management. It compares a flow-based formulation and a reinforcement learning-based heuristic approach, finding that the flow-based formulation is smaller and superior to the existing mixed integer programming formulations, while the heuristic approach is highly competitive in solution quality and computation time.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Review
Management
Vinicius N. Motta, Miguel F. Anjos, Michel Gendreau
Summary: This survey presents a review of optimization approaches for the integration of demand response in power systems planning and highlights important future research directions.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Philipp Schulze, Armin Scholl, Rico Walter
Summary: This paper proposes an improved branch-and-bound algorithm, R-SALSA, for solving the simple assembly line balancing problem, which performs well in balancing workloads and providing initial solutions.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Roshan Mahes, Michel Mandjes, Marko Boon, Peter Taylor
Summary: This paper discusses appointment scheduling and presents a phase-type-based approach to handle variations in service times. Numerical experiments with dynamic scheduling demonstrate the benefits of rescheduling.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Oleg S. Pianykh, Sebastian Perez, Chengzhao Richard Zhang
Summary: Efficient scheduling is crucial for optimizing resource allocation and system performance. This study focuses on critical utilization and efficient scheduling in discrete scheduling systems, and compares the results with classical queueing theory.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Review
Management
Hamed Jahani, Babak Abbasi, Jiuh-Biing Sheu, Walid Klibi
Summary: Supply chain network design is a large and growing area of research. This study comprehensively surveys and analyzes articles published from 2008 to 2021 to detect and report financial perspectives in SCND models. The study also identifies research gaps and offers future research directions.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Patrick Healy, Nicolas Jozefowiez, Pierre Laroche, Franc Marchetti, Sebastien Martin, Zsuzsanna Roka
Summary: The Connected Max-k-Cut Problem is an extension of the well-known Max-Cut Problem, where the objective is to partition a graph into k connected subgraphs by maximizing the cost of inter-partition edges. The researchers propose a new integer linear program and a branch-and-cut algorithm for this problem, and also use graph isomorphism to structure the instances and facilitate their resolution. Extensive computational experiments show that, if k > 2, their approach outperforms existing algorithms in terms of quality.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Victor J. Espana, Juan Aparicio, Xavier Barber, Miriam Esteve
Summary: This paper introduces a new methodology based on the machine learning technique MARS for estimating production functions that satisfy classical production theory axioms. The new approach overcomes the overfitting problem of DEA through generalized cross-validation and demonstrates better performance in reducing mean squared error and bias compared to DEA and C2NLS methods.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Stefano Nasini, Rabia Nessah
Summary: In this paper, the authors investigate the impact of time flexibility in job scheduling, showing that it can significantly affect operators' ability to solve the problem efficiently. They propose a new methodology based on convex quadratic programming approaches that allows for optimal solutions in large-scale instances.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Zhiqiang Liao, Sheng Dai, Timo Kuosmanen
Summary: Nonparametric regression subject to convexity or concavity constraints is gaining popularity in various fields. The conventional convex regression method often suffers from overfitting and outliers. This paper proposes the convex support vector regression method to address these issues and demonstrates its advantages in prediction accuracy and robustness through numerical experiments.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Kuo-Hao Chang, Ying-Zheng Wu, Wen-Ray Su, Lee-Yaw Lin
Summary: The damage and destruction caused by earthquakes necessitates the evacuation of affected populations. Simulation models, such as the Stochastic Pedestrian Cell Transmission Model (SPCTM), can be utilized to enhance disaster and evacuation management. The analysis of SPCTM provides insights for government officials to formulate effective evacuation strategies.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Qinghua Wu, Mu He, Jin-Kao Hao, Yongliang Lu
Summary: This paper studies a variant of the orienteering problem known as the clustered orienteering problem. In this problem, customers are grouped into clusters and a profit is associated with each cluster, collected only when all customers in the cluster are served. The proposed evolutionary algorithm, incorporating a backbone-based crossover operator and a destroy-and-repair mutation operator, outperforms existing algorithms on benchmark instances and sets new records on some instances. It also demonstrates scalability on large instances and has shown superiority over three state-of-the-art COP algorithms. The algorithm is also successfully applied to a dynamic version of the COP considering stochastic travel time.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Bjorn Bokelmann, Stefan Lessmann
Summary: Estimating treatment effects is an important task for data analysts, and uplift models provide support for efficient allocation of treatments. However, evaluating uplift models is challenging due to variance issues. This paper theoretically analyzes the variance of uplift evaluation metrics, proposes variance reduction methods based on statistical adjustment, and demonstrates their benefits on simulated and real-world data.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Congzheng Liu, Wenqi Zhu
Summary: This paper proposes a feature-based non-parametric approach to minimizing the conditional value-at-risk in the newsvendor problem. The method is able to handle both linear and nonlinear profits without prior knowledge of the demand distribution. Results from numerical and real-life experiments demonstrate the robustness and effectiveness of the approach.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Laszlo Csato
Summary: This paper compares the performance of the eigenvalue method and the row geometric mean as two weighting procedures. Through numerical experiments, it is found that the priorities derived from the two eigenvectors in the eigenvalue method do not always agree, while the row geometric mean serves as a compromise between them.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
Article
Management
Guowei Dou, Tsan-Ming Choi
Summary: This study investigates the impact of channel relationships between manufacturers on government policies and explores the effectiveness of positive incentives versus taxes in increasing social welfare. The findings suggest that competition may be more effective in improving sustainability and social welfare. Additionally, government incentives for green technology may not necessarily enhance sustainability.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2024)
