Article
Computer Science, Artificial Intelligence
Manolis N. Kritikos, George Ioannou
Summary: A new variant of the minimum spanning tree problem, referred to as the CMSTP_ATW, is studied with associated time windows and capacities, and a Mixed Integer Programming formulation is devised to model the problem. Experimental results show a strong negative correlation between the GAP of CPLEX and the total number of iterations, indicating potential for improvement. Additionally, a greedy heuristic algorithm is compared to the CPLEX built-in heuristic, showing high quality solutions in short computational times for large-scale test problems.
EXPERT SYSTEMS WITH APPLICATIONS
(2021)
Article
Computer Science, Software Engineering
Ilias Zadik, Miles Lubin, Juan Pablo Vielma
Summary: We investigate the structural geometric properties of mixed-integer convex representable (MICP-R) sets and compare them with the class of mixed-integer linear representable (MILP-R) sets. We provide examples of MICP-R sets that are countably infinite unions of convex sets with countably infinitely many different recession cones, and countably infinite unions of polytopes with different shapes. These examples highlight the differences between MICP-R sets and MILP-R sets.
MATHEMATICAL PROGRAMMING
(2023)
Article
Computer Science, Artificial Intelligence
Daniel Molina-Perez, Efren Mezura-Montes, Edgar Alfredo Portilla-Flores, Eduardo Vega-Alvarado, Barbara Calva-Yanez
Summary: This paper presents a new proposal based on two fundamental strategies to improve the performance of the differential evolution algorithm when solving MINLP problems. The proposal considers a set of good fitness-infeasible solutions to explore promising regions and introduces a composite trial vector generation method to enhance combinatorial exploration and convergence capacity.
SWARM AND EVOLUTIONARY COMPUTATION
(2024)
Article
Operations Research & Management Science
Hacene Ouzia, Nelson Maculan
Summary: This work introduces new mixed integer nonlinear optimization models for the Euclidean Steiner tree problem in high dimensions (d >= 3), featuring nonsmooth objective functions with convex continuous relaxations. Four convex mixed integer linear and nonlinear relaxations derived from these models are considered, each having the same feasible solutions as their respective original models. Preliminary computational results discussing the main features of these relaxations are presented.
JOURNAL OF GLOBAL OPTIMIZATION
(2022)
Article
Engineering, Industrial
Manolis N. Kritikos, George Ioannou
Summary: This paper introduces the non-unit demand capacitated minimum spanning tree problem with arc time windows and flow costs, presents a mixed integer programming formulation and valid inequalities to solve the problem, and conducts extensive computational experiments to demonstrate the positive effect of including valid inequalities in the MIP.
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH
(2023)
Article
Management
Fernando H. C. Dias, Hassan Hijazi, David Rey
Summary: This study introduces new mixed-integer programming formulations for aircraft conflict resolution with speed, heading, and altitude control based on disjunctive linear separation conditions. The proposed method significantly outperforms existing benchmarks in terms of runtime and the ability to solve more instances to global optimality.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2022)
Article
Computer Science, Interdisciplinary Applications
Alexander V. Smirnov
Summary: This paper mainly studies undirected multiple graphs of any natural multiplicity, including properties of multiple trees and complete spanning trees.
JOURNAL OF COMBINATORIAL OPTIMIZATION
(2022)
Article
Computer Science, Interdisciplinary Applications
Fabio Barbosa, Agostinho Agra, Amaro de Sousa
Summary: The paper focuses on upgrading networks to enhance robustness to multiple failures, utilizing a mixed integer linear programming model to minimize cost and maximize network robustness. A general iterative framework is proposed to compute Pareto solutions effectively on various network topologies.
COMPUTERS & OPERATIONS RESEARCH
(2021)
Article
Computer Science, Artificial Intelligence
Bahriye Akay, Dervis Karaboga, Beyza Gorkemli, Ebubekir Kaya
Summary: This paper reviews the use of Artificial Bee Colony algorithm for solving discrete numeric optimization problems, discussing various encoding types, search operators and selection operators integrated into ABC. It is the first comprehensive survey study on this topic and aims to benefit readers interested in utilizing ABC for binary, integer and mixed integer discrete optimization problems.
APPLIED SOFT COMPUTING
(2021)
Article
Multidisciplinary Sciences
Tomas Thorbjarnarson, Neil Yorke-Smith
Summary: Recent research has shown potential in optimizing certain aspects of neural networks (NNs) using Mixed Integer Programming (MIP) solvers. However, the approach of training NNs with MIP solvers has not been explored thoroughly. This article introduces new MIP models for training integer-valued neural networks (INNs) and provides two methods to improve the efficiency and data handling capabilities of MIP solvers. Experimental results demonstrate the superiority of our approach in terms of accuracy, training time, and data usage compared to previous state-of-the-art methods. Our methodology is particularly proficient at training NNs with minimal data and memory requirements, making it valuable for deployment on low-memory devices.
Article
Operations Research & Management Science
Saravanan Venkatachalam, Lewis Ntaimo
Summary: This paper develops the theory of integer set reduction for solving two-stage stochastic mixed-integer programs with general integer variables in the second-stage. The goal is to generate a valid inequality by using the smallest possible subset of the subproblem feasible integer set, similar to Fenchel decomposition cuts, in order to reduce computation time. An algorithm is devised to obtain such a subset based on the solution of the subproblem linear programming relaxation and incorporated into a decomposition method for SMIP. A computational study based on randomly generated knapsack test instances demonstrates the effectiveness of the new integer set reduction methodology in speeding up cut generation and obtaining better bounds compared to using a direct solver in solving SMIPs with pure integer recourse.
COMPUTATIONAL OPTIMIZATION AND APPLICATIONS
(2023)
Article
Management
Roberto Baldacci, Edna A. Hoshino, Alessandro Hill
Summary: This article focuses on novel solution methods for network optimization problems in the strategic planning of telecommunication infrastructure. The authors propose non-compact formulations, integrated cuts to strengthen polyhedral descriptions, and new relaxations for the pricing problem. Their algorithmic framework outperforms existing approaches in terms of solution time and quality, as shown in computational studies.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2023)
Article
Mathematics
Hui Gao, Daqing Yang
Summary: This paper generalizes the spanning tree packing theorem for undirected graphs by Nash-Williams and Tutte, while also extending the previous characterization on directed graphs by Cai and Frank.
JOURNAL OF GRAPH THEORY
(2021)
Article
Geography, Physical
Jemil Avers Butt, David Salido-Monzu, Andreas Wieser
Summary: Distance measurement based on the accumulated phase of intensity-modulated continuous-wave lasers is a precise method for pointwise geometry acquisition. However, the performance of these systems is limited by signal mixing caused by different delays. This study proposes an algorithm based on mixed integer linear programming to address the signal mixing and mixed pixel detection issues in multi-wavelength phase-based distance estimation. The results demonstrate the reliability of the proposed method and its ability to identify mixed pixel affected measurements.
ISPRS JOURNAL OF PHOTOGRAMMETRY AND REMOTE SENSING
(2023)
Article
Mechanics
G. Ntourmas, F. Glock, F. Daoud, G. Schuhmacher, D. Chronopoulos, E. Oezcan
Summary: This manuscript presents two novel formulations for manufacturable stacking sequence retrieval, achieving solutions that meet both design and manufacturing requirements through a two-stage optimization approach. Using mathematical programming algorithms, high-quality solutions can be consistently obtained, with increased design freedom concerning blending formulation.
COMPOSITE STRUCTURES
(2021)
Editorial Material
Computer Science, Hardware & Architecture
Bernard Fortz, Luis Gouveia, Christina Busing, Markus Leitner
Editorial Material
Management
Luis Gouveia, Sean McGarraghy, Cathal MacSwiney Brugha
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2021)
Article
Computer Science, Interdisciplinary Applications
Victor Bucarey, Bernard Fortz, Natividad Gonzalez-Blanco, Martine Labbe, Juan A. Mesa
Summary: The article discusses two covering variants of the network design problem: the Maximal Covering Network Design problem and the Partial Covering Network Design problem. A Benders decomposition approach is developed to solve these problems, with several stabilization methods considered for determining Benders cuts. Computational experiments demonstrate the efficiency of these different aspects.
COMPUTERS & OPERATIONS RESEARCH
(2022)
Article
Operations Research & Management Science
Jerome De Boeck, Luce Brotcorne, Bernard Fortz
Summary: This study presents a price-maker model for strategic bidding in Price Coupled Regions from the perspective of a producer, with a focus on optimal spot prices and the introduction of two novel heuristics for solving the problem efficiently. Experimental results highlight the importance of considering factors like Price Coupled Regions and an accurate Unit Commitment problem for the bidder's success, as well as the effectiveness of the proposed reformulation techniques and valid inequalities in solving larger instances.
MATHEMATICAL METHODS OF OPERATIONS RESEARCH
(2022)
Article
Computer Science, Hardware & Architecture
Bernard Fortz, Luis Gouveia, Pedro Moura
Summary: This article explores the relation between the linear programming relaxation of two classes of models for the Steiner tree problem with hop constraints, and finds that the linear programming relaxation of node-based models is implied by the linear programming relaxation of arc-based models.
Article
Economics
L. Brotcorne, P. Escalona, B. Fortz, M. Labbe
Summary: This study analyzes the scheduling of unpredictable fare inspections in proof-of-payment transit systems using a Stackelberg game approach. It introduces an exact formulation of inspection probabilities and develops new heuristics for the fare inspection scheduling problem.
TRANSPORTATION RESEARCH PART B-METHODOLOGICAL
(2021)
Article
Computer Science, Hardware & Architecture
Raquel Bernardino, Luis Gouveia, Ana Paias, Daniel Santos
Summary: This article focuses on the multi-depot family traveling salesman problem (MDFTSP) and its two clustered variants: the soft-clustered MDFTSP (SC-MDFTSP) and the hard-clustered MDFTSP. The study highlights the relevance of these problems to warehouse activities and points out the lack of discussion on clustered variants of routing problems in the literature. The article presents several mixed integer linear programming formulations and branch-and-cut based algorithms for solving these problems, which are tested on a newly generated dataset. The computational experiments reveal the main differences between the three problems in terms of modeling approaches and solution methods, and demonstrate the challenging nature of the SC-MDFTSP in particular.
Article
Operations Research & Management Science
Luis Gouveia, Markus Leitner, Mario Ruthmair
Summary: We have developed an exact algorithm for the multi-depot split-delivery vehicle routing problem (MDSDVRP), and proposed an integer programming formulation with effective inequalities. Experimental results demonstrate that the new inequalities strengthen the linear programming relaxation, improve algorithm performance, and reduce the number of feasibility cuts. The algorithm performs exceptionally well in MDSDVRP, significantly outperforms existing techniques in MDTSP, and remains competitive in SDVRP.
TRANSPORTATION SCIENCE
(2022)
Article
Management
Luis Gouveia, Ana Paias, Mafalda Ponte
Summary: This paper explores the Consistent Traveling Salesman Problem with positional consistency constraints (CTSP), which aims to find a set of routes with minimal cost while ensuring that all visited clients maintain positional consistency across routes. Various compact formulations and a new aggregated model derived from Time-dependent TSP (TDTSP) models are presented. Computational experiments reveal that the new aggregated model outperforms existing models in cases with consistent nodes appearing in all or most routes, while the original time-dependent model is more efficient when consistent nodes appear in fewer routes or less frequently.
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
(2023)
Article
Management
Pablo Escalona, Alejandro Angulo, Luce Brotcorne, Bernard Fortz, Paulina Tapia
Summary: This paper presents a new algorithm to address the optimal design of a distribution network for fast-moving consumer goods with high fill-rate service level. The algorithm considers both location and inventory decisions and provides good-quality solutions close to the optimal solution.
INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH
(2023)
Article
Computer Science, Hardware & Architecture
Hugo Callebaut, Jerome De Boeck, Bernard Fortz
Summary: In this article, a preprocessing technique is introduced to efficiently solve the Segment Routing Traffic Engineering Problem by utilizing fewer computational resources. The article focuses on the scalability issue of the exponential increase in segment paths when calculating optimal solutions. The notion of dominated segment paths is introduced to eliminate unnecessary paths, and a dynamic programming algorithm is proposed to handle any number of segments. Numerical results indicate the high dominance percentage of paths for different segment numbers in benchmark network topologies.
Article
Computer Science, Interdisciplinary Applications
Mariam Sangare, Eric Bourreau, Bernard Fortz, Amaury Pachurka, Michael Poss
Summary: This paper focuses on optimizing the collective self-consumption rate in energy communities by scheduling members' loads. The proposed strategy aims to implement a Demand Side Management program using controllable loads' characteristics. A MILP formulation is used to give optimal planning for electrical devices' operations and minimize energy flows from the public grid. Additionally, a column generation-based heuristic is developed for large problem instances. Numerical experiments show that joining an energy community saves money on energy bills and reduces energy drawn from the primary grid by at least 15%.
COMPUTERS & OPERATIONS RESEARCH
(2023)
Article
Computer Science, Information Systems
Arnaud Laurent, Luce Brotcorne, Bernard Fortz
Summary: This paper studies the transaction fee optimization problem in the Ethereum blockchain and proposes a solution based on the Monte Carlo method to predict the probability of a transaction being mined. Numerical results validate the effectiveness of the proposed method.
BLOCKCHAIN-RESEARCH AND APPLICATIONS
(2022)
Article
Mathematics, Applied
Yuehua Bu, Peng Wang, Hongguo Zhu, Junlei Zhu
Summary: This paper investigates the injective-edge coloring of a sparse graph G, and proves that when mad(G) meets certain conditions, the injective chromatic index x(i)'(G) has a upper bound.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Fawad Ali, Bilal A. Rather, Muhammad Naeem, Wei Wang
Summary: A topological descriptor is a numerical value derived from the molecular structure and is related to the important structural characteristics of the molecule. It is used to describe the composition of chemicals and their relationship with physical properties. This article explores various topological indices for power graphs of different finite groups.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Sergio Bermudo, Roslan Hasni, Fateme Movahedi, Juan E. Napoles
Summary: This article introduces a new graph index, the geometric-arithmetic index, and discusses the upper and lower bounds for this index in trees.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Ran Gu, Hui Lei, Yongtang Shi, Yiqiao Wang
Summary: This paper discusses the existence of rainbow-free coloring in random k-uniform hypergraphs, and provides the threshold function and the answer.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Fengwei Li, Qingfang Ye, Huajing Lu
Summary: This paper introduces the definition and application of the atom-bond sum-connectivity index (ABS index), and discusses its importance in studying molecular structures.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Milan Basic
Summary: This passage mainly describes the definition of integral circulant graph ICGn(D), the condition for adjacent vertices, and the characterization of minimal spread in the class of connected integral circulant graphs of a given order.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Andrey A. Dobrynin, Konstantin V. Vorob'ev
Summary: This study investigates the relationship between the Wiener index and R-m(G) of a graph G, and establishes the existence and properties of graphs G that satisfy specific conditions.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Devsi Bantva, Daphne Der-Fen Liu
Summary: This paper provides a lower bound for the radio number of the Cartesian product of two trees and presents three necessary and sufficient conditions as well as three sufficient conditions for achieving this bound. By applying these results, the radio number of the Cartesian product of two stars as well as a path and a star is determined.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Mikhail Fadin
Summary: This article discusses rational lattices, octahedral defects, and their relationship with monotonic increasing functions.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Jian Lu, Huiqing Liu, Xiaolan Hu
Summary: This paper investigates the problem of strong edge-coloring, and proves that when certain conditions are satisfied, the upper bound of the strong chromatic index is 29, thereby verifying Erdos' conjecture under certain circumstances.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Tom Denat, Ararat Harutyunyan, Nikolaos Melissinos, Vangelis Th. Paschos
Summary: This paper studies the average-case complexity of a branch-and-bound algorithm for the MIN DOMINATING SET problem in random graphs. We identify phase transitions between subexponential and exponential average-case complexities, depending on the growth of the probability p with respect to the number n of nodes.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Lkhagva Buyantogtokh, Batmend Horoldagva
Summary: This paper discusses the application of the exponential second Zagreb index in graphs and proves a conjecture regarding the maximum index. It also identifies the properties of graphs with maximum index under certain conditions.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Shenwei Huang, Yiao Ju, T. Karthick
Summary: This paper studies the coloring of (P5, kite)-free graphs with small clique number. It provides color number bounds for different constraints on cliques and proves them for specific conditions. The paper also gives examples to demonstrate the tightness of the bounds and makes a conjecture for the more general case.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Ryul Kim
Summary: This paper establishes relations between irreducible polynomials over a finite field Fq and its quadratic extension Fq2. The paper considers the relation between the numbers of irreducible polynomials of a fixed degree over Fq and Fq2, as well as the relations between self-reciprocal irreducible polynomials over Fq and self-conjugatereciprocal irreducible polynomials over Fq2. The paper also provides formulas for the number and the product of all self-conjugate-reciprocal irreducible monic (SCRIM) polynomials over Fq2.
DISCRETE APPLIED MATHEMATICS
(2024)
Article
Mathematics, Applied
Beata Benyi, Sithembele Nkonkobe
Summary: This paper introduces and lists weighted alpha-distanced words, showing their connection to the unified Apostol-type polynomials and providing combinatorial proofs of certain identities.
DISCRETE APPLIED MATHEMATICS
(2024)
