Search

The leafage of a chordal graph G is the minimum integer ℓ such that G can be realized as an intersection graph of subtrees of a tree with ℓ leaves. We consider structural parameterization by the leafage of classical domination and cut problems on chordal graphs. Fomin, Golovach, and Raymond [ESA 2018, Algorithmica 2020] proved, among other things, that Dominating Set on chordal graphs admits an algorithm running in time 2 O (ℓ 2) · n O (1) . We present a conceptually much simpler algorithm that runs in time 2 O (ℓ) · n O (1) . We extend our approach to obtain similar results for Connected Dominating Set and Steiner Tree. We then consider the two classical cut problems MultiCut with Undeletable Terminals and Multiway Cut with Undeletable Terminals. We prove that the former is W[1]-hard when parameterized by the leafage and complement this result by presenting a simple n O (ℓ) -time algorithm. To our surprise, we find that Multiway Cut with Undeletable Terminals on chordal graphs can be solved, in contrast, in n O (1) -time. [ABSTRACT FROM AUTHOR]

Partition problems in graphs are extremely important in applications, as shown in the Data Science and Machine Learning literature. One approach is spectral partitioning based on a Fiedler vector, i.e., an eigenvector corresponding to the second smallest eigenvalue a (G) of the Laplacian matrix L G of the graph G. This problem corresponds to the minimization of a quadratic form associated with L G , under certain constraints involving the ℓ 2 -norm. We introduce and investigate a similar problem, but using the ℓ 1 -norm to measure distances. This leads to a new parameter b (G) as the optimal value. We show that a well-known cut problem arises in this approach, namely the sparsest cut problem. We prove connectivity results and different bounds on this new parameter, relate to Fiedler theory and show explicit expressions for b (G) for trees. We also comment on an ℓ ∞ -norm version of the problem. [ABSTRACT FROM AUTHOR]

This paper studies a two-dimensional two-stage guillotine cutting stock problem which includes determination of how the items should be cut from stock panels in an optimal way, by developing and applying different solution approaches. An integer programming model with new features is proposed. A random key based genetic algorithm is utilized to obtain feasible solutions, and by applying a local search within the algorithm, a hybrid structure is acquired. Besides, a novel two-stage math-heuristic solution method is proposed. In the first stage of this method, a relaxation of the problem is solved; in the second, this solution is improved. The time to obtain the results of the developed two-stage math-heuristic solution approach is significantly lower than the other methods given in the article. Optimal solution values were obtained in 26 of 30 test problems taken from the literature with the proposed mathematical model, in 14 with mathematical programming based heuristic method, and in 16 with a random key based genetic algorithm. [ABSTRACT FROM AUTHOR]

Utilization of residue is a challenge in engineering practice, because unreasonable cutting causes excess materials wasted and increases the production cost. This work considers the residual two-dimensional cutting stock problem with usable leftover in which unused parts of cutting patterns can be used for future orders. We propose an algorithm that combines the iterative sequential value correction heuristic with the beam search heuristic, considering both the accumulation and the reusability of leftovers to reduce the material consumption. Cutting plans are constructed iteratively and the best one are chosen as the solution. Cutting patterns in the cutting plan are generated sequentially by recursive techniques, and potentially usable leftover are accumulated by beam search heuristic. Item values are corrected after each pattern to diversify cutting plans. Three sets of simulations under different number of periods, over medium and large instances from the literature, are used to demonstrate the effectiveness of the heuristics. Computational results show that the algorithm provides better solutions, which can save a considerable amount of plate in a long-term production period. The utilization of wastages can save a considerable amount of stock plate and contract the production cost of enterprises in the long-term production period. [ABSTRACT FROM AUTHOR]

We study the robust charging station location problem for a large-scale commercial taxi fleet. Vehicles within the fleet coordinate on charging operations but not on customer acquisition. We decide on a set of charging stations to open to ensure operational feasibility. To make this decision, we propose a novel solution method situated between the location routing problems with intraroute facilities and flow refueling location problems. Additionally, we introduce a problem variant that makes a station sizing decision. Using our exact approach, charging stations for a robust operation of citywide taxi fleets can be planned. We develop a deterministic core problem employing a cutting plane method for the strategic problem and a branch-and-price decomposition for the operational problem. We embed this problem into a robust solution framework based on adversarial sampling, which allows for planner-selectable risk tolerance. We solve instances derived from real-world data of the metropolitan area of Munich containing 1,000 vehicles and 60 potential charging station locations. Our investigation of the sensitivity of technological developments shows that increasing battery capacities shows a more favorable impact on vehicle feasibility of up to 10 percentage points compared with increasing charging speeds. Allowing for depot charging dominates both of these options. Finally, we show that allowing just 1% of operational infeasibility risk lowers infrastructure costs by 20%. Funding: This work was partially funded by the Deutsche Forschungsgemeinschaft [Project 277991500]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/trsc.2022.0207. [ABSTRACT FROM AUTHOR]

We consider the temporal bin packing problem with fire-ups (TBPP-FU), a branch of operations research recently introduced in multi-objective cloud computing. In this scenario, any item is equipped with a resource demand and a lifespan meaning that it requires the bin capacity only during that time interval. We then aim at finding a schedule minimizing a weighted sum of the total number of bins required and the number of switch-on processes (so-called fire-ups) caused during operation. So far, research on the TBPP-FU has mainly focused on exact approaches and their improvement by valid cuts or variable reduction techniques. Although these studies have revealed the problem considered here to be very difficult to cope with, theoretical contributions to heuristic solution methods have not yet been presented in the available literature. Hence, in this article we investigate the worst-case behavior of some approximation algorithms, ranging from classic online algorithms to a more sophisticated look-ahead heuristic specifically designed for the TBPP-FU. In addition, we theoretically study three heuristics the ideas of which are inspired by solution methods for generalized bin packing problems in the field of logistics. As a main contribution, we constructively show that the feasible solutions obtained by all these approaches can be arbitrarily bad. By doing so, we (i) identify a new open problem in cutting and packing, and (ii) establish another previously unknown difference between the classical TBPP and the extended problem with fire-ups, rendering the latter the more difficult problem even from a heuristic point of view. [ABSTRACT FROM AUTHOR]

We consider in this paper the budgeted minimum s - t cut problem. Suppose that we are given a directed graph G = (V , A) with two distinguished nodes s and t, k non-negative cost functions c 1 , ... , c k : A → Z + , and k - 1 budget bounds b 1 , ... , b k - 1 . The goal is to find a s - t cut C satisfying the budget constraints c h (C) ⩽ b h , for h = 1 , ... , k - 1 , and whose cost c k (C) is minimum. In this paper we discuss the linear relaxation of the problem and introduce a strict partial ordering on its solutions. We give a necessary and sufficient condition for which it has an integral optimal minimal (with respect to this ordering) basic solution. We also show that recognizing whether this is the case is NP-hard. [ABSTRACT FROM AUTHOR]

The big policy challenges of our times are complex problems cutting across policy sectors and levels of government. To answer the question how cross‐sectoral policy coordination in multilevel structures can be achieved, we argue in line with policy integration and multilevel governance scholarship that "loosely coupled" institutions create the interdependency necessary to secure complex coordination. This argument is substantiated empirically by investigating coordination of energy transition in the German Bundesrat. Expectations are derived on how loosely coupled institutions promote coordination. They are tested using a mix of empirical data. It can be shown that loosely coupled institutions indeed enable coordination by linking powers across multiple dimensions, creating incentives for cross‐sectoral communication, using personal ties in negotiations to bridge different institutional backgrounds, and sequencing the decision process to allow strategic shifts between coordination dimensions. Those mechanisms may not guarantee the best possible result, but they provide a satisfactory solution at least. [ABSTRACT FROM AUTHOR]

A theoretical model of ductile-brittle transition considering the cutter-rock friction was established, and the cutting force, mechanical specific energy (MSE), morphology of cutting chips and ductile-brittle failure transition mechanism of four different specially-shaped cutters were investigated through rock cutting tests. Furthermore, the 3D heterogeneous granite cutting numerical simulation models of 12 kinds of specially-shaped cutters and PDC bits were established by using the finite-discrete element method, and the problems such as the cutting force response, cutting chips formation, and MSE change rules were reproduced, as well as the influence of cutter shapes on drilling efficiency of PDC bits. The results indicate that there exists a critical cutting depth of ductile-brittle transition. Moreover, the critical cutting depth, MSE, footage and other parameters of 12 kinds of cutters were compared to provide a certain basis for the selection of drilling cutters, design optimization of drilling bits and the optimization of drilling parameters. [ABSTRACT FROM AUTHOR]

Cutting problems consist of cutting a set of objects available in stock in order to produce the desired items in specified quantities and sizes. The cutting process can generate leftovers (which can be reused in the case of new demand) or losses (which are discarded). This paper presents a tree-based heuristic method for minimizing the number of cut bars in the one-dimensional cutting process, satisfying the item demand in an unlimited bar quantity of just one type. The results of simulations are compared with the R G R L 1 algorithm and with the limiting values for this considered type of problem. The results show that the proposed heuristic reduces processing time and the number of bars needed in the cutting process, while it provides a larger leftover (by grouping losses) for the one-dimensional cutting stock problem. The heuristic contributes to reduction in raw materials or manufacturing costs in industrial processes. [ABSTRACT FROM AUTHOR]

This study stems from a furniture factory producing products by cutting and splicing operations. We formulate the problem into an assignment-based model, which reflects the problem accurately, but is intractable, due to a large number of binary variables and severe symmetry in the solution space. To overcome these drawbacks, we reformulate the problem into a clustering-assignment-based model (and its variation), which provides lower (upper) bounds of the assignment-based model. According to the classification of the board types, we categorize the instances into three cases: Narrow Board, Wide Board, and Mixed Board. We prove that the clustering-assignment-based model can obtain the optimal schedule for the original problem in the Narrow Board case. Based on the lower and upper bounds, we develop an iterative heuristic to solve instances in the other two cases. We use industrial data to evaluate the performance of the iterative heuristic. On average, our algorithm can generate high-quality solutions within a minute. Compared with the greedy rounding heuristic, our algorithm has obvious advantages in terms of computational efficiency and stability. From the perspective of the total costs and practical metrics, our method reduces costs by 20.90% and cutting waste by 4.97%, compared with a factory's method. [ABSTRACT FROM AUTHOR]

Monitoring cuttings concentration and ensuring that the wellbore is kept sufficiently clean during drilling is critical to safe drilling. Traditional analysis of cuttings concentration using mechanistic and empirical models has problems of adaptability and accuracy. To address the existing problems of cutting concentration prediction, this paper investigates the cutting concentration neural network model, and uses the established principal component analysis model to reduce the dimensionality of the parameters affecting the annular cutting concentration, and segments the well inclination according to 0-30°, 30-65° and 65+° to obtain the input parameters for cutting concentration prediction in different well inclination sections. By investigating the neural network prediction method, the mapping of nonlinear relationship between cutting concentration influencing factors and cutting concentration was realized, and the cutting concentration prediction fitting function was obtained. The model was tested using a full well section, well inclination segmented training and validation approach, and the predicted and measured cutting concentrations were compared and analyzed, and the results showed that The cuttings concentration prediction model established in this paper based on PCA and ANN for horizontal wells can achieve accurate prediction of annular cuttings concentration; the cuttings concentration prediction results of the neural network model are consistent with the influence of cuttings transport mechanism on cuttings concentration in different well inclination sections, which proves that the neural network model of cuttings concentration in separate well sections is highly adaptable and has the value of oil field application. [ABSTRACT FROM AUTHOR]

In order to solve a few problems of silage cutting device and baling device, the position-variable cutting device and rubber "herringbone" steel roll baling device are designed. Using the finite element devices to simulate the main components, and comparing the forces of the two tool materials, it is concluded that 60 Mn steel has better cutting effect compared with 45 steel; The radial deviation between the tool center axis and the theoretical axis is small to 1 mm, which satisfies the requirements, and the test analysis of 5 tools at the constant tool speed shows that the best uniformity appears when the amount of tools is 32, which reaches 91%. By analyzing the linear relationship between fragmentation uniformity and baling density, we conclude that fragmentation uniformity is linearly related to bale density. The motion analysis of the grain accumulation in the baling shows that the angle between the lower plane and the horizontal plane of the synchronous zone directly affects the degree of straw compaction. The improved position-variable cutting device can meet the crushing needs of a large range of different crops, and the floating steel roller design can increase the friction between the axial surface and the straw. Compared with traditional machines and tools, the whole improved device has certain advantages of cutting and baling. [ABSTRACT FROM AUTHOR]

In the multiway cut problem we are given a weighted undirected graph G = (V , E) and a set T ⊆ V of k terminals. The goal is to find a minimum weight set of edges E ′ ⊆ E with the property that by removing E ′ from G all the terminals become disconnected. In this paper we present a simple local search approximation algorithm for the multiway cut problem with approximation ratio 2 − 2 k . We present an experimental evaluation of the performance of our local search algorithm and show that it greatly outperforms the isolation heuristic of Dalhaus et al. and it has similar performance as the much more complex algorithms of Calinescu et al., Sharma and Vondrak, and Buchbinder et al. which have the currently best known approximation ratios for this problem. [ABSTRACT FROM AUTHOR]

While the maximum cut problem and its corresponding polytope has received a lot of attention inliterature, comparably little is known about the natural closely related variant maximum bond. Here, given a graph G = (V, E), we ask for a maximum cut δ(S) ⊆ E with S ⊆ V under the restriction that both G[S] as well as G[V \ S] are connected. Observe that both the maximum cut and the maximum bond can be seen as inverse problems to the traditional minimum cut, as there, the connectivity arises naturally in optimal solutions. The bond polytope is the convex hull of all incidence vectors of bonds. Similar to the connection of the corresponding optimization problems, the bond polytope is closely related to the cut polytope. While the latter has been intensively studied, there are no results on bond polytopes. We start a structural study of the latter, which additionally allows us to deduce algorithmic consequences. We investigate the relation between cut- and bond polytopes and the additional intricacies that arise when requiring connectivity in the solutions. We study the effect of graph modifications on bond polytopes and their facets, akin to what has been spearheaded for cut polytopes by Barahona, Grötschel and Mahjoub [4; 3] and Deza and Laurant [17; 15; 16]. Moreover, we study facet-defining inequalities arising from edges and cycles for bond polytopes. In particular, these yield a complete linear description of bond polytopes of cycles and 3-connected planar (K5 − e)-minor free graphs. Finally, we present a reduction of the maximum bond problem on arbitrary graphs to the maximum bond problem on 3-connected graphs. This yields a linear time algorithm for maximum bond on (K5 − e)-minor free graphs. [ABSTRACT FROM AUTHOR]

For Chinese cabbage cutting device in the harvesting process, the problem of cutting resistance and low cutting root qualification rate will occur. This paper takes the Chinese cabbage root as the research object, analyses the root-cutting mechanism of Chinese cabbage, and determines that the main factors affecting its cutting effect are the cutter's inclination angle, rotational speed and its working speed. The finite element method is adopted to establish a rigid-flexible coupling model between the cutting device and the cabbage root, and the Response Surface Method (RSM) central composite design method is used to investigate the relationship among the cutter inclination angle, the cutter rotational speed as well as the working speed and Maximum root-cutting reaction force (MRF) of the cabbage and to further obtain the optimal combination of parameters. Field test results show that in the optimal combination of parameters, which means cutter inclination angle of 11o, cutter rotating speed of 216 r/min and working speed of 0.28 m/s, the root cutting effect is perfect. At this time, the root-cutting qualification rate of 92.81% and field productivity of 0.12 hm2/h, meet the requirements of the standard of Chinese cabbage harvesting mechanization. The results of the study can provide reference for optimization of Chinese cabbage harvesting equipment design. [ABSTRACT FROM AUTHOR]

The skiving stock problem represents a natural counterpart of the extensively studied cutting stock problem and requires the construction of as many large units as possible from a given set of small items. In recent years, it has been able to develop into an independent branch of research within the OR community, exhibiting a wide variety of specific applications and associated integer programs, reaching its preliminary peak with the introduction of a powerful graph-theoretic approach, the reflect arc-flow model. However, there are still many benchmark instances that even the current formulations cannot yet contribute to solving. To this end, we present a new approach that is based on the observation that solutions of very good quality can already be determined on rather sparse (arc-flow) graphs, in general. More precisely, the arc sets of these graphs are defined by appropriate patterns obtained from a stabilized column-generation approach, so that considering the complete integer reflect arc-flow model is only necessary in a few cases. Compared to the reflect+ approach originally introduced for the cutting stock problem, we apply several modifications, discuss their numerical advantages by extensive computational tests, and end up with an adaptive solution method showing the most convincing results. In particular, we succeed in optimally solving some very challenging benchmark instances for the first time. [ABSTRACT FROM AUTHOR]

Fradkin and Seymour (J Comb Theory Ser B 110:19–46, 2015) defined the class of digraphs of bounded independence number as a generalization of the class of tournaments. They argued that the class of digraphs of bounded independence number is structured enough to be exploited algorithmically. In this paper, we further strengthen this belief by showing that several cut problems that admit sub-exponential time parameterized algorithms (a trait uncommon to parameterized algorithms) on tournaments, including Directed Feedback Arc Set, Directed Cutwidth and Optimal Linear Arrangement, also admit such algorithms on digraphs of bounded independence number. Towards this, we rely on the generic approach of Fomin and Pilipczuk (in: Proceedings of the Algorithms—ESA 2013—21st Annual European Symposium, Sophia Antipolis, France, September 2–4, 2013, pp. 505–516, 2013), where to get the desired algorithms, it is enough to bound the number of k-cuts in digraphs of bounded independence number by a sub-exponential FPT function (Fomin and Pilipczuk bounded the number of k-cuts in transitive tournaments). Specifically, our main technical contribution is a combinatorial result that proves that the yes-instances of the problems (defined above) have a sub-exponential number of k-cuts. We prove this bound by using a combination of chromatic coding, inductive reasoning and exploiting the structural properties of these digraphs. [ABSTRACT FROM AUTHOR]

We propose a hybrid quantum-classical algorithm to compute approximate solutions of binary combinatorial problems. We employ a shallow-depth quantum circuit to implement a unitary and Hermitian operator that block-encodes the weighted maximum cut or the Ising Hamiltonian. Measuring the expectation of this operator on a variational quantum state yields the variational energy of the quantum system. The system is enforced to evolve toward the ground state of the problem Hamiltonian by optimizing a set of angles using normalized gradient descent. Experimentally, our algorithm outperforms the state-of-the-art quantum approximate optimization algorithm on random fully connected graphs and challenges D-Wave quantum annealers by producing good approximate solutions. Source code and data files are publicly available (https://github.com/nkuetemeli/UQMaxCutAndIsing). [ABSTRACT FROM AUTHOR]

Modern applications of graph algorithms often involve the use of the output sets (usually, a subset of edges or vertices of the input graph) as inputs to other algorithms. Since the input graphs of interest are large and dynamic, it is desirable for an algorithm's output to not change drastically when a few random edges are removed from the input graph, so as to prevent issues in postprocessing. Alternately, having such a guarantee also means that one can revise the solution obtained by running the algorithm on the original graph in just a few places in order to obtain a solution for the new graph. We formalize this feature by introducing the notion of average sensitivity of graph algorithms, which is the average earth mover's distance between the output distributions of an algorithm on a graph and its subgraph obtained by removing an edge, where the average is over the edges removed and the distance between two outputs is the Hamming distance. In this work, we initiate a systematic study of average sensitivity of graph algorithms. After deriving basic properties of average sensitivity such as composition, we provide efficient approximation algorithms with low average sensitivities for concrete graph problems, including the minimum spanning forest problem, the global minimum cut problem, the minimum s-t cut problem, and the maximum matching problem. In addition, we prove that the average sensitivity of our global minimum cut algorithm is almost optimal, by showing a nearly matching lower bound. We also show that every algorithm for the 2-coloring problem has average sensitivity linear in the number of vertices. One of the main ideas involved in designing our algorithms with low average sensitivity is the following fact: if the presence of a vertex or an edge in the solution output by an algorithm can be decided locally, then the algorithm has a low average sensitivity, allowing us to reuse the analyses of known subline artime algorithms and local computation algorithms. Using this fact in conjunction with our average sensitivity lower bound for 2-coloring, we show that every local computation algorithm for 2-coloring has query complexity linear in the number of vertices, thereby answering an open question. [ABSTRACT FROM AUTHOR]

Regenerative chatter vibration is a typical machining problem during cutting. The frequency and phase shift of regenerative chatter can be used as indicators to suppress regenerative chatter. However, direct measurement of chatter vibration during cutting is difficult for end milling because the tool blade rotates. Therefore, chatter vibration is generally measured indirectly, for example, from cutting noise or vibration transmitted to the spindle. The type and position of the installed sensors must be appropriately selected to accurately measure chatter vibration with these methods. This selection must account for the machine tool structure, cutting conditions, and the position where the chatter vibration occurs, making the measurement methods not universally applicable. When chatter vibration occurs during cutting, a periodic pattern called a chatter mark is formed on the machined surface. The chatter mark is formed by vibration during cutting, i.e., vibration information during cutting is directly recorded. Therefore, this paper proposes a method to analyze the frequency and phase shift of chatter vibration using a two-dimensional discrete Fourier analysis of the chatter mark based on the modeled formation mechanism of chatter marks, and further validates the proposed method by elucidating the mechanism of chatter mark formed by chatter vibration. First, a cutting simulation was performed based on the vibration displacement of the tool during chatter cutting obtained experimentally. This simulation elucidates the mechanism by which the vibration information of chatter vibration can be analyzed from the chatter mark. Subsequently, the chatter vibration parameters were analyzed from the chatter mark using the proposed method. The parameters were consistent with those analyzed from the vibration displacement of the tool, confirming the effectiveness of the proposed method. • The formation mechanism of chatter marks was elucidated by simulation. • The waveform of chatter vibration during cutting cannot be analyzed from chatter mark. • A method was proposed to analyze the regenerative chatter vibration during cutting. • The proposed method enables direct analysis of regenerated chatter vibration. • The results of the proposed method and the conventional method are in good agreement. [ABSTRACT FROM AUTHOR]

The vertex cover problem is a famous combinatorial problem, and its complexity has been heavily studied. It is known that it is hard to approximate to within any constant factor better than 2, while a 2-approximation for it can be trivially obtained. In this paper, new properties and new techniques are introduced which lead to approximation ratios smaller than 2 on special graphs; e.g. graphs for which their maximum cut values are less than 0.999|E|. In fact, we produce a (1.9997)-approximation ratio on graph G, where the (0.878)- approximation algorithm of the Goemans-Williamson for the maximum cut problem on G produces a value smaller than 0.877122|E|. [ABSTRACT FROM AUTHOR]

We consider the problem of interdicting a directed graph by deleting nodes with the goal of minimizing the local edge connectivity of the remaining graph from a given source to a sink. We introduce and study a general downgrading variant of the interdiction problem where the capacity of an arc is a function of the subset of its endpoints that are downgraded, and the goal is to minimize the downgraded capacity of a minimum source-sink cut subject to a node downgrading budget. This models the case when both ends of an arc must be downgraded to remove it, for example. For this generalization, we provide a bicriteria (4, 2)-approximation that downgrades nodes with total weight at most 4 times the budget and provides a solution where the downgraded connectivity from the source to the sink is at most 2 times that in an optimal solution. We accomplish this with an LP relaxation and rounding using a ball-growing algorithm based on the LP values. Furthermore, we show that other bicriteria approximations exist where one can worsen the approximation factor for one of the costs in order to improve the other. We further generalize the downgrading problem to one where each vertex can be downgraded to one of k levels, and the arc capacities are functions of the pairs of levels to which its ends are downgraded. We generalize our LP rounding to get a (4k, 4k)-approximation for this case. Trade-offs between the two approximation ratios similar to the two-level case also exist for the generalized problem. By transferring node values to edge values, we also derive new bicriteria approximation results for the vertex interdiction versions of the multiway cut problem in digraphs and multicut problems in undirected graphs. [ABSTRACT FROM AUTHOR]

This paper considers an optimal movement routing problem with constraints. One such constraint is due to decomposing the original problem into a preliminary subproblem and a final subproblem; the tasks related to the preliminary problem must be executed before the tasks of the final subproblem begin. In particular, this condition may arise in the tool control problem for thermal cutting machines with computer numerical control (CNC): if there are long parts among workpieces, the cutting process near a narrow material boundary should start with these workpieces since such parts are subject to thermal deformations, which may potentially cause rejects. The problem statement under consideration involves two zones for part processing. The aggregate routing process in the original problem includes a starting point, a route (a permutation of indices), and a particular track consistent with the route and the starting point. Each of the subproblems has specific precedence conditions, and the travel cost functions forming the additive criterion may depend on the list of pending tasks. A special two-stage procedure is introduced to apply dynamic programming as a solution method. The structure of the optimal solution is established and an algorithm based on this structure is developed. The algorithm is implemented on a personal computer and a computational experiment is carried out. [ABSTRACT FROM AUTHOR]

This article presents a prediction model of the optimal dual variables for the cutting stock problem. For this purpose, we first analyze the influence of different attributes on the optimal dual variables within an instance for the cutting stock problem. We apply and compare our predictions in a stabilization technique for column generation. In most studies, the parameters for stabilized column generation are determined by numerical tests, that is, the same problem is solved several times with different settings. We develop two learning algorithms that predict the best algorithm configuration based on the predicted optimal dual variables and thus omit the numerical study. Our extensive computational study shows the tradeoff between the learning algorithms using full and sparse instance information. We show that both algorithms can efficiently predict the optimal dual variables and dominate the common update mechanism in a generic stabilized column generation approach. Although the learning algorithm with full instance information is applicable when one has to solve the problem mainly for a fixed set of items, the algorithm with sparse instance information is applicable when there is more variability in the number of items between the different instances. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2023.1277. [ABSTRACT FROM AUTHOR]

The carbonate Yijianfang formation and the Yingshan formation of the Ordovician system in the Shunbei oil and gas field is developed with microfractures and active gas zones. Serious and frequent CH4 and CO2 gas cut ascended fast in the annular spaces, leading to coexistence of mud losses and well blow-out. To prevent gas cut, previous experiences obtained in the Shunbei oil and gas field were borrowed and analyzed, and a high temperature weak gel drilling fluid was developed to deal with the gas cut problem. Several additives were used to formulate this drilling fluid, such as a high temperature stabilizer MG-HT, a high temperature rheology modifier JHVIS, a high temperature filter loss reducer JHFLO and a high temperature plugging agent JHSEAL, as well as other additives selected for this drilling fluid. This drilling fluid has high temperature resistance to 180 °C, good plugging capacity to gas cut and is able to improve the pressure bearing capacity of the formations. This drilling fluid can be weighted to 1.8 g/cm³ and has good rheology, filtration property and contamination resistance. The 6-RPM and 3-RPM readings of the drilling fluid measured on a 6-speed direct-reading rheometer are both greater than 5, and the low-shear-rate viscosity of the drilling fluid is greater than 15,000 mPa·s. Formations strengthened with this drilling fluid have forward and backward pressure bearing capacities of greater than 5 MPa and 1 MPa, respectively. This weak gel drilling fluid, with good gas cut preventing capacity, has provided a technical support to the safe, fast exploration and development of the fractured carbonate reservoirs in the Shunbei oil and gas field. [ABSTRACT FROM AUTHOR]

We present a parameterized dichotomy for the k - Sparsest Cut problem in weighted and unweighted versions. In particular, we show that the weighted k - Sparsest Cut problem is NP-hard for every k ≥ 3 even on graphs with bounded vertex cover number. Also, the unweighted k - Sparsest Cut problem is W[1]-hard when parameterized by the three combined parameters tree-depth, feedback vertex set number, and k. On the positive side, we show that the unweighted k - Sparsest Cut problem is FPT when parameterized by the vertex cover number and k , and when k is fixed, it is FPT with respect to the treewidth. Moreover, we show that the generalized version κ - Small-Set Expansion problem is FPT when parameterized by κ and the maximum degree of the graph, though it is W[1]-hard for each of these parameters separately. [ABSTRACT FROM AUTHOR]

Because of its high strength and poor thermal conductivity, TC11 alloy has some problems such as high cutting force and serious tool wear. To solve the problems, the finite element simulation and milling TC11 experiment are combined to research tool selection, cutting force, cutting vibration, and so on. First of all, the simulation and experiment of the cutting force are carried out, the prediction model is established, and the cutter parameters are optimized; Secondly, the milling experiment is carried out to compare and analyze the change rules of force and vibration when cutting with an optimized milling cutter and conventional cutter, and the best cutting parameters are selected; Finally, the tool life of milling TC11 under different cooling and lubrication conditions is explored. [ABSTRACT FROM AUTHOR]

It is well known that the one-dimensional cutting stock problem (1DCSP) is a combinatorial optimization problem with nondeterministic polynomial (NP-hard) characteristics. Heuristic and genetic algorithms are the two main algorithms used to solve the cutting stock problem (CSP), which has problems of small scale and low-efficiency solutions. To better improve the stability and versatility of the solution, a mathematical model is established, with the optimization objective of the minimum raw material consumption and the maximum remaining material length. Meanwhile, a novel algorithm based on deep reinforcement learning (DRL) is proposed in this paper. The algorithm consists of two modules, each designed for different functions. Firstly, the pointer network with encoder and decoder structure is used as the policy network to utilize the underlying mode shared by the 1DCSP. Secondly, the model-free reinforcement learning algorithm is used to train network parameters and optimize the cutting sequence. The experimental data show that the one-dimensional cutting stock algorithm model based on deep reinforcement learning (DRL-CSP) can obtain the approximate satisfactory solution on 82 instances of 3 data sets in a very short time, and shows good generalization performance and practical application potential. [ABSTRACT FROM AUTHOR]

This study aims to solve a one-dimensional multi-period cutting stock production replanning problem encountered in manufacturing industry cutting departments, considering pattern-setup costs. For operational purposes, long-term coordinated production and cutting plans are often created based on predicted demand. However, real demand may differ from predictions, and replanning may be warranted by changing conditions. A mixed-integer mathematical model was proposed by minimizing both the production cost and the cost of deviating from established plans. In addition, a hybrid dynamic programming-based heuristic was proposed. Extensive experiments were conducted on randomly generated instances. The influences on the solutions are analysed by varying the holding cost per unit and the deviation cost. Finally, the proposed heuristic is applied to enterprise practice, and the results indicate that the total cost can be expected to be reduced by 14.55% on average. [ABSTRACT FROM AUTHOR]

We address the solution of Mixed Integer Linear Programming (MILP) models with strong relaxations that are derived from Dantzig–Wolfe decompositions and allow a pseudo-polynomial pricing algorithm. We exploit their network-flow characterization and provide a framework based on column generation, reduced-cost variable-fixing, and a highly asymmetric branching scheme that allows us to take advantage of the potential of the current MILP solvers. We apply our framework to a variety of cutting and packing problems from the literature. The efficiency of the framework is proved by extensive computational experiments, in which a significant number of open instances could be solved to proven optimality for the first time. [ABSTRACT FROM AUTHOR]

The maximum cut problem is a typical problem in the quantum approximate optimization algorithm (QAOA), and Ansatz circuit is an important part of the algorithm. In order to reduce the construction cost of various graph structures in Q AOA and improve its stability, this paper analyzed the optimizability of the circuit, combined the point edge storage characteristics of Dijkstra algorithm, proposed a Dijkstra-like optimization algorithm for the circuit, and applied it to the QAOA maximum cut problem. The paper used the Qiskit quantum framework to simulate the correctness of the optimization algorithm and used the real environment of IBM Quantum Composer to perform comparative experiments to verify the stability of the optimization. After comparing with the initial algorithm, the proposed algorithm reduced the CNOT gate by about 40% and significantly improves its stability. The results show that the Dijkstra-like optimization algorithm can optimize the QAOA maximum cut problem of multiple graph structures. [ABSTRACT FROM AUTHOR]

Hubs are high-degree nodes within a network, ubiquitous in complex networks such as telecommunication, biological, social and semantic networks. Here, we do not seek a hub that is a single node, but a hub consisting of k nodes. Formally, given a graph G = (V , E) , we a seek a set A ⊆ V of size k that induces a connected subgraph from which at least p edges emanate. Thus, we identify k nodes which can act as a unit (due to the connectivity constraint) that is a hub (due to the cut constraint). This problem, which we call Multi-Node Hub (MNH), is a variant of the classic Max Cut problem. While it is easy to see that MNH is W[1]-hard with respect to the parameter k , our main contribution is a parameterized algorithm that shows that MNH is FPT with respect to the parameter p. [ABSTRACT FROM AUTHOR]

We consider a natural variant of the Erdős–Rényi random graph process in which k $k$ vertices are special and are never put into the same connected component. The model is natural and interesting on its own, but is actually inspired by the multiway cut problem that itself is connected to a number of important problems in graph theory. We will show that a phase transition for the appearance of the giant component occurs when the number of special vertices is roughly n1∕3 ${n}^{1\unicode{x02215}3}$, where n $n$ is the number of vertices. [ABSTRACT FROM AUTHOR]

To solve problems such as nonexistence of solutions to two-point boundary value problem of fuzzy linear multi-term fractional differential equations with variable coefficients, it is important to consider the necessary and sufficient condition for the existence of solutions. Choe et al. (Abstr Appl Anal 5129013:1–18, 2019) only obtained the sufficient condition for the existence of solutions. In this paper, we study a necessary and sufficient condition and then derive the solution expression of the proposed problem with constant coefficients. First, we obtain the cut problem with inequality constraints corresponding to the fuzzy two-point boundary value problem and present the necessary and sufficient condition for the fuzzy value function constructed from this cut problem to be the solution to the proposed problem. Also the solution expression is presented by using the multivariate Mittag–Leffler function. Some examples are given to illustrate our results. [ABSTRACT FROM AUTHOR]

To solve the problems of high cutting forces, severe tool wear, and poor surface integrity faced by advanced materials in aerospace manufacturing, multi-dimensional vibration machining (MDVM) is receiving unprecedented attention. MDVM utilizes workpiece and/or tool vibration excited in different directions to achieve high quality and efficient machining of aeronautical hard-to-cut materials. This paper covered typical MDVM hardware systems based on different vibration mechanisms, vibration application methods, and control methods, discussed the machining mechanisms such as friction reversal and contact-separation, and displayed the application effects in extending tool life, improving surface integrity, and manufacturing functional surfaces. The diversity of vibration mechanisms and the complexity of vibration modes of the MDVM system made it difficult to develop a unified design method for vibration systems and to demonstrate the machining mechanism under the coupling of different ultrasonic-induced effects. Therefore, it is an important development direction for future research to investigate the vibration and machining characteristics of MDVM systems and reveal the unified law. [ABSTRACT FROM AUTHOR]

A major problem in the high-speed cutting process of machine tools is tool wear. Tool wear directly affects the surface quality and machining accuracy of the workpiece. However, the limits of fusing multiple sensing signals to indirectly monitor tool wear are rarely concerned in real manufacturing environments. In this paper, a tool wear identification method based on a single sensor signal is proposed. To solve the limits of less obtained information and poor anti-interference ability of single sensor, multi-domain feature fusion strategy is established. By establishing a hybrid model of deep convolutional neural network and stacked long short-term memory network, the complex mapping relationship between fusion features and tool wear is constructed. Specifically, the spatial features of the input data set are extracted by the convolution kernel of the deep convolutional neural network. Then, a stacked double-layer long short-term memory neural network is established to capture sequence features with long-term dependence, thereby identifying tool wear. Finally, the superiority of the developed method is verified by tool wear experiments. The results show that the method can be effectively applied to tool wear identification from single sensor signals, and the mean RMSE and MAE of the identification results are 9.43 and 7.15, respectively. Compared with four other traditional multiple regression methods, RMSE and MAE are reduced by 73.0% and 78.7% on average. This study provides a reference value for the industrial implementation of tool wear monitoring system. [ABSTRACT FROM AUTHOR]

• EDDI supports on-demand inference acceleration over Edge-Cloud Collaboration. • Two novel components are introduced in EDDI, namely Evaluator and Optimizer. • Evaluator derives an approximate solution to construct a DNN into an DAG. • Optimizer enables a collaborative optimization of the early-exit and the partition. • EDDI can achieve better performance in model accuracy, latency, and throughput. As the development of deep neural network (DNN) tasks that feature a directed acyclic graph (DAG) surges in modern industries, simultaneously meeting the latency and accuracy requirements of these key DNN tasks has remained elusive. The general feasible solution is to find an optimal DNN partition that combines cloud with edge computing to implement edge–cloud collaboration for DNN inference. Nevertheless, the dynamicity of network conditions and the uncertain availability of cloud computing resources pose formidable obstacles to this collaborative inference. In this study, we formulate the optimization of DNN partition as a minimum cut problem in DAG derived from DNN and then propose an early-exit DAG-DNN inference (EDDI) framework that supports synergistically on-demand inference acceleration for DAG DNN. This framework introduces two novel components: (1) Evaluator that derives an approximately optimal solution for constructing DNN into appropriate DAG, assisting in solving the optimization problem; and (2) Optimizer that enables collaborative optimization of the early exit and DNN partition strategy at run time to improve performance while meeting user-defined latency requirements. Quantitative evaluations show that EDDI outperforms state-of-the-art schemes by 10.6%, 3.3%, and 3%, on average, in terms of model accuracy, inference latency, and throughput under diverse latency constraints, respectively. Meanwhile, latency speedup ratio increases by an average of 8% and 4% under varying network conditions and cloud server capacities, respectively. [ABSTRACT FROM AUTHOR]

In a previous work joint with Dai and Luo, we show that a connected generalized Sierpinski carpet (or shortly a GSC) has cut points if and only if the associated n-th Hata graph has a long tail for all n ≥ 2. In this paper, we extend the above result by showing that it suffices to check a finite number of those graphs to reach a conclusion. This criterion provides a truly "algorithmic" solution to the cut point problem of connected GSCs. We also construct for each m ≥ 1 a connected GSC with exactly m cut points and demonstrate that when m ≥ 2, such a GSC must be of the so-called non-fragile type. [ABSTRACT FROM AUTHOR]

Many problems in imaging and low-level vision can be formulated as nonconvex variational problems. A promising class of approaches to tackle such problems are convex relaxation methods, which consider a lifting of the energy functional to a higher-dimensional space. However, they come with increased memory requirements due to the lifting. The present paper is an extended version of the earlier conference paper by Ye et al. (in: DAGM German conference on pattern recognition (GCPR), 2021) which combined two recent approaches to make lifting more scalable: product-space relaxation and sublabel-accurate discretization. Furthermore, it is shown that a simple cutting-plane method can be used to solve the resulting semi-infinite optimization problem. This journal version extends the previous conference work with additional experiments, a more detailed outline of the complete algorithm and a user-friendly introduction to functional lifting methods. [ABSTRACT FROM AUTHOR]

High-speed abrasive water jet machining (AWJM) is a universal tool for manufacturing engineering materials. However, the application of AWJM is greatly limited due to the jet lag value caused by the cutting front profile. This paper proposes a new method to predict jet lag values at different cutting depths. The novelty is that a simplified mathematical model of the cutting front profile is developed based on the energy balance theory. Two groups of experiments were conducted to investigate the influences of process parameters on the jet lag value and the dissipated energy during cutting. The numerical regression method is adopted to obtain the energy dissipation function, which has taken the key parameters such as material property, cutting depth, traverse speed, and the initial water jet energy into consideration. The predicted curves are compared with experimental results under different operating situations with the least value of R 2 = 0.9136 and the maximum deviation in percent of 16% at the jet exit point. The proposed method contributes to further research on product distortion in abrasive water jet cutting. • A new mathematical model is established to predict the jet lag values at different depths based on the energy balance approach. • The analysis of variance regression method is adopted to obtain the energy dissipation function. • The influences of key parameters on the dissipated energy are systematically analyzed. [ABSTRACT FROM AUTHOR]

Hypergraph generalizations of many graph cut problems and algorithms have recently been introduced to better model data and systems characterized by multiway relationships. Recent work in machine learning and theoretical computer science uses a generalized cut function for a hypergraph H = (V, E) that associates each hyperedge e ∈ E with a splitting function we, which assigns a penalty to each way of separating the nodes of e. When each we satisfies we(S) = g(|S|) for some concave function g, previous work has shown how to reduce the generalized hypergraph cut problem to a directed graph cut problem, although the resulting graph may be very dense. We introduce a framework for sparsifying hypergraph-to-graph reductions, where the hypergraph cut function is (1+ε)-approximated by a cut on a directed graph. For ε > 0 we need at most O(ε-1|e|log|e|) edges to reduce any hyperedge e, while only O(|e|ε-1/2log log1/ε) edges are needed to approximate the clique expansion, a widely used heuristic in hypergraph clustering. Our framework leads to improved results for solving cut problems in co-occurrence graphs, decomposable submodular function minimization problems, and localized hypergraph clustering problems. [ABSTRACT FROM AUTHOR]

The rectangular packing problem is an NP-complete combinatorial optimization problem. This problem occurs widely in social production scenarios, with steel plate cutting being one example. The cutting scheme for the rectangular packing problem needs to be improved because, without the globally optimal solution, there are many unnecessary edges in the steel cutting process. Based on a practical roll-fed disc shearing steel plate optimization problem, this paper explores a generalized packing method for rectangles of special dimensions and abstractly condenses complex quantitative relationships to establish a multi-objective mixed-integer nonlinear programming model. An innovative algorithm design based on a genetic algorithm is established to plan the cutting scheme in a high-speed and efficient way. The outcome is a utilization rate of up to 92.73% for raw materials and a significant reduction in labor, providing a guide for practical production and processing tasks. The advantages and disadvantages of the model and algorithm are discussed, and it is concluded that this rectangular packing method has strong universality and generalization ability, allowing rectangular packing tasks with large data volumes to be completed within a short time. [ABSTRACT FROM AUTHOR]

The Cutting Stock Problem (CSP) is an optimisation problem that roughly consists of cutting large objects in order to produce small items. The computational effort for solving this problem is largely affected by the number of cutting patterns. In this article, in order to cope with large instances of the One-Dimensional Cutting Stock Problem (1D-CSP), we resort to a pattern generating procedure and propose a strategy to restrict the number of patterns generated. Integer Linear Programming (ILP) models, an implementation of the Column Generation (CG) technique, and an application of the Generate-and-Solve (G&S) framework were used to obtain solutions for benchmark instances from the literature. The exact method was capable of solving small and medium sized instances of the problem. For large sized instances, the exact method was not applicable, while the effectiveness of the other methods depended on the characteristics of the instances. In general, the G&S method presented successful results, obtaining quasi-optimal solutions for the majority of the instances, by employing the strategy of artificially reducing the number of cutting patterns and by exploiting them in a heuristic framework. [ABSTRACT FROM AUTHOR]

Graph sparsification underlies a large number of algorithms, ranging from approximation algorithms for cut problems to solvers for linear systems in the graph Laplacian. In its strongest form, "spectral sparsification" reduces the number of edges to near-linear in the number of nodes, while approximately preserving the cut and spectral structure of the graph. In this work we demonstrate a polynomial quantum speedup for spectral sparsification and many of its applications. In particular, we give a quantum algorithm that, given a weighted graph with n nodes and m edges, outputs a classical description of an ϵ-spectral sparsifier in sublinear time Õ(√mn/ϵ). This contrasts with the optimal classical complexity Õ(m). We also prove that our quantum algorithm is optimal up to polylog-factors. The algorithm builds on a string of existing results on sparsification, graph spanners, quantum algorithms for shortest paths, and efficient constructions for k-wise independent random strings. Our algorithm implies a quantum speedup for solving Laplacian systems and for approximating a range of cut problems such as min cut and sparsest cut. [ABSTRACT FROM AUTHOR]

Circular saw blades are widely used in stone processing. The circular saw blade cutting hard rock numerical simulation model based on ANSYS/LS-DYNA was established to investigate the complex dynamic problem in rock cutting. The failure mechanism of the rock and the influence of cutting parameters on the cutting force and rock fragments were studied by numerical simulation. The results demonstrated that the failure modes of the rock were mainly tensile failure with some shear failure and compressive failure. The cutting force and the number of fragments increased with the feed speed. With the increasing circular saw blade rotational speed, the cutting force and the number of fragments decreased and tended to stabilize. With the distance between the circular saw blades increasing, the cutting force and rock fragments number increase and then maintain basic stability, and when the distance between double circular saw blades reaches 25 mm, it will form a completed rock plate and the interaction of circular saw blades will decrease. The numerical simulation can accurately simulate rock breakage and force when a circular saw blade cuts rock. [ABSTRACT FROM AUTHOR]

In an undirected graph, a matching cut is a partition of vertices into two sets such that the edges across the sets induce a matching. The Matching Cut problem is the problem of deciding whether a given graph has a matching cut. Let H be a fixed undirected graph. A vertex coloring of an undirected input graph G is said to be an H - Free Coloring if none of the color classes contain H as an induced subgraph. The H - Free Chromatic Number of G is the minimum number of colors required for an H - Free Coloring of G. Both The Matching Cut problem and the H - Free Coloring problem can be expressed using a monadic second-order logic (MSOL) formula and hence is solvable in linear time for graphs with bounded tree-width. However, this approach leads to a running time of f (| | φ | | , t) n O (1) , where | | φ | | is the length of the MSOL formula, t is the tree-width of the graph and n is the number of vertices of the graph. The dependency of f (| | φ | | , t) on | | φ | | can be as bad as a tower of exponentials. In this paper, we provide explicit combinatorial FPT algorithms for Matching Cut problem and H - Free Coloring problem, parameterized by the tree-width of G. The single exponential FPT algorithm for the Matching Cut problem answers an open question posed by Kratsch and Le (2016). The techniques used in the paper are also used to provide an FPT algorithm for a variant of H -free coloring, where H is forbidden as a subgraph (not necessarily induced) in the color classes of G. [ABSTRACT FROM AUTHOR]