Search

This paper studies the non-progressive spread of influence with threshold model in social networks. Consider a graph G with a threshold function t on its vertex set. Spread of influence is a discrete dynamic process as follows. For a given set of initially infected vertices at time step 0 each vertex v gets infected at time step i, i = 1, if and only if the number of infected neighbors are at least t (v) in time step i-1. Our goal is to find the minimum cardinality of initially infected vertices (perfect target set) such that eventually all of the vertices get infected at some time step l. In this paper an upper bound for the convergence time of the process is given for graphs with general thresholds. Then an integer linear programming for the size of minimum perfect target set is presented. Then we give a lower bound for the size of perfect target sets with strict majority threshold on graphs which all of the vertices have even degrees. It is shown that the later bound is asymptotically tight. [ABSTRACT FROM AUTHOR]

Designing a green supply chain is becoming popular in the context of sustainable development. To address this academic concern, this paper designs a multi-product, multi-echelon green supply chain network (GSCN) from economic and environmental aspects. During the modeling process, the main challenge is to access the accurate probability distributions of uncertain parameters from limited historical data. To overcome this difficulty, this paper develops a distributionally robust design framework for bi-objective GSCN, where the distribution information of uncertain parameter is partially available and characterized by ambiguity sets. For the tractability, this paper discusses robust counterpart reformulation under Wasserstein-distance-based ambiguity sets. Finally, the obtained mixed integer programming model is resolved via commercial optimization software. To validate the proposed optimization framework, we design a meat supply chain network for a Chinese realistic food enterprise. The computational results demonstrate that the proposed distributionally robust model can provide reliable solutions compared with stochastic optimization method. [ABSTRACT FROM AUTHOR]

In the context of Industry 4.0, industrial production equipment needs to communicate through the industrial internet to improve the intelligence of industrial production. This requires the current communication network to have the ability of large-scale equipment access, multiple communication protocols/heterogeneous systems interoperability, and end-to-end deterministic low-latency transmission. Time-sensitive network (TSN), as a new generation of deterministic Ethernet communication technology, is the main development direction of time-critical communication technology applied in industrial environments, and Wi-Fi technology has become the main way of wireless access for users due to its advantages of high portability and mobility. Therefore, accessing WiFi in the TSN is a major development direction of the current industrial internet. In this paper, we model the scheduling problem of TSN and WiFi converged networks and propose a scheme based on a greedy strategy distributed estimation algorithm (GE) to solve the scheduling problem. Compared with the integer linear programming (ILP) algorithm and the Tabu algorithm, the algorithm implemented in this paper outperforms the other algorithms in being able to adapt to a variety of different scenarios and in scheduling optimization efficiency, especially when the amount of traffic to be deployed is large. [ABSTRACT FROM AUTHOR]

This paper introduces a simultaneous optimization approach to synthesizing work and heat exchange networks (WHENs). The proposed work and heat integration (WHI) superstructure enables different thermodynamic paths of pressure and temperature-changing streams. The superstructure is connected to a heat exchanger network (HEN) superstructure, enabling the heat integration of hot and cold streams identified within the WHI superstructure. A two-step solution strategy is proposed, consisting of initialization and design steps. In the first step, a thermodynamic path model based on the WHI superstructure is combined with a model for simultaneous optimization and heat integration. This nonlinear programming (NLP) model aims to minimize operating expenditures and provide an initial solution for the second optimization step. In addition, hot and cold streams are identified, enabling additional model reduction. In the second step of the proposed solution approach, a thermodynamic path model is combined with the modified HEN model to minimize the network's total annualized cost (TAC). The proposed mixed integer nonlinear programming (MINLP) model is validated by several examples, exploring the impact of the equipment costing and annualization factor on the optimal network design. The results from these case studies clearly indicate that the new synthesis approach proposed in this paper produces solutions that are consistently similar to or better than the designs presented in the literature using other methodologies. [ABSTRACT FROM AUTHOR]

In the high-speed railway system, trains' original timetable is often disturbed by some emergencies including geological disasters and equipment failures, which brings great influence to passengers. This paper proposes a real-time high-speed train dispatching model in case of segment blockages, where a railway network is considered. The model includes the following two parts. First, if the trains are not cancelled or decelerated after a blockage occurs, the scope of the affected trains and stations is roughly estimated via the prediction of delay propagation model. Second, with the overall delay as the objective function, this paper constructs a mixed integer nonlinear programming (MINLP) model by considering the following three adjustment strategies: cancellation, delayed departure and deceleration, where the safe headway of the train operation is guaranteed by the moving blocking principle. Furthermore, to reduce the computation complexity, the solution of the model is only considered within the scope obtained in the first stage. The model is verified by using a small railway network with Nanjing as the hub station, which shows that the model is useful for reducing the effect of a disruption on original timetable, especially in comparison with the First Scheduled First Served (FSFS) rule used in practice. [ABSTRACT FROM AUTHOR]

The redundancy allocation problem is to find an optimal allocation of redundant components by considering the set of resources and cost constraints. In this research, the satellite attitude determination and control system is studied and its components is introduced, then the reliability of this system is modeled and optimized based on a mathematical approach based on the redundancy allocation. The model studied in this paper is about the structure of a series-parallel system that is in the exact mode of a satellite attitude determination and control system. In this paper, a new approach for modeling and optimization is presented. The mathematical model presented in this paper is into the class of mixed integer non-linear programming (MINLP). Solving these problems is very important for various researchers due to the high mathematical complexity. In this research, a heuristic method is used to the problem exact solution, the results of which have been reported. [ABSTRACT FROM AUTHOR]

Edge computing provides task offloading services to extend the computational capacity of mobile users and reduce task latency. Prior studies mainly focus on tasks with strict deadlines. However, in the real world, some tasks may not always have to be finished before hard deadlines, e.g., multimedia tasks. Tasks with soft deadlines can miss their primary deadlines, but not by too much, and still be timely. This has not been properly considered by existing offloading approaches. In this paper, we propose CONFECT, a novel offloading approach that handles tasks with mixtures of hard deadlines and soft deadlines. Specifically, we first formulate the problem as an integer linear programming and prove its hardness. Then, we propose two online algorithms with proven competitive ratios to solve the problem collectively, including an algorithm that assigns tasks to edge servers to maximize the task completion ratio and an algorithm that adjusts the task execution order to maximize the task completion revenue. Moreover, to balance the fairness among tasks and system revenue elastically, we extend CONFECT by using a tunable fairness knob. Finally, extensive experiments show that CONFECT outperforms five baseline algorithms in terms of task completion ratio and completion revenue. [ABSTRACT FROM AUTHOR]

Optimal planning and design of microgrids are priorities in the electrification of off-grid areas. Indeed, in one of the Sustainable Development Goals (SDG 7), the UN recommends universal access to electricity for all at the lowest cost. Several optimization methods with different strategies have been proposed in the literature as ways to achieve this goal. This paper proposes a microgrid installation and planning model based on a combination of several techniques. The programming language Python 3.10 was used in conjunction with machine learning techniques such as unsupervised learning based on K-means clustering and deterministic optimization methods based on mixed linear programming. These methods were complemented by the open-source spatial method for optimal electrification planning: onsset. Four levels of study were carried out. The first level consisted of simulating the model obtained with a cluster, which is considered based on the elbow and k-means clustering method as a case study. The second level involved sizing the microgrid with a capacity of 40 kW and optimizing all the resources available on site. The example of the different resources in the Togo case was considered. At the third level, the work consisted of proposing an optimal connection model for the microgrid based on voltage stability constraints and considering, above all, the capacity limit of the source substation. Finally, the fourth level involved a planning study of electrification strategies based mainly on microgrids according to the study scenario. The results of the first level of study enabled us to obtain an optimal location for the centroid of the cluster under consideration, according to the different load positions of this cluster. Then, the results of the second level of study were used to highlight the optimal resources obtained and proposed by the optimization model formulated based on the various technology costs, such as investment, maintenance, and operating costs, which were based on the technical limits of the various technologies. In these results, solar systems account for 80% of the maximum load considered, compared to 7.5% for wind systems and 12.5% for battery systems. Next, an optimal microgrid connection model was proposed based on the constraints of a voltage stability limit estimated to be 10% of the maximum voltage drop. The results obtained for the third level of study enabled us to present selective results for load nodes in relation to the source station node. Finally, the last results made it possible to plan electrification using different network technologies and systems in the short and long term. The case study of Togo was taken into account. The various results obtained from the different techniques provide the necessary leads for a feasibility study for optimal electrification of off-grid areas using microgrid systems. [ABSTRACT FROM AUTHOR]

This paper presents an approach to community detection in complex networks by simultaneously incorporating a connectivity-based metric and Max-Min Modularity. By leveraging the connectivity-based metric and employing a heuristic algorithm, we develop a novel complementary graph for the Max-Min Modularity that enhances its effectiveness. We formulate community detection as an integer programming problem of an equivalent yet more compact counterpart model of the revised Max-Min Modularity maximization problem. Using a row generation technique alongside the heuristic approach, we then provide a hybrid procedure for near-optimally solving the model and discovering high-quality communities. Through a series of experiments, we demonstrate the success of our algorithm, showcasing its efficiency in detecting communities, particularly in extensive networks. [ABSTRACT FROM AUTHOR]

This paper proposes two integer linear programming formulations to solve the optimal stratification problem (OSP). In this problem, once given the number of strata and the total sample size, the cutoff points and sample allocation should be determined jointly to minimize an expression of variance and to solve the OSP corresponding to an integer nonlinear optimization problem. One proposed formulation determines the optimal cutoff points considering classical allocation methods from the literature, and a second formulation produces the global optimum regarding the determination of the cutoff points and the sample allocation to the strata. Both formulations were implemented using Gurobi solver and applied to a set of 20 datasets from the literature, with population sizes ranging from 91 to 16,057, considering six different scenarios concerning the number of strata and sample sizes. The results obtained indicate that the formulations are a good alternative for the resolution of the OSP. [ABSTRACT FROM AUTHOR]

The integration of renewable energy is rapidly leading the existing grid systems toward modern hybrid power systems. These hybrid power systems are more complex due to the random and intermittent nature of RE and involve numerous operational challenges. This paper presents the operational model for solar integrated power systems to address the issues of economical operation, reliable solar share, energy deficit in case of contingency events, and the allocation of system spinning reserve. A mixed-integer optimization is formulated to minimize the overall cost of the system operation and to maximize the solar share under robust system spinning reserve limits as well as various other practical constraints. A Pareto-optimal solution for the maximization of the number of solar power plants and minimization of the solar cost is also presented for reliable solar share. Further, a decomposition framework is proposed to split the original problem into two sub-problems. The solution of joint optimization is obtained by exploiting a Lagrange relaxation method, a binary search Lambda iteration method, system spinning reserve analysis, and binary integer programming. The proposed model was implemented on an IEEE-RTS 26 units system and 40 solar plants. [ABSTRACT FROM AUTHOR]

The Double Row Layout Problem (DRLP) asks for an arrangement of machines on both sides of a straight line corridor so as to minimize the total cost for transferring materials among machines. The DRLP is NP-Hard and has practical relevance, specially in manufacturing systems design. In this paper, we drastically reduce the time required to solve the problem by constructing a new and effective mixed-integer linear programming (MILP) model of the DRLP. The new model was obtained by reformulating an existing MILP model. This includes tightening some constraints, introducing new variables, implementing constraints to link the new and original variables; and adding valid inequalities and a valid system of equations. To reduce the size of the reformulated model, we eliminate several of the new introduced variables by a substitution using the system of equations. The computational results demonstrate that the proposed model requires considerably smaller computational times compared to the ones in the literature. As a consequence, optimal solutions can now be efficiently found for larger instances of the problem. Previous studies have been able to optimally solve, within reasonable time, instances with size up to 16 machines, while with the new model four instances with 20 machines could be optimally solved. [ABSTRACT FROM AUTHOR]

Power system operators are faced with the problem of unit commitment belonging to mixed integer programming, which becomes very complicated, as units become large-scale and highly constrained. Because unit commitment problem is a binary problem with commitment and de-commitment, a discrete/binary optimization algorithm with superior performance is required. This paper proposes a novel hybrid binary bat algorithm for unit commitment problem, which consists of two process. To begin with, the proposed binary bat algorithm is applied to determining the commitment schedule of unit commitment problem. Specifically, an improved crossover operator based on exponential-logic-modulo map is proposed to enhance the convergence and maintain the diversity of populations. To prevent the algorithm from falling into a local optimum, a local mutation strategy performs local perturbation. Chaotic map is responsible for updating some parameters to increase the performance of the proposed algorithm. Furthermore, Lambda-iteration method is adopted to solve economic load dispatch in continuous space. Constraint handling is performed using the heuristic constraint produce. The effectiveness of the proposed algorithm is verified by benchmark functions and test systems. Additionally, the simulation results are compared with other well-established heuristic and binary approaches. [ABSTRACT FROM AUTHOR]

In this paper, we study the knapsack problem with conflict pair constraints. After a thorough literature survey on the topic, our study focuses on the special case of bipartite conflict graphs. For complete bipartite (multipartite) conflict graphs, the problem is shown to be NP-hard but solvable in pseudo-polynomial time, and it admits an FPTAS. Extensions of these results to more general classes of graphs are also presented. Further, a class of integer programming models for the general knapsack problem with conflict pair constraints is presented, which generalizes and unifies the existing formulations. The strength of the LP relaxations of these formulations is analyzed, and we discuss different ways to tighten them. Experimental comparisons of these models are also presented to assess their relative strengths. This analysis disclosed various strong and weak points of different formulations of the problem and their relationships to different types of problem data. This information can be used in designing special purpose algorithms for KPCC involving a learning component. [ABSTRACT FROM AUTHOR]

We consider the problem of designing lightweight, load-bearing planar frame structures for additive manufacturing, which can be formulated as a nonlinear, non-convex mathematical programming problems. Even using state-of-the-art commercial solvers, exact methods are only capable of solving small unrealistic instances (with very few variables). In this paper, we develop a heuristic method which is fast and capable of solving the design problem for larger-scale, weight-optimized, planar frame structures for additive manufacturing. The approach explicitly considers manufacturability constraints stemming from the use of additive manufacturing technology and leverages the problem structure imposed by these constraints. The proposed heuristic method is based on iteratively resolving a relaxed master problem on a reduced ground structure. The approach differs from the existing methods in two important aspects. First, we consider planar frame optimization master problem directly (instead of simpler but less relevant truss optimization). Secondly, we employ both element and node addition, which allows us to enforce additive manufacturability constraints without using binary variables (and hence, avoiding the need for computationally expensive integer programming). [ABSTRACT FROM AUTHOR]

The optimal PMU placement problem is placing the minimum number of PMUs in the network to ensure complete network observability. It is an NP-complete optimization problem. PMU placement based on cost and critical nodes is solved separately in the literature. This paper proposes a novel approach, a degree of centrality in the objective function, to combine the effect of both strategies to place PMUs in the power network optimally. The contingency analysis and the effect of zero-injection buses are solved to ensure the reliability of network monitoring and attain a minimum number of PMUs. Integer linear programming is used on the IEEE 7-bus, IEEE 14-bus, IEEE 30-bus, New England 39-bus, IEEE 57-bus, and IEEE 118-bus systems to solve this problem. The results are evaluated based on two performance measures: the bus observability index (BOI) and the sum of redundancy index (SORI). On comparison, it is found that the proposed methodology has significantly improved results, i.e., a reduced number of PMUs and increased network overall observability (SORI). This methodology is more practical for implementation as it focuses on critical nodes. Along with improvement in the results, the limitations of existing indices are also discussed for future work. [ABSTRACT FROM AUTHOR]

Delay-sensitive task offloading in a device-to-device assisted mobile edge computing (D2D-MEC) system with energy harvesting devices is a critical challenge due to the dynamic load level at edge nodes and the variability in harvested energy. In this paper, we propose a joint dynamic task offloading and CPU frequency control scheme for delay-sensitive tasks in a D2D-MEC system, taking into account the intricacies of multi-slot tasks, characterized by diverse processing speeds and data transmission rates. Our methodology involves meticulous modeling of task arrival and service processes using queuing systems, coupled with the strategic utilization of D2D communication to alleviate edge server load and prevent network congestion effectively. Central to our solution is the formulation of average task delay optimization as a challenging nonlinear integer programming problem, requiring intelligent decision making regarding task offloading for each generated task at active mobile devices and CPU frequency adjustments at discrete time slots. To navigate the intricate landscape of the extensive discrete action space, we design an efficient multi-agent DRL learning algorithm named MAOC, which is based on MAPPO, to minimize the average task delay by dynamically determining task-offloading decisions and CPU frequencies. MAOC operates within a centralized training with decentralized execution (CTDE) framework, empowering individual mobile devices to make decisions autonomously based on their unique system states. Experimental results demonstrate its swift convergence and operational efficiency, and it outperforms other baseline algorithms. [ABSTRACT FROM AUTHOR]

LU and Cholesky matrix factorization algorithms are core subroutines used to solve systems of linear equations (SLEs) encountered when solving an optimization problem. Standard floating-point algorithms are highly efficient but remain susceptible to the accumulation of round-off errors, which can lead solvers to return feasibility and optimality claims that are actually invalid. This paper introduces a novel direct solution approach for solving sequences of closely related SLEs encountered in nonlinear programming efficiently and without round-off errors. Specifically, it introduces rank-one update algorithms for the round-off error–free factorization framework, a tool set built on integer-preserving arithmetic that has led to the development and implementation of extremely reliable subroutines for solving SLEs occurring in linear programming. The formal guarantees of the presented algorithms are established through the derivation of theoretical insights. Their advantages are supported with computational experiments, which demonstrate upward of 75× improvements over exact factorization runtimes on fully dense matrices with more than one million entries. A significant advantage of the featured integer-preserving framework is that the length of any matrix coefficient produced by its algorithms is bounded polynomially in the size of the inputs without having to resort to greatest common divisor operations, which are required by and thereby hinder an efficient implementation of exact rational arithmetic approaches. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms–Continuous. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2021.0331) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2021.0331). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

In most project portfolio selection (PPS) situations, the presence of multiple attributes and decision-maker preference is inevitable. As Multi-criteria Decision Analysis (MCDA) methods provide a framework well-suited to deal with these challenges in PPS problems, the use of MCDA methods in real-life PPS problems has increased in recent years. This paper provides a comprehensive literature review of the use of different MCDA methods and their individual or combined utilization with other modeling techniques to support PPS problems. First, we summarize how MCDA methods are used in different modeling approaches. Second, we examine the mathematical models that are generally used to combine MCDA with mathematical programming techniques to solve PPS problems with resource constraints. Third, we present the drawbacks of combined utilization and discuss recent advances. Finally, we visualize the summary of the reviewed papers as a decision tree to assist researchers and practitioners in the use of MCDA methods in a specific PPS context and propose some future research directions. [ABSTRACT FROM AUTHOR]

It is a critical issue to allocate redundancy to critical smart grid infrastructure for disaster recovery planning. In this study, a framework to combine statistical prediction methods and optimization models for the optimal redundancy allocation problem is presented. First, statistical simulation methods to identify critical nodes of very large-scale smart grid infrastructure based on the topological features of embedding networks are developed, and then a linear integer programming model based on generalized assignment problem (GAP) for the redundancy allocation of critical nodes in smart grid infrastructure is presented. This paper aims to contribute to the field by employing a general redundancy allocation problem (GRAP) model from high-order nonlinear to linear model transformation. The model is specifically implemented in the context of smart grid infrastructure. The innovative linear integer programming model proposed in this paper capitalizes on the logarithmic multiplication property to reframe the inherently nonlinear resource allocation problem (RAP) into a linearly separable function. This reformulation markedly streamlines the problem, enhancing its suitability for efficient and effective solutions. The findings demonstrate that the combined approach of statistical simulation and optimization effectively addresses the size limitations inherent in a sole optimization approach. Notably, the optimal solutions for redundancy allocation in large grid systems highlight that the cost of redundancy is only a fraction of the economic losses incurred due to weather-related outages. [ABSTRACT FROM AUTHOR]

In refinery hydrogen networks, the optimal arrangement of hydrogen compressors is important to hydrogen reuse and cost reduction. The share of hydrogen compressors can not only reduce the number of compressors, but also provide the economy of scale. However, the previous studies only consider the whole share of compressors and mostly treat the compressor model as reciprocating compressors by default, which limits the optimization of hydrogen networks and does not correspond well with the practice. This paper presents a novel method for hydrogen network synthesis considering the hydrogen compressor type selection and the interstage suction/discharge of multi-stage compressors. In the developed superstructure, hydrogen sources are allowed to be suctioned and discharged via all possible stages of multi-stage compressors. Meanwhile, hydrogen sources can select centrifugal compressors or reciprocating compressors according to the working ranges. A mixed integer nonlinear programming model is developed to minimize the total annualized cost. The proposed method is suitable for both retrofit problems and new design problems, which is demonstrated by a refinery case and a literature case. For the refinery case, the zero-investment retrofit based on the existing compressors can reduce the fresh hydrogen demand by 1.73%, and the new hydrogen network design requires fewer compressors. In terms of the literature case, the hydrogen network design obtained in this paper can reduce the number of compressors by 5 or 3 through interstage suction/discharge of multi-stage compressors. • The interstage suction/discharge of compressors is considered in hydrogen network synthesis. • Different types of hydrogen compressors are incorporated in the superstructure. • The number of compressors is reduced by interstage suction/discharge. • The proposed approach is applicable to zero-investment retrofit problems and new design problems. [ABSTRACT FROM AUTHOR]

Exploring a dimensionality reduction model that can adeptly eliminate outliers and select the appropriate number of clusters is of profound theoretical and practical importance. Additionally, the interpretability of these models presents a persistent challenge. This paper proposes two innovative dimensionality reduction models based on integer programming (DRMBIP). These models assess compactness through the correlation of each indicator with its class center, while separation is evaluated by the correlation between different class centers. In contrast to DRMBIP-p, the DRMBIP-v considers the threshold parameter as a variable aiming to optimally balances both compactness and separation. This study, getting data from the Global Health Observatory (GHO), investigates 141 indicators that influence life expectancy. The findings reveal that DRMBIP-p effectively reduces the dimensionality of data, ensuring compactness. It also maintains compatibility with other models. Additionally, DRMBIP-v finds the optimal result, showing exceptional separation. Visualization of the results reveals that all classes have a high compactness. The DRMBIP-p requires the input of the correlation threshold parameter, which plays a pivotal role in the effectiveness of the final dimensionality reduction results. In the DRMBIP-v, modifying the threshold parameter to variable potentially emphasizes either separation or compactness. This necessitates an artificial adjustment to the overflow component within the objective function. The DRMBIP presented in this paper is adept at uncovering the primary geometric structures within high-dimensional indicators. Validated by life expectancy data, this paper demonstrates potential to assist data miners with the reduction of data dimensions. To our knowledge, this is the first time that integer programming has been used to build a dimensionality reduction model with indicator filtering. It not only has applications in life expectancy, but also has obvious advantages in data mining work that requires precise class centers. [ABSTRACT FROM AUTHOR]

When designing a patrol route, it is often necessary to pay more attention to locations with high crime rates. In this paper, we study a patrol routing problem for a fleet of patrol cars patrolling a region with a high-crime neighborhood (HCN) consisting of multiple hot spots. Considering the disorder and chaos in the HCN, at least one patrol car is required in the HCN at any given time during the patrol. We call this routing problem the hot spot coverage patrol problem (HSCPP). In the HSCPP, the importance of a patrol location is quantified by a prize, and the prize is collected if a patrol car visits the location. Our objective is to maximize the sum of prizes collected by the patrol cars, obeying all operational requirements. We propose mathematical formulations and develop several solution approaches for the HSCPP. The global approach consists of finding the routing solution for all patrol cars with a single integer programming (IP) formulation. The partition approach involves first partitioning the region geographically and solving the routing problem in each subregion with two IP formulations. Next, we strengthen the partition approach by developing a column generation (CG) approach in which the initial columns of the CG approach are the solutions generated from the partition approach. We conduct a detailed computational case study using instances based on real crime data from Montgomery County, Maryland. To further understand the computational tractability of our solution approaches, we also perform a sensitivity analysis using synthetic instances under various scenarios. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0192) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0192). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

In the multi-domain network scenario, in order to improve the survivability of service function chain (SFC) in the face of network failure, most methods solve this problem through virtual network function (VNF) backup mechanism. However, the traditional multi-domain SFC deployment method lacks a SFC partition mechanism for backup resource consumption and does not consider the isolation and privacy requirements between different network domains. In view of the above problems, this paper proposes a reliability partition scheme based on reinforcement learning in SFC partition stage, which can ensure that VNF is backed up while maintaining good load balancing and low inter-domain transmission delay, and improve the reliability of SFC. Then, this paper proposes a VNF backup mechanism with minimum resource fluctuation in the VNF mapping stage and uses the integer linear programming (ILP) model to determine the backup scheme of each VNF, so as to ensure the minimum fluctuation of resource occupancy of the entire network. Finally, this paper proposes a multi-domain SFC deployment and backup algorithm based on Federated learning (FA-MSDB). The experimental results indicate that FA-MSDB can effectively improve the survival rate of SFC, reduce the overall transmission delay, and ensure good inter-domain and intra-domain load balance. [ABSTRACT FROM AUTHOR]

The current arterial signal coordination models only target through traffic or critical traffic, resulting in fairness issues for traffic in other directions. Moreover, these models fail to achieve system optimality between intersections along the arterial. To address these problems, this paper establishes an arterial signal coordination optimization model based on all-direction pairs of adjacent intersections. The model takes the minimum weighted green wave band center offset of all-direction pairs at the intersections as the objective function. The optimization variables are the cycle length, offset, and phase sequence. The phase sequence structure adopts the ring-and-barrier structure, and the phase sequence optimization includes not only the main road but also the minor road intersecting with it. The model is an integer linear programming model, and it optimizes all-direction pairs of the upstream and downstream intersections. By analyzing the spatiotemporal diagram of the intersections, constraints are established for the phase sequence of the main road and intersecting roads. Through optimization of the offset and phase sequence, the coordination of flow direction pairs between upstream and downstream intersections can be optimized to improve the overall traffic fairness of the arterial. [ABSTRACT FROM AUTHOR]

Due to the high pollution of the transportation sector, nowadays the role of electric vehicles has been noticed more and more by governments, organizations, and environmentally friendly people. On the other hand, the problem of electric vehicle routing (EVRP) has been widely studied in recent years. This paper deals with an extended version of EVRP, in which electric vehicles (EVs) deliver goods to customers. The limited battery capacity of EVs causes their operational domains to be less than those of gasoline vehicles. For this purpose, several charging stations are considered in this study for EVs. In addition, depending on the operational domain, a full charge may not be needed, which reduces the operation time. Therefore, partial recharging is also taken into account in the present research. This problem is formulated as a multi-objective integer linear programming model, whose objective functions include economic, environmental, and social aspects. Then, the preemptive fuzzy goal programming method (PFGP) is exploited as an exact method to solve small-sized problems. Also, two hybrid meta-heuristic algorithms inspired by nature, including MOSA, MOGWO, MOPSO, and NSGAII_TLBO, are utilized to solve large-sized problems. The results obtained from solving the numerous test problems demonstrate that the hybrid meta-heuristic algorithm can provide efficient solutions in terms of quality and non-dominated solutions in all test problems. In addition, the performance of the algorithms was compared in terms of four indexes: time, MID, MOCV, and HV. Moreover, statistical analysis is performed to investigate whether there is a significant difference between the performance of the algorithms. The results indicate that the MOSA algorithm performs better in terms of the time index. On the other hand, the NSGA-II-TLBO algorithm outperforms in terms of the MID, MOCV, and HV indexes. [ABSTRACT FROM AUTHOR]

The containerized transportation mode has attracted more attention from many finished-vehicle (FV) logistics companies and ocean carriers which can provide door-to-door service and organize the multi-model transportation. This paper considers the FV loading problem for a carrier who uses containerized transportation mode. To increase the loading factor of containers and guarantee the safety of vehicles from damage, an adjustable bracket is introduced to place two-layer vehicles by tilting the upper pallet. A bi-objective programming problem is proposed in the sense of maximizing the safety margins of vehicles by setting the configuration of an adjustable bracket and the locations of the vehicles on the pallets. For any given combination of two vehicle types, we proved that the Pareto frontier of the bi-objective programming problem is a line and the Pareto optimal slope of the upper pallet can be determined by a maximization problem. With the Pareto frontier, the general FV loading problem with multiple vehicle types can be modeled as an integer programming problem and calculated by traditional programming algorithms. Areal loading task for the COSCO was adopted to depict our model and method. [ABSTRACT FROM AUTHOR]

Metric-based parameters aided the study of the structural properties of graph network space like complexity, central tendency, connectivity, robustness, accessibility, and vulnerability. At the same time, these parameters played a pivotal role in rectifying problems in navigation, integer programming, optimization, pattern recognition and avoidance, combinatoric detection, backtracking in geographical routing, etc. In this paper, we considered the fractional edge dimension, a metric-based parameter in local environment by initiating the study of the fractional local edge dimensions of a graph (FLED). We define the aforesaid concept and give its bounds. We discussed the characterization problem for FLED equal to 1 , the realization problem, and its relation with the fractional metric dimensions. We also calculated the FLED of the Petersen graph, Coxeter graph, the families of cycle, complete, wheel, grid and complete r -partite graphs. [ABSTRACT FROM AUTHOR]

This paper studies a framework of Reliable Capacitated Facility Location Problem with Single source constraint, which allows us to capture the mental account management problem for a bank under uncertain environment. In the problem, each facility, corresponding to a financial product, has limited capacity and may fail randomly, which represents that the product fails to reach the threshold level of return. Each customer, corresponding to a mental account, is served by a single primary facility or product, and its demands, or the setting goals, can be split on several backup facilities or alternative investments with redundant capacity. With the operation, a portion of the satisfaction can still be met by the backup facilities when the primary service of a customer fails. We formulate a mixed integer programming model for the problem and design a Lagrangian relaxation based solution algorithm, which sophisticatedly exploits the structure of the model and transfers the complicated relaxation problems into 0–1 knapsack problems to reduce the complexity. A local search procedure is also incorporated into the algorithm to enhance the accuracy of small- and large-scale computation. Finally, a real-life case of mental accounting is investigated to illustrate the application of the decision model. [ABSTRACT FROM AUTHOR]

This paper presents two novel formulations for scheduling problems, namely order-position hybrid formulation (OPH) and order-disjunctive hybrid formulation (ODH), which extend and combine parts of existing formulation strategies. The first strategy (OPH) is based on sequence position and linear ordering formulations, adding relationships between constraints that allow relaxing some decision variables. The second approach (ODH) is based on linear ordering and disjunctive formulations. In this work, we prove ODH to be the most efficient formulation known so far. The experiments have been carried out with a large set of problems, which consider single machines and identical parallel machines. Computational results show that OPH is better than the rest of the existing formulations for the case of weighted completion objectives, while ODH turns out to be the best approach for most scenarios studied. [ABSTRACT FROM AUTHOR]

In this paper, we analyze the copy complexity of unsatisfiable Horn constraint systems, under the ADD refutation system. Recall that a linear constraint of the form ∑ i = 1 n a i · x i ≥ b , is said to be a horn constraint if all the a i ∈ { 0 , 1 , - 1 } and at most one of the a i s is positive. A conjunction of such constraints is called a Horn constraint system (HCS). Horn constraints arise in a number of domains including, but not limited to, program verification, power systems, econometrics, and operations research. The ADD refutation system is both sound and complete. Additionally, it is the simplest and most natural refutation system for refuting the feasibility of a system of linear constraints. The copy complexity of an infeasible linear constraint system (not necessarily Horn) in a refutation system, is the minimum number of times each constraint needs to be replicated, in order to obtain a read-once refutation. We show that for an HCS with n variables and m constraints, the copy complexity is at most 2 n - 1 , in the ADD refutation system. Additionally, we analyze bounded-width HCSs from the perspective of copy complexity. Finally, we provide an empirical analysis of an integer programming formulation of the copy complexity problem in HCSs. (An extended abstract was published in FroCos 2021 [26].) [ABSTRACT FROM AUTHOR]

Generally, when optimizing a rolling stock schedule, the locations of the depots, or places in the network where the composition changes and maintenance occurs, are assumed known. The locations where maintenance is performed naturally influence the quality of any resulting rolling stock schedules. In this paper, the problem of selecting new depot locations and their corresponding capacities is considered. A two-stage mixed integer programming approach for rolling stock scheduling with maintenance requirements is extended to account for depot selection. First, a conventional flow-based model is solved, ignoring maintenance requirements, to obtain a variety of rolling stock schedules with multiple depot locations and capacity options. Then, a maintenance feasible rolling stock schedule can be obtained by solving a series of assignment problems by using the schedules found in the first stage. The proposed methodology is tested on real-life instances, and the numerical experiments of different operational scenarios are discussed. [ABSTRACT FROM AUTHOR]

One of the fundamental problems in randomly deployed sensor networks is enhancing the network lifetime while providing full area coverage. The problem is more challenging when location information is not available. Scheduling the activities of sensor nodes in a way that each point of the area of interest is covered by at least one sensor node is a promising way when a smaller set of sensor nodes is scheduled autonomously. The autonomous sleep scheduling of sensor nodes can be efficiently achieved based on the topological properties of the sensor network in a distributed fashion. In this paper, we address the problem of autonomously scheduling of sensor nodes to provide full area coverage in wireless sensor networks, even when location information is unavailable. The goal is to prolong the network lifetime. The proposed method is based on homology. The idea is autonomous selection of the minimum number of active sensors with the highest level of energy based on the properties of the simplicial complex of the network. We formulate this problem as an integer programming problem. Then, we propose a distributed algorithm, which does not require the knowledge of the location of nodes or distance between them. Finally, we provide simulation results demonstrating the performance of the proposed algorithm. [ABSTRACT FROM AUTHOR]

In the context of community detection, correlation clustering (CC) provides a measure of balance for social networks as well as a tool to explore their structures. However, CC does not encompass features such as the mediation between the clusters, which could be all the more relevant with the recent rise of ideological polarization. In this work, we study correlation clustering under mediation (CCM), a new variant of CC in which a set of mediators is determined. This new signed graph clustering problem is proved to be NP-hard and formulated as an integer programming formulation. An extensive investigation of the mediation set structure leads to the development of two efficient exact enumeration algorithms for CCM. The first one exhaustively enumerates the maximal sets of mediators in order to provide several relevant solutions. The second algorithm implements a pruning mechanism, which drastically reduces the size of the exploration tree in order to return a single optimal solution. Computational experiments are presented on two sets of instances: signed networks representing voting activity in the European Parliament and random signed graphs. History: Accepted by Van Hentenryck, Area Editor for Pascal. Funding: This work was supported by Fondation Mathématique Jacques Hadamard [Grant P-2019-0031]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0129) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0129). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

The Steinitz constant in dimension d is the smallest value c(d) such that for any norm on R d and for any finite zero-sum sequence in the unit ball, the sequence can be permuted such that the norm of each partial sum is bounded by c(d). Grinberg and Sevastyanov prove that c (d) ≤ d and that the bound of d is best possible for arbitrary norms; we refer to their result as the Steinitz Lemma. We present a variation of the Steinitz Lemma that permutes multiple sequences at one time. Our result, which we term a colorful Steinitz Lemma, demonstrates upper bounds that are independent of the number of sequences. Many results in the theory of integer programming are proved by permuting vectors of bounded norm; this includes proximity results, Graver basis algorithms, and dynamic programs. Due to a recent paper of Eisenbrand and Weismantel, there has been a surge of research on how the Steinitz Lemma can be used to improve integer programming results. As an application we prove a proximity result for block-structured integer programs. [ABSTRACT FROM AUTHOR]

With the continuous prosperity of maritime transportation on a global scale and the resulting escalation in port trade volume, tugboats assume a pivotal role as essential auxiliary tools influencing the ingress and egress of vessels into and out of ports. As a result, the optimization of port tug scheduling becomes of paramount importance, as it contributes to the heightened efficiency of ship movements, cost savings in port operations, and the promotion of sustainable development within the realm of maritime transportation. However, a majority of current tugboat scheduling models tend to focus solely on the maximum operational time. Alternatively, the formulated objective functions often deviate from real-world scenarios. Furthermore, prevailing scheduling methods exhibit shortcomings, including inadequate solution accuracy and incompatibility with integer programming. Consequently, this paper introduces a novel multi-objective tugboat scheduling model to align more effectively with practical considerations. We propose a novel optimization algorithm, the Improved Grey Wolf Optimization (IGWO), for solving the tugboat scheduling model. The algorithm enhances convergence performance by optimizing convergence parameters and individual updates, making it particularly suited for solving integer programming problems. The experimental session designs several scale instances according to the reality of the port, carries out simulation experiments comparing several groups of intelligent algorithms, verifies the effectiveness of IGWO, and verifies it in the comprehensive port area of Huanghua Port to get the optimal scheduling scheme of this port area, and finally gives management suggestions to reduce the cost of tugboat operation through sensitivity analysis. [ABSTRACT FROM AUTHOR]

Integrating preventive maintenance (PM) scheduling and production planning efficiently remains challenging for researchers and practitioners alike, owing to complex component interdependencies. Existing studies often lack practicality due to oversimplified assumptions. In this paper, we propose a two-stage solution for the integrated PM scheduling and production planning problem within multi-parallel component manufacturing systems, accounting for diverse interdependencies. These interdependencies encompass stochastic, structural, economic, and resource-related interdependencies, all while accounting for the resultant degradation. The primary objective is jointly optimizing costs associated with holding, backorders, production, setup, and maintenance. Initially, we employ an Ordinary Differential System to compute a realistic production capacity. Additionally, we analyze the effects of interdependence-induced degradation on system availability and failures. Subsequently, we formulate the problem as an integer programming model to determine an optimal joint plan. The effectiveness of our approach is validated through numerical examples and sensitivity analysis, providing insightful guidance for efficient PM scheduling and production planning, particularly in large-scale production systems. [ABSTRACT FROM AUTHOR]

The uncertain flow is a common factor that leads to risks in hub-and-spoke systems. Confronted with risks, it cannot be ignored that the decision maker has different risk-bearing capacities, which influence decision-making. This paper presents an α -risk appetite to characterize the risk-bearing capacity and employs the concept of belief degree to construct it. A multi-commodity capacitated p-hub median model is built with time windows, uncertain flows and the α -risk appetite objective function. In this model, the uncertain flows are depicted as uncertain variables, which possess an empirical uncertainty distribution even with little data. Uncertainty theory has the advantage in converting the proposed uncertain model into a deterministic equivalent form. While the deterministic model is still a mixed 0–1 integer programming problem and has challenges in theory and practice for addressing large-scale problems. Based on the difficulty, we design a hybrid genetic algorithm, where a new principle of cis-position assignment is proposed and inserted into this algorithm to accelerate the solving process. By comparing the proposed model with a deterministic benchmark model, the computational results demonstrate that taking the α -risk appetite and uncertainty into account could avoid the losses of neglecting risks. The observations of cost and hub location reflect the model's sensitivity about risk appetite levels. Finally, the effectiveness of the proposed algorithm is verified by two data sets, the Civil Aeronautics Board data and the Australian Post data. [ABSTRACT FROM AUTHOR]

The extensive consumption of energy in manufacturing has led to a large amount of greenhouse gas emissions that have caused an enormous effect on the environment. Therefore, investigating how to reduce energy consumption in manufacturing is of great significance to cleaner production. This paper considers an energy-conscious unrelated parallel batch processing machine scheduling problem under time-of-use (TOU) electricity prices. Under TOU, electricity prices vary for different periods of a day. This problem is grouping jobs into batches, assigning the batches to machines and allocating time to the batches so as to minimize the total electricity cost. A mixed-integer linear programming model and two groups of heuristics are proposed to solve this problem. The first group of heuristics first forms batches, assigns the batches to machines and finally allocates time to the batches, while the second group of heuristics first assigns jobs to machines, batches the jobs on each machine and finally allocates time to each batch. The computational results show that the SPT-FBLPT-P1 heuristic in the second group can provide high-quality solutions for large-scaled instances in a short time, in which the jobs are assigned to the machines based on the shortest processing time rule, the jobs on each machine are batched following the full-batch longest processing time algorithm, and the time is allocated to each batch following an integer programming approach. The MDEC-FBLPT-P1 heuristic that uses the minimum difference of the power consumption algorithm to assign the jobs also performed well. [ABSTRACT FROM AUTHOR]

Self-energy recycling cooperative communication, in which the relay nodes simultaneously harvest energy from the source and their own transmitted signal, has been demonstrated to significantly increase the total harvested energy. In this paper, we present an optimization framework for the resource allocation and relay selection with the objective of maximizing the sum-throughput in afull-duplex multi-relay multi-user multiple-input-multiple-output network by incorporating self-energy recycling at the relays, for the first time. The formulated problem is a mixed integer non-linear programming problem, which is difficult to solve for the global optimal solution in polynomial-time. As a solution strategy, we decompose the optimization problem into two sub-problems: resource allocation problem and relay selection problem. First, we solve the resource allocation problem for a predetermined relay selection by using Taylor series approximation and convex optimization techniques. For the relay selection problem, we propose a polynomial-time sub-optimal algorithm based on the idea of iteratively selecting the relay offering the maximum throughput at each time. Through simulations, we demonstrate that the proposed dynamic time FD-MIMO system increases the throughput by 30% as compared to the conventional static time protocol system, and by a factor of 2.4 over the system without self-energy recycling. [ABSTRACT FROM AUTHOR]

The operations performance of a railway station depends on the compatibility of its layout and the traffic pattern. It is necessary to determining an adaptable station layout for a railway station in accordance with its complex traffic pattern during the design phase. This paper assesses the railway station layout from a capacity perspective. In particular, this paper addresses an optimization-based capacity estimation approach for the layout variants of a railway station (i.e., the number of siding tracks and the structure of the connections in between) considering the traffic pattern variants. A mixed integer programming model for microscopic timetable compression is applied to calculate the occupation rate of the given traffic pattern with flexible route choices and train orders. A novel "schedule-and-fix" heuristic algorithm is proposed to solve large-scale instances efficiently. In the case study, we evaluate the performance of the schedule-and-fix method compared with the benchmark solvers Gurobi and CP-SAT. Applying the proposed method, we compare the capacity performances of the two station design schemes, i.e., one with a flyover and the other without. The result shows that, for the given instance, building a flyover gains capacity benefits as it reduces the potential conflict in the throat area. However, the level of benefit depends on the combination of trains. It is necessary to build the flyover when the proportion of turn-around trains is more than 70% from the perspective of station capacity. [ABSTRACT FROM AUTHOR]

Enhanced index tracking (EIT) problem is concerned with selecting a tracking portfolio to beat the benchmark on return while having the minimum tracking error. This paper addresses the EIT problem based on uncertainty theory where stock returns are treated as uncertain variables instead of random variables. Under the framework of uncertainty theory, the paper proposes a new uncertain EIT model where the higher-order moment of the downside is used as the tracking error measure, as higher-order moment makes the model more widely applicable and the downside risk is in line with investors' perception of risk. Besides, some realistic constraints are considered in the new uncertain EIT model. Then, the properties of the proposed model are discussed. To solve the model, we proposed, which is a nonlinear integer programming problem, a meta-heuristic algorithm presented. The efficiency of the algorithm and the applications of the proposed model are illustrated through numerical experiments. [ABSTRACT FROM AUTHOR]

Mobile edge computing (MEC) has emerged as a promising paradigm to improve the energy efficiency for latency-constraint computation. This paper proposes a novel user cooperation approach in both computation and communication for MEC, based on the three-node cooperative offloading architecture, which consists of two mobile users and a computing access point (CAP). The mobile application tasks can be executed locally or be offloaded to either a cooperative mobile user or CAP for remote execution. The cooperative task offloading problem is investigated to minimize the energy consumption of mobile users while satisfying the execution delay. The problem is formulated as a mixed integer programming, and the NP-hardness is provided by reducing it to a 0-1 knapsack problem. This paper also provides an optimal algorithm based on dynamic programming and an efficient heuristic approach. Numerical results show that the cooperative offloading scheme outperforms the local computing method by 66.4% on the energy consumption of mobile nodes. Furthermore, the proposed heuristic algorithm can achieve near-optimal performance under different network settings. [ABSTRACT FROM AUTHOR]

This paper proposes a smart system for managing the operations of grid-connected charging stations for electric vehicles (EV) that use photovoltaic (PV) sources. This system consists of a mobile application for EV drivers to make charging reservations, an algorithm to optimize the charging schedule, and a remote execution module of charging operations based on the open charge point protocol (OCPP). The optimal charging schedule was obtained by solving a binary integer programming problem. The merits of our solution are illustrated by simulating different charging demand scenarios. [ABSTRACT FROM AUTHOR]

Abstract: One of the desirable attributes of real-life examination timetabling solutions is the maximization of paper spread, which is a measure of the amount of study time that each student has between examinations. In this study, we face with a predefined examination schedule that must be modified in order to maximize paper spread in course of examination. We will show how the integer programming can be employed to achieve this aim. The model presents constraints for the quality of feasible examination timetables and all the requirements found in most academic institutions. The approach is tested on real-world exam timetabling problems. The computational experiments and results will be reported. [Copyright &y& Elsevier]