Search

We show that any memory-constrained, first-order algorithm which minimizes d-dimensional, 1-Lipschitz convex functions over the unit ball to 1/poly(d) accuracy using at most d1.25 - δ bits of memory must make at least \(\tilde{\Omega }(d^{1 + (4/3)\delta })\) first-order queries (for any constant \(\delta \in [0, 1/4]\)). Consequently, the performance of such memory-constrained algorithms are at least a polynomial factor worse than the optimal Õ(d) query bound for this problem obtained by cutting plane methods that use Õ(d2) memory. This resolves one of the open problems in the COLT 2019 open problem publication of Woodworth and Srebro. [ABSTRACT FROM AUTHOR]

This paper studies the constrained two-dimensional non-guillotine cutting problem with defects, in which a set of items of a specific size is cut from a large rectangular sheet with defective areas, with the number of each type of cut item cannot exceed a specified quantity. The objective is to maximise the total value of the cut items. We propose a decomposition approach to address the problem. The process involves decomposing the original problem into a master problem and a subproblem. The master problem is formulated as a one-dimensional contiguous bin packing problem, while the subproblem is an x-Check problem to identify a two-dimensional packing that does not lead to any overlap. The x-Check problem is effectively addressed by using an integer linear programming model. When the x-Check problem proves infeasible, cuts are added to the master problem, and the iteration is repeated until the x-Check finds a feasible solution. Furthermore, we introduce several novel techniques, including valid inequalities, preprocessing techniques, and lifting the cut methods to improve the performance of the algorithm. Extensive computational results show that our method can quickly find the optimal solution for the 5450 instances in the literature. [ABSTRACT FROM AUTHOR]

This paper introduces novel mathematical optimisation models for the 2-Dimensional guillotine Cutting Stock Problem with Variable-Sized Stock that appears in a Spanish company in the honeycomb cardboard industry. This problem mainly differs from the classical cutting stock problems in the stock, which is considered variable-sized, i.e. we have to decide the panel dimensions, width, and length. This approach is helpful in industries where the stock is produced simultaneously with the cutting process. The stock is then cut into smaller rectangular pieces that must meet the customers' requirements, such as the type of item, dimensions, demands, and technical specifications. Furthermore, in the problem tackled in this paper, the cuts are guillotine, performed side to side. The proposed mathematical models are validated using real data from the company, obtaining results that drastically reduce the produced material and leftovers, reducing operation times and economic costs. [ABSTRACT FROM AUTHOR]

Advances in quantum computing with applications in combinatorial optimization have evolved at an increasing rate in recent years. The quadratic unconstrained binary optimization (QUBO) model is at the center of these developments and has become recognized as an effective alternative method for representing a wide variety of combinatorial optimization problems. Additional momentum has resulted from the arrival of quantum computers and their ability to solve the Ising spin glass problem, another form of the QUBO model. This paper highlights advances in solving QUBO models and extensions to more general polynomial unconstrained binary optimization (PUBO) models as important alternatives to traditional approaches. Computational experience is provided that compares the performance of unique quantum‐inspired metaheuristic solvers—the Next Generation Quantum (NGQ) solver for QUBO models and the NGQ‐PUBO solver for PUBO models—with the performance of CPLEX and the Dwave quantum advantage solver. Extensive results, including experiments with a set of large set partitioning problems representing the largest QUBO models reported in the literature to date, along with maximum diversity and max cut problem sets, disclose that our solvers outperform both CPLEX and Dwave by a wide margin in terms of both computational time and solution quality. [ABSTRACT FROM AUTHOR]

The objective of the max-cut problem is to cut any graph in such a way that the total weight of the edges that are cut off is maximum in both subsets of vertices that are divided due to the cut of the edges. Although it is an elementary graph partitioning problem, it is one of the most challenging combinatorial optimization-based problems, and tons of application areas make this problem highly admissible. Due to its admissibility, the problem is solved using the Harris Hawk Optimization algorithm (HHO). Though HHO effectively solved some engineering optimization problems, is sensitive to parameter settings and may converge slowly, potentially getting trapped in local optima. Thus, HHO and some additional operators are used to solve the max-cut problem. Crossover and refinement operators are used to modify the fitness of the hawk in such a way that they can provide precise results. A mutation mechanism along with an adjustment operator has improvised the outcome obtained from the updated hawk. To accept the potential result, the acceptance criterion has been used, and then the repair operator is applied in the proposed approach. The proposed system provided comparatively better outcomes on the G-set dataset than other state-of-the-art algorithms. It obtained 533 cuts more than the discrete cuckoo search algorithm in 9 instances, 1036 cuts more than PSO-EDA in 14 instances, and 1021 cuts more than TSHEA in 9 instances. But for four instances, the cuts are lower than PSO-EDA and TSHEA. Besides, the statistical significance has also been tested using the Wilcoxon signed rank test to provide proof of the superior performance of the proposed method. In terms of solution quality, MC-HHO can produce outcomes that are quite competitive when compared to other related state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

With problems of low cutting efficiency, poor forming quality, and low control accuracy in large-section semi-coal rock roadway tunneling, comprehensive coal tunneling seriously lags behind fully mechanized mining. A fuzzy PID control method was proposed, taking the cutting robot in a shield-type tunneling system as the research object. Using mathematical analysis and other methods, a kinematic model of the cutting robot was established, and the pose transformation matrix of the cutting robot during the cutting process was obtained. A limit model for the motion space of the cutting robot cutting drum was established, and the motion relationship between the driving cylinder and the cutting drum was obtained. A fuzzy PID cutting robot control scheme was designed. The feasibility of the model was validated by simulation methods, and the correctness of the model and simulation was verified through on-site experiments. The results indicate that the established cutting robot model is correct, and the proposed fuzzy PID control method for the cutting robot is feasible. The maximum error of the center control of the cutting drum was 5.5 mm, and the average date was 0.89 mm, which was far less than the standard of 50 mm for engineering of the cross-section cutting of the roadway. This study enriches the control theory of shield-type cutting robots by improving control accuracy, enhancing the cutting efficiency of large-section semi-coal rock tunnels, ensuring the quality of section forming, and narrowing the gap between comprehensive coal tunneling and fully mechanized mining. [ABSTRACT FROM AUTHOR]

Purpose: The mine sequencing problem is NP-hard. Therefore, simplifying it is necessary. One way to do this is to employ clusters as input instead of individual blocks. The mining cut clustering problem has been little addressed in the literature, and the solutions used are almost always heuristic. We solve the mining cut clustering problem, which is NP-hard, through single- and multi-objective optimization, finding results that are local optima in acceptable computational time. Design/methodology/approach: We first elaborate an ILP-based model to address the mining cut clustering problem. We employ a mono-objective approach and two multi-objective approaches, solving all these models by constraint programming. To choose the best solutions generated by multi-objective approaches, we employ two multi-criteria decision analysis approaches, considering different weight configurations. We developed a case study using real data. Findings: We verified that the approaches based on multi-objective optimization performed better than the mono-objective approach for the economic return criterion. The weighted-sum multi-objective approach presented the best results considering all objective functions used. Once viable solutions were obtained through multi-objective optimization, multi-criteria decision analysis approaches almost always selected the same solution. We obtained solutions that are local optima in acceptable computational time. Research limitations/implications: This study solves an instance with 80 blocks. Consequently, it is aimed at short-term mine planning. The methodology has not yet been evaluated in large instances related to medium- and long-term mine planning. Originality/value: This is the first time that multi-objective optimization has been employed to solve the mining cut custering problem. Even other problems related to mine planning were, at most, solved by goal programming, so that multi-objective optimization is a knowledge that is not widespread among mining researchers. The results are consistent, and the study achieves the objective of finding quality solutions to an NP-hard problem in an acceptable computational time. [ABSTRACT FROM AUTHOR]

Interest in integrating lot-sizing and cutting stock problems has been increasing over the years. This integrated problem has been applied in many industries, such as paper, textile and furniture. Yet, there are only a few studies that acknowledge the importance of uncertainty to optimise these integrated decisions. This work aims to address this gap by incorporating demand uncertainty through stochastic programming and robust optimisation approaches. Both robust and stochastic models were specifically conceived to be solved by a column generation method. In addition, both models are embedded in a rolling-horizon procedure in order to incorporate dynamic reaction to demand realisation and adapt the models to a multistage stochastic setting. Computational experiments are proposed to test the efficiency of the column generation method and include a Monte Carlo simulation to assess both stochastic programming and robust optimisation for the integrated problem. Results suggest that acknowledging uncertainty can cut costs by up to 39.7%, while maintaining or reducing variability at the same time. [ABSTRACT FROM AUTHOR]

We address three variants of the two-dimensional cutting stock problem in which the guillotine cutting of large objects produces a set of demanded items. The characteristics of the variants are the rectangular shape of the objects and items; the number of two or three orthogonal guillotine stages; and a sequencing constraint that limits the number of open stacks to a scalar associated with the number of automatic compartments or available space near the cutting machine. These problems arise in manufacturing environments that seek minimum waste solutions with limited levels of work-in-process. Despite their practical relevance, we are not aware of mathematical models for them. In this paper, we propose an integer linear programming (ILP) formulation for each of these variants based on modelling strategies for the two-dimensional guillotine cutting stock problem and the minimisation of the open stacks problem. The first two variants deal with exact and non-exact 2-stage patterns, and the third with a specific type of 3-stage patterns. Using a general-purpose ILP solver, we performed computational experiments to evaluate these approaches with benchmark instances. The results show that several equivalent solutions of the cutting problem allow obtaining satisfactory solutions with a reduced number of open stacks. [ABSTRACT FROM AUTHOR]

This paper studies the constrained two-dimensional guillotine cutting problem with defects, whose objective is to cut a subset of given items from a defective sheet such that the profit of selected items is maximised. The guillotine cut constraint, which requires each cut must go through one side of the sheet to the opposite side, is considered. We solve this problem via a recursive dynamic programming approach. A set of upper bounds is proposed to keep the promising nodes. The normal points and raster points are extended to reduce the number of vertical and horizontal cuts by considering the effect of the defect. The experiment results show that our approach can solve most of the instances in the literature and outperforms existing approaches. [ABSTRACT FROM AUTHOR]

In this paper, we consider the following two problems: (i) Deletion Blocker (α) where we are given an undirected graph G = (V , E) and two integers k , d ≥ 1 and ask whether there exists a subset of vertices S ⊆ V with | S | ≤ k such that α (G − S) ≤ α (G) − d , that is the independence number of G decreases by at least d after having removed the vertices from S ; (ii) Transversal (α) where we are given an undirected graph G = (V , E) and two integers k , d ≥ 1 and ask whether there exists a subset of vertices S ⊆ V with | S | ≤ k such that for every maximum independent set I we have | I ∩ S | ≥ d. We show that both problems are polynomial-time solvable in the class of co-comparability graphs by reducing them to the well-known Vertex Cut problem. Our results generalise a result of Chang et al. (2001) and a recent result of Hoang et al. (2023). [ABSTRACT FROM AUTHOR]

Underwater acoustic transducer based on high piezoelectric phase volume fraction, large thickness, large area and curved piezoelectric composites (PC) possess wider beam width, higher source level and better directivity. However, the curved PC with large size is difficult to fabricate. The preparation of curved PC with large size and high piezoelectric phase volume fraction is even more tricky. The reported methods have risks of depolarization, deformation and poor periodicity and are not suitable for preparing PC with high piezoelectric phase volume fraction and large thickness. In this work, we proposed a novel fabrication method of the shaped-mold-assisted dice and fill technology. The 1–3 PC with high piezoelectric ceramic volume fraction of 80 %, thickness of 4.3 mm and area of 340 mm × 77 mm and the 2-2 PC with high piezoelectric ceramic volume fraction of 89.5 %, thickness of 5 mm and area of 262 mm × 20 mm were fabricated. The piezoelectric coefficient d 33 and relative constant stress permittivity ε 33 T / ε 0 of 1–3 and 2-2 PCs were comparable to piezoelectric phase itself. In addition, both 1–3 and 2-2 PCs exhibited a favorable performance consistency. This method solved the problem of limited cutting depth of thin blade, realizing PC with the structure of high piezoelectric phase volume fraction (＞ 70 %) and large thickness (＞ 3 mm) and eliminates the risk of depolarization, deformation and poor periodicity. This work enabled the potential for achieving large area, high piezoelectric phase volume and special-shaped PCs, which offers new ideas for designing innovative acoustic transducers and facilitates the progress of acoustic sensing technology. [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]

Given a graph G = (V , E) and a set S ⊆ V 2 of terminal pairs, the minimum multicut problem asks for a minimum edge set δ ⊆ E such that there is no s-t-path in G - δ for any { s , t } ∈ S . For | S | = 1 this is the well known s-t-cut problem, but in general the minimum multicut problem is NP-complete, even if the input graph is a tree. The multicut polytope M U L T C □ (G , S) is the convex hull of all multicuts in G; the multicut dominant is given by M U L T C (G , S) = M U L T C □ (G , S) + R ≥ 0 E . The latter is the relevant object for the minimization problem. While polyhedra associated to several cut problems have been studied intensively there is only little knowledge for multicut. We investigate properties of the multicut dominant and in particular derive results on liftings of facet-defining inequalities. This yields a classification of all facet-defining path- and edge inequalities. Moreover, we investigate the effect of graph operations such as node splitting, edge subdivisions, and edge contractions on the multicut-dominant and its facet-defining inequalities. In addition, we introduce facet-defining inequalities supported on stars, trees, and cycles and show that the former two can be separated in polynomial time when the input graph is a tree. [ABSTRACT FROM AUTHOR]

This paper addresses the one-dimensional cutting stock problem, focusing on minimizing total stock usage. Most procedures that deal with this problem reside on linear programming methods, heuristics, metaheuristics, and hybridizations. These methods face drawbacks like handling only low-complexity instances or requiring extensive parameter tuning. To address these limitations we develop a Petri-net model to construct cutting patterns. Using the filtered beam search algorithm, the reachability tree of the Petri net is constructed level by level from its root node to find the best solution, pruning the nodes that worsen the solution as the search progresses through the tree. Our algorithm is compared with the Least Lost Algorithm and the Generate and Solve algorithm over five datasets of instances. These algorithms share some characteristics with ours and have proven to be effective and efficient. Experimental results demonstrate that our algorithm effectively finds optimal and near-optimalsolutions for both low and high-complexity instances. These findings confirm that Petri nets are suitable for modeling and solving the one-dimensional cutting stock problem. [ABSTRACT FROM AUTHOR]

Cutting and Packing problems have been recognized as a sub-discipline of operation research for more than half a century. Such problems are involved in a range of circumstances such as pallet loading, wood or glass cutting, strip packing, and positioning problems. The focus of this study is on 2D rectangular strip packing problems in which rectangle items are not oriented and guillotine constraint is not considered aiming to pack all these items without overlapping into an open-ended bin called a strip of fixed width while the objective is obtaining the minimum total height of cutting. The main aim of this paper is to introduce two proposed heuristics for solving the problem under study. The two heuristics are improved versions of the known Best Fit heuristics, Tower Checker Best Fit (TCBF) and Waste Priority Best Fit (WPBF). The performance of the proposed heuristics is tested using well-known benchmark problems. The computational analysis of the results shows that the proposed heuristics can generate near-optimal solutions to large-scale problems. In addition, the performance of the heuristics outperforms other well-known heuristics from literature by 3%. [ABSTRACT FROM AUTHOR]

About 15 years ago, a paper proposed the first integer linear programming formulation for the constrained two‐dimensional guillotine cutting problem (with unlimited cutting stages). Since then, eight other formulations followed, seven of them in the last four years. This spike of interest gave no opportunity for a comprehensive comparison between the formulations. We review each formulation and compare their empirical results over instance datasets of the literature. We adapt most formulations to allow for piece rotation. The possibility of adaptation was already predicted but not realized by the prior work. The results show the dominance of pseudo‐polynomial formulations until the point instances become intractable by them, while more compact formulations keep achieving good primal solutions. Our study also reveals a mistake in the generation of the T instances, which should have the same optima with or without guillotine cuts. We also propose hybridising a recent formulation with a prior formulation for a restricted version of the problem. The hybridisations show a reduction of about 20% of the branch‐and‐bound time thanks to the symmetries broken by the hybridisation. [ABSTRACT FROM AUTHOR]

Microwave treatment is one of the research topics to solve cutting problems of hard rocks such as low cutting rate and high tool wear. Microwave irradiation creates fractures in the rock body and decreases its strength. Numerous studies have been conducted to ascertain how microwaves affect the strength of rocks. Ten carbonate rocks are examined in this paper to see how microwaving affects their strength. First, unconfined compression and tensile strength tests were conducted on unirradiated dry and saturated core specimens. Following that, the two tests were performed again on samples that had been exposed to radiation for varying amounts of time—between 2 and 6 min—at a microwave power of 6 kW. The results showed that the uniaxial compressive strength loss due to microwave irradiation was between 9.0 and 90.0% and 7.3 and 92.0% for the dry and saturated samples, respectively. Tensile strength loss was between 15.6 and 62.7% and 23.2 and 63.1% for the dry and saturated samples, respectively. The efficiency of treating carbonate rocks with microwaves is significantly impacted by density, porosity, and impurities. Multiple regression equations were derived to estimate the strength losses. Concluding remark is that the strength reductions due to microwaves are significant for carbonate rocks. [ABSTRACT FROM AUTHOR]

In this study, the 1.5-dimensional cutting stock problem with technical constraints is considered. In the literature, this problem is also defined as a strip packing or open dimension problem. When given a strip of infinite length and bounded width, the problem is to define a packing of rectangular objects into a strip that minimizes its final length. Technical constraints, such as the order type and the number of strips, are indispensable in real life; however, they are often neglected in the literature because they make the problem difficult to solve. Only one study was reached in the literature that took into account technical constraints, but in that mentioned study, only a mathematical model was proposed for the problem. In this context, our aim is to solve the problem with a more effective approach. The research question in this study is the usability of the column generation technique to solve the 1.5-dimensional cutting stock problem. In this study, the column generation approach was proposed for the first time for the considered problem. To demonstrate the performance of the proposed solution method, randomly generated test problems were solved with GAMS/Cplex. As we report the results, proposed column generation approach (CG) reaches very close (such as 1% and 2% error) solutions to integrated mathematical model (IM) for small sized problems in a second. On the other hand, while CG solved all the problems in a reasonable time, IM could not produce a feasible solution to some problems. Numerical experiments showed that the column generation algorithm outperforms the integrated mathematical model for the problem. [ABSTRACT FROM AUTHOR]

The recent explosion of Large Language Models (LLMs) has provoked lively debate about "emergent" properties of the models, including intelligence, insight, creativity, and meaning. These debates are rocky for two main reasons: The emergent properties sought are not well-defined; and the grounds for their dismissal often rest on a fallacious appeal to extraneous factors, like the LLM training regime, or fallacious assumptions about processes within the model. The latter issue is a particular roadblock for LLMs because their internal processes are largely unknown - they are colossal black boxes. In this paper, I try to cut through these problems by, first, identifying one salient feature shared by systems we regard as intelligent/conscious/sentient/etc., namely, their responsiveness to environmental conditions that may not be near in space and time. They engage with subjective worlds ("s-worlds") which may or may not conform to the actual environment. Observers can infer s-worlds from behavior alone, enabling hypotheses about perception and cognition that do not require evidence from the internal operations of the systems in question. The reconstruction of s-worlds offers a framework for comparing cognition across species, affording new leverage on the possible sentience of LLMs. Here, we examine one prominent LLM, OpenAI's GPT-4. Inquiry into the emergence of a complex subjective world is facilitated with philosophical phenomenology and cognitive ethology, examining the pattern of errors made by GPT-4 and proposing their origin in the absence of an analogue of the human subjective awareness of time. This deficit suggests that GPT-4 ultimately lacks a capacity to construct a stable perceptual world; the temporal vacuum undermines any capacity for GPT-4 to construct a consistent, continuously updated, model of its environment. Accordingly, none of GPT-4's statements are epistemically secure. Because the anthropomorphic illusion is so strong, I conclude by suggesting that GPT-4 works with its users to construct improvised works of fiction. [ABSTRACT FROM AUTHOR]

Reducing material waste and computation time are primary objectives in cutting and packing problems (C &P). A solution to the C &P problem consists of many steps, including the grouping of items to be nested and the arrangement of the grouped items on a large object. Current algorithms use meta-heuristics to solve the arrangement problem directly without explicitly addressing the grouping problem. In this paper, we propose a new pipeline for the nesting problem that starts with grouping the items to be nested and then arranging them on large objects. To this end, we introduce and motivate a new concept, namely the Geometrical Compatibility Index (GCI). Items with higher GCI should be clustered together. Since no labels exist for GCIs, we propose to model GCIs as bidirectional weighted edges of a graph that we call geometrical relationship graph (GRG). We propose a novel reinforcement-learning-based framework, which consists of two graph neural networks trained in an actor-critic-like fashion to learn GCIs. Then, to group the items into clusters, we model the GRG as a capacitated vehicle routing problem graph and solve it using meta-heuristics. Experiments conducted on a private dataset with regularly and irregularly shaped items show that the proposed algorithm can achieve a significant reduction in computation time (30% to 48%) compared to an open-source nesting software while attaining similar trim loss on regular items and a threefold improvement in trim loss on irregular items. [ABSTRACT FROM AUTHOR]

The thermal-controlled fracture method has been increasingly focused upon in the high-quality cutting of advanced ceramic materials due to its excellent characteristics. The successful application of this method in cutting ceramics mainly depends on the volumetric heating effect. However, most ceramics are treated using the surface heating mode. For the surface heating mode, the processing quality, including fracture trajectory and fracture quality, is far lower than the industrial application standards. This work was conducted to reveal the mechanism of this processing quality. Experiments involving cutting ceramics in single-surface heating mode indicate that the fracture trajectories of the upper and lower surfaces display a significant inconsistency, and the fracture quality is worse than that using the dual-surface heating mode. A cutting model was established to calculate the thermal stress distribution and to simulate the crack-propagation behaviors. The simulation results show good agreement with the experiment and provide the stress distribution, and are used to understand the reason for the processing quality problem. The mechanism of the trajectory deviation and uneven distribution of the fracture quality is revealed based on the simulation and calculation results. This study helps provide a deep understanding of the processing problems arising from this method and thus helps to innovate high-quality processing methods in this field. [ABSTRACT FROM AUTHOR]

Global changes cause widespread forest fragmentation, which, in turn, has given rise to many ecological problems; this is especially true if the forest carbon stock is profoundly impacted by fragmentation levels. However, the way in which forest carbon uptake changes with different fragmentation levels and the main pathway through which fragmentation affects forest carbon uptake are still unclear. Remote sensing data, vegetation photosynthesis models, and fragmentation models were employed to generate a time series GPP (gross primary productivity) dataset, as well as forest fragmentation levels for forest landscapes in Zhejiang province, China. We analyzed GPP variation with forest fragmentation levels and identified the relative importance of the phenology (carbon uptake period—CUP) and physiology (maximum daily GPP—GPPmax) control pathways of GPP under different fragmentation levels. The results showed that the normalized mean annual GPP data of highly fragmented forests during the period from 2000 to 2018 were significantly higher than those of other fragmentation levels, while there was almost no significant difference in the annual GPP trend of forest landscapes with all fragmentation levels. Moreover, the percentage area of the control variable, GPPmax, gradually increased with fragmentation levels; the mean GPPmax between 2000 and 2018 of high-level fragmentation was higher than that of other fragmentation levels. Our results demonstrate that the carbon uptake capacity per unit area was enhanced in highly fragmented forest areas, and the maximum photosynthetic capacity (physiology-based process) played an important role in controlling carbon uptake, especially in highly fragmented forest landscapes. Our study calls for a better and deeper understanding of the potential of forest carbon uptake, and it is necessary to explore the mechanism by which forest fragmentation changes the vegetation photosynthetic process. [ABSTRACT FROM AUTHOR]

In the non-uniform sparsest cut problem, we are given a supply graph G and a demand graph D, both with the same set of nodes V. The goal is to find a cut of V that minimizes the ratio of the total capacity on the edges of G crossing the cut over the total demand of the crossing edges of D. In this work, we study the non-uniform sparsest cut problem for supply graphs with bounded treewidth k. For this case, Gupta et al. (ACM STOC, 2013) obtained a 2-approximation with polynomial running time for fixed k, and it remained open the question of whether there exists a c-approximation algorithm for a constant c independent of k, that runs in FPT time. We answer this question in the affirmative. We design a 2-approximation algorithm for the non-uniform sparsest cut with bounded treewidth supply graphs that runs in FPT time, when parameterized by the treewidth. Our algorithm is based on rounding the optimal solution of a linear programming relaxation inspired by the Sherali-Adams hierarchy. In contrast to the classic Sherali-Adams approach, we construct a relaxation driven by a tree decomposition of the supply graph by including a carefully chosen set of lifting variables and constraints to encode information of subsets of nodes with super-constant size, and at the same time we have a sufficiently small linear program that can be solved in FPT time. [ABSTRACT FROM AUTHOR]

Hard work like climbing a tall coconut tree while balancing and stretching the whole body increases musculoskeletal discomfort and pain. Scratches, cuts and dermatitis problems cause serious health problems. Injury and accidents badly affect the human body, reducing farmers' productivity and quality of work. Sometimes, they are physically incapable of performing such work or die. Sometimes, disasters and environmental conditions have a negative impact on coconut farming. The main aim of this study was to calculate the discomfort level of coconut farmers in the coastal districts of Odisha using the QEC (quick exposure checkup) tool of Ergofellow 3.0. [ABSTRACT FROM AUTHOR]

Copyright of China Mining Magazine is the property of China Mining Magazine Co., Ltd. and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

The study examines the proliferation of small arms and light weapons (SALW) and the susceptible factors responsible for illicit SALW infiltration in Nigeria. The study investigates the implications of illegal acquisition of SALW on Nigeria's security architecture and the institutional efforts to mitigate the influence of illicit SALWs on Nigerian soil. The study adopts descriptive survey research for rigorous analysis of the implication of the illegal proliferation of SALW on Nigeria's security architecture. The study found several measures have been rolled out to salvage the country from the imbroglio. Still, the efforts yielded little results because they cut the problem from the edge instead of uprooting it. Finally, collective security theory was used to analyse the subject matter; providing economic and cultural security was suggested to tackle the precarious country's insecurity challenges orchestrated by the proliferation of SALWs. [ABSTRACT FROM AUTHOR]

Oleaginous Flax is harvested using direct combining to obtain seeds. During this process - Stem-Fiber Mass (SFM) is disposed of by incineration or shredding. Both cases are harmful to the environment. With a sufficient amount of moisture and heat, a short non-oriented fiber is formed in a stem. The fiber creates a problem in the operation of the cutting device of the harvester. Especially, when harvesting Oleaginous Flax in the phase of full ripeness, when the fiber has strengthened and the woody part has turned into a shives. Thus, it is possible to save the grown crop by pulling the stems. Well-known technical means of pulling flax stems have a small width of grip, which affects their productivity. The solution to the problem lies in the creation of the harvesting working bodies, taking into account the width of the harvester. Such a device, when installed on the harvesting part of the combine, should not disturb its structure. As a section of the working body, a pair of rollers of the appropriate geometric shape, rotating towards each other, is offered. The technological process of stem pulling involves capturing a certain number of stems with rotating surfaces and clamping them in the space between the surfaces. Superimposition of surface rotation speeds and forward speed of the grain harvester helps pull the stems out of the soil. This approach makes it possible to preserve the grown crop of Oleaginous Flax and create prerequisites for the use of the SFM. [ABSTRACT FROM AUTHOR]

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]

This paper develops an exact algorithm for the identical parallel additive machine scheduling problem by considering multiple processing alternatives to minimise the makespan. This research is motivated from an idea of elevating flexibility of a manufacturing system by using additive machines, such as 3D printers. It becomes possible to produce a job in a different form; a job can be printed in a complete form or in separate parts. This problem is defined as a bi-level optimisation model in which its upper level problem is to determine a proper processing alternative for each product, and its lower level problem is to assign the parts that should be produced to the additive machines. An exact algorithm, which consists of the linear programming relaxation of a one-dimensional cutting stock problem, a branch-and-price algorithm, and a rescheduling algorithm, is proposed to find an optimal solution of the problem. The experimental results show that the computational time of the algorithm outperforms a commercial solver (CPLEX). By examining how the parts are comprised when the processing alternatives are optimally selected, some useful insights are derived for designing processing alternatives of products. [ABSTRACT FROM AUTHOR]

This research looks at the production planning of hollow-core slabs integrated to the optimisation problem of the use of moulds. Considering the production process of these structures, two mathematical models are proposed for the arising problem, which consists of a one-dimensional multi-period cutting stock problem with innovative aspects regarding the multiple manufacturing modes that can be used to produce the slabs. In addition, a theoretical analysis of the proposed models is presented. These models are solved using heuristic methods, both aiming to minimise production and inventory costs. Using data based on real information provided by a company, the computational results showed that the heuristic based on the compact model performed better than the one based on the extended model, due to some characteristics specific to the problem being studied. [ABSTRACT FROM AUTHOR]

We address two variants of the two-dimensional guillotine cutting problem that appear in different manufacturing settings that cut defective objects. Real-world applications include the production of flat glass in the glass industry and the cutting of wooden boards with knotholes in the furniture industry. These variants assume that there are several defects in the object, but the items cut should be defective-free; the cutting pattern is limited to two guillotine stages; and the maximum number of copies per item type in the pattern can be limited. The first variant deals with exact 2-stage patterns, while the second with exact 1-group patterns. To effectively solve these problems, we propose a Constraint Programming (CP) based algorithm as well as different Integer Linear Programming (ILP) formulations. The first presented formulations are extensions of the modelling approach of [Martin, M., E. G. Birgin, R. D. Lobato, R. Morabito, and P. Munari. 2020. "Models for the Two-Dimensional Rectangular Single Large Placement Problem with Guillotine Cuts and Constrained Pattern." International Transactions in Operational Research 27: 767–793. doi:] for the case with defects, while the others are novel and more elaborate formulations based on the relative position of the items. We evaluate these three approaches with computational experiments using a set of benchmark instances from the literature. The results show that the approaches find optimal and near-optimal solutions in short processing times for several types of problem instances. [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]

We give a new decomposition theorem in unit disk graphs (UDGs) and demonstrate its applicability in the fields of Structural Graph Theory and Parameterized Complexity. First, our new decomposition theorem shows that the class of UDGs admits an "almost" Contraction Decomposition Theorem. Prior studies on this topic exhibited that the classes of planar graphs [Klein, SICOMP, 2008], graphs of bounded genus [Demaine, Hajiaghayi and Mohar, Combinatorica 2010], and H-minor free graphs [Demaine, Hajiaghayi and Kawarabayashi, STOC 2011] admit a Contraction Decomposition Theorem. Even bounded-degree UDGs can contain arbitrarily large cliques as minors, and therefore our result is a significant advance in the study of contraction decompositions. Additionally, this result answers an open question posed by Hajiaghayi (www.youtube.com/watch?v=2Bq2gy1N01w) regarding the existence of contraction decompositions for classes of graphs beyond H-minor free graphs though under a relaxation of the original formulation. Second, we present a "parameteric version" of our new decomposition theorem. We prove that there is an algorithm that, given a UDG G and a positive integer k, runs in polynomial time and outputs a collection of \(\mathcal {O}(k)\) tree decompositions of G with the following properties. Each bag in any of these tree decompositions can be partitioned into \(\mathcal {O}(k)\) connected pieces (we call this measure the chunkiness of the tree decomposition). Moreover, for any subset S of at most k edges in G, there is a tree decomposition in the collection such that S is well preserved in the decomposition in the following sense. For any bag in the tree decomposition and any edge in S with both endpoints in the bag, either its endpoints lie in different pieces or they lie in a piece that is a clique. Having this decomposition at hand, we show that the design of parameterized algorithms for some cut problems becomes elementary. In particular, our algorithmic applications include single-exponential (or slightly super-exponential) algorithms for well-studied problems such as Min Bisection, Steiner Cut, s-Way Cut, and Edge Multiway Cut-Uncut on UDGs; these algorithms are substantially faster than the best-known algorithms for these problems on general graphs. [ABSTRACT FROM AUTHOR]

The optimization of the cutting path of the sample can effectively reduce the cutting time, thereby improving the production efficiency of numerical control processing. This paper comprehensively considers the impact of the cutting order and the position of the knife entry point on the cutting path, converts the cutting path problem into a type of traveling salesman problem (TSP), and proposes an improved genetic-particle swarm optimization algorithm. The selection mechanism of the algorithm combines the elitist retention strategy and roulette wheel selection method to accelerate the search for the optimal solution; the mutation strategy designs a linear decreasing mutation rate, which enhances the global search ability; at the same time, introduces the ant colony optimization algorithm to process the fitness function, adjusts the population evolution difference, and speeds up the optimization process. Through this hybrid algorithm, the cutting order of the sample can be quickly optimized, and the nearest neighbor algorithm is used to determine the position of the knife entry point. Tests are conducted on clothing patterning charts and standard examples. Compared with several commonly used algorithms, experimental results verify the feasibility and effectiveness of this algorithm. [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]

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]

Cut patio construction was a critical process in the medium-deep hole or deep hole mining methods, which mainly included staged blasting or one-time grooved blasting. Cut patio was essential in the medium-deep hole mining technology. The common method, the conventional raising, cage raising and climber raising method was usually used to construct the cutting patio, which has great safety risks and low excavation efficiency, which seriously affects the mine production. In recent years, Sanshandao Gold Mine has researched downward sublevel filling mining with medium and deep hole blasting. This research was currently facing the problem of cut patio construction under the backfill roof. This study demonstrated a one-time grooved blasting method fitting the backfill roof condition and its application. By comparing the characteristics of the straight-hole cutting method and the blasting crater method, the straight-hole cutting method was selected for the cut patio construction. By calculating blasting parameters, the diameter of the charging hole was Φ65 mm, and the diameter of the compensation hole was Φ110mm. The distance between the charging and empty holes was 0.3m, which could meet the requirements of blasting compensation space and free surface. In consideration of the surrounding rock stability conditions, a nine-hole cutout method was selected, containing 29 holes, where the cutout hole was designed with 1 central charging hole, 12 empty holes as compensation holes, 4 auxiliary holes, and 12 peripheral holes, after determining the blast hole plugging length, explosive selection, charge structure, differential time, detonation sequence and other process parameters, an in-situ industrial test of cut patio construction was carried out. The industrial test showed that the one-time grooved blasting plan for patio construction was feasible. The blasting rock particle size is uniform with no large blocks and excessive powder, the blasting disturbance is minor, and the blasting patio dimensions meet the design requirements. Overall, this test provided experiences and a reference basis for other one-time grooved blasting technical applications with similar conditions. [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]

In response to the unclear impact of header vibration on cutting performance (stalk cutting quality and cutting energy consumption) during field operations of industrial hemp harvesters, this study utilized a vibration recorder to collect information on header vibration during the operation of industrial hemp harvesters. Through data processing, the dominant range for the resonant frequency and amplitude of the cutting platform is primarily concentrated between 5–45 Hz and 0–35 mm, respectively. Using numerical simulation techniques, a quadratic orthogonal rotation combination experiment was conducted with vibration frequency and amplitude as experimental factors and stalk cutting quality and cutting energy consumption as indicators. Regression equations were established to reveal the relationships between indicators and factors, elucidating the influence of each factor and its interactions on the indicators. Specifically, for the crack length indicator, the amplitude has a highly significant influence on the model, and there is a significant interaction effect between vibration frequency and amplitude on the model. As for the cutting energy consumption indicator, frequency and the interaction between frequency and amplitude significantly affect the model, while amplitude has an extremely significant impact on the model. Through comprehensive fuzzy evaluation, the optimal vibration parameter combination satisfying comprehensive cutting performance indicators was determined as a vibration frequency of 37.86 Hz and an amplitude of 5.34 mm. Furthermore, the reliability of the model has been further validated. This research can provide a reference for improving the field performance of industrial hemp harvesters. [ABSTRACT FROM AUTHOR]

Identifying shortest paths between nodes in a network is a common graph analysis problem that is important for many applications involving routing of resources. An adversary that can manipulate the graph structure could alter traffic patterns to gain some benefit (e.g., make more money by directing traffic to a toll road). This article presents the Force Path Cut problem, in which an adversary removes edges from a graph to make a particular path the shortest between its terminal nodes. We prove that the optimization version of this problem is APX-hard but introduce PATHATTACK, a polynomial-time approximation algorithm that guarantees a solution within a logarithmic factor of the optimal value. In addition, we introduce the Force Edge Cut and Force Node Cut problems, in which the adversary targets a particular edge or node, respectively, rather than an entire path. We derive a nonconvex optimization formulation for these problems and derive a heuristic algorithm that uses PATHATTACK as a subroutine. We demonstrate all of these algorithms on a diverse set of real and synthetic networks, illustrating where the proposed algorithms provide the greatest improvement over baseline methods. [ABSTRACT FROM AUTHOR]

Given a network G = (N , A , c) and an s − t cut [ S , S ̄ ] with the capacity β and the constant value α , an inverse minimum s − t cut problem with value constraint is to modify the vector capacity c as little as possible to make the s − t cut [ S , S ̄ ] become a minimum s − t cut with the capacity α. The distinctive feature of this problem with the inverse minimum cut problems is the addition of a constraint in which the capacity of the given cut has to equal to the preassumed value α. In this paper, we investigate the inverse minimum s − t cut problem with value constraint under the bottleneck weighted Hamming distance. We propose two strongly polynomial time algorithms based on a binary search to solve the problem. At each iteration of the first one, we solve a feasible flow problem. The second algorithm considers the problem in two cases β > α and β < α. In this algorithm, we first modify the capacity vector such that the given cut becomes a minimum s − t cut in the network and then, by preserving optimality this s − t cut, adjust it to satisfy value constraint. [ABSTRACT FROM AUTHOR]

The production planning problem in the Pinus radiata sawmill industry revolves around determining how to cut a set of logs of different diameters to obtain pieces with a rectangular base, typically of the same length as the original log. The primary objective is often to maximize the volumetric yield or the ratio between the total volume of the produced pieces and the available volume of the logs. Given the scarcity of timber forests, small and medium-sized (SME) sawmills must optimize their operations to maximize the volumetric yield of logs, usually procured from third parties and may vary in quality and dimensions. In this context, the absence of decision support tools directly contributes to inefficient raw material utilization, consequently impacting the business’s profit. This study introduces a multi-objective mixed-integer linear programming model incorporating log availability and product demand as input parameters. The objective functions aim to minimize the total volumetric loss of utilized logs and the surplus quantity associated with products exceeding demand. The model integrates cutting patterns pre-determined for each log diameter as an additional input. The Cutlog© software was used to identify all the optimal cutting patterns. The $\varepsilon $ -constraint method, implemented in the CPLEX© solver, was employed to solve the model. The model was validated using representative instances designed to emulate the challenges faced by SME sawmills. Real industry data, surveys, and commercial records from SME sawmills in southern Chile were utilized. The results confirm the effectiveness of the proposed model in addressing the multi-objective challenges encountered by these businesses. The model successfully identifies multiple solutions on the Pareto frontier, offering valuable insights for decision-making.