Search

The optimal tool routing for cutting machines, also known as cutting path optimisation is an important problem in production research. This problem is relevant in various manufacturing environments such as aeronautic, automotive, garment and semiconductor industries. In this paper, we introduce a general solution framework for the discrete Cutting Path Problem which includes: (i) the universal approach to reduce numerous settings of this problem to the appropriate auxiliary instances of the well-known Precedence Constrained Generalized Traveling Salesman Problem; (ii) the proposition of efficient solution methods for finding (sub-) optimal solutions. We carry out extensive computational experiments in order to evaluate performance of the proposed framework and the obtained results demonstrate its efficiency for real-life industrial instances. [ABSTRACT FROM AUTHOR]

We show a flow-augmentation algorithm in directed graphs: There exists a randomized polynomial-time algorithm that, given a directed graph G, two vertices s, t ∈ V(G), and an integer k, adds (randomly) to G a number of arcs such that for every minimal st-cut Z in G of size at most k, with probability 2−poly(k) the set Z becomes a minimumst-cut in the resulting graph. We also provide a deterministic counterpart of this procedure. The directed flow-augmentation tool allows us to prove fixed-parameter tractability of a number of problems parameterized by the cardinality of the deletion set whose parameterized complexity status was repeatedly posed as open problems: Chain SAT, defined by Chitnis, Egri, and Marx [ESA'13, Algorithmica'17], a number of weighted variants of classic directed cut problems, such as Weightedst-Cut or Weighted Directed Feedback Vertex Set. By proving that Chain SAT is FPT, we confirm a conjecture of Chitnis, Egri, and Marx that, for any graph H, if the ListH-Coloring problem is polynomial-time solvable, then the corresponding vertex-deletion problem is fixed-parameter tractable. [ABSTRACT FROM AUTHOR]

The cutting and packing problems (CPP) widely appear in various industrial fields, such as additive manufacturing (AM) and the fashion industry. The evolutionary optimization (EO) algorithms inspired by biological evolution are popular to solve such combinatorial optimization problems these years. Most of the research focused on the improvement of nesting strategies (NS) and EO algorithms, while the relationship between NSs and evolutionary optimization stages is the neglected crucial point. In this paper, a fidelity-adaptive evolution optimization (FAEO) method is proposed to speed up the optimization process by using different nesting strategies at the appropriate optimization stages. In FAEO methods, two switching methods are designed to convert NSs. The neighbourhood-elite evaluation (NEE) and staged-archive (S-A) methods are developed to accelerate individual internal assessment. The experimental results and relevant analysis of the cases from ESICUP by the combination of genetic algorithm (GA) and skyline-derived NSs prove the effectiveness, rapidity, and industrial value of the FAEO algorithm compared with the benchmark algorithms. [ABSTRACT FROM AUTHOR]

In industrial manufacturing, cutting path planning is very important since it directly affects cutting quality and efficiency. However, traditional methods are no longer suitable for large-scale and real-time cutting path planning due to the long computation time needed. Currently, though the deep learning method can be used for cutting path planning, the node number has to be fixed, and a large amount of labeled data is required. Another method is deep reinforcement learning, which can be used for cutting path planning. The node number also has to be fixed. As a result, these two potential methods are unsuitable for practical industrial cutting problems. To solve the above problem, this study provides a new reinforcement learning approach that integrates adaptive sequence adjustment and attention mechanisms. Compared to traditional methods, which took hours or days to finish a complicated cutting path plan, this approach significantly improves processing efficiency, completing tasks in seconds, and also minimizes non-cutting travel paths. And compared to deep learning and deep reinforcement learning provided by others, a variable number of nodes can be processed with this method. Therefore, it is more suitable for practical industrial cutting problems. [ABSTRACT FROM AUTHOR]

The classic cake cutting problem concerns the fair allocation of a heterogeneous resource among interested agents. In this paper, we study a public goods variant of the problem, where instead of competing with one another for the cake, the agents all share the same subset of the cake which must be chosen subject to a length constraint. We focus on the design of truthful and fair mechanisms in the presence of strategic agents who have piecewise uniform (i.e., approval) utilities over the cake. On the one hand, we show that the leximin solution is excludably truthful (meaning it is truthful when it can block each agent from accessing parts of the cake that the agent does not claim to desire) and moreover maximizes the guaranteed normalized egalitarian welfare among all excludably truthful and position oblivious mechanisms. On the other hand, we demonstrate that the maximum Nash welfare solution is excludably truthful for two agents (as it coincides with leximin in that case) but not in general. We also provide an impossibility result on truthfulness when blocking is not allowed, and adapt notions of representation to our setting. [ABSTRACT FROM AUTHOR]

For a subset T of nodes of an undirected graph G, a T-Steiner cut is a cut δ(S) with T∩S≠ø and T\S≠ø. The T-Steiner cut dominant of G is the dominant CUT+(G,T) of the convex hull of the incidence vectors of the T-Steiner cuts of G. For T={s,t} , this is the well-understood s-t-cut dominant. Choosing T as the set of all nodes of G, we obtain the cut dominant for which an outer description in the space of the original variables is still not known. We prove that for each integer τ, there is a finite set of inequalities such that for every pair (G, T) with |T|≤τ , the nontrivial facet-defining inequalities of CUT+(G,T) are the inequalities that can be obtained via iterated applications of two simple operations, starting from that set. In particular, the absolute values of the coefficients and of the right-hand sides in a description of CUT+(G,T) by integral inequalities can be bounded from above by a function of |T|. For all |T|≤5 , we provide descriptions of CUT+(G,T) by facet-defining inequalities, extending the known descriptions of s-t-cut dominants. [ABSTRACT FROM AUTHOR]

Industrial engineering and operations management have been two of the most studied fields by operational research practitioners in recent decades owing to their theoretical and practical significance. Although several surveys have addressed various problems in this field, to the best of the author's knowledge, no survey has been dedicated to analysing the evolution of optimization studies over the past decades. On the 50th anniversary of the launch of the journal Engineering Optimization (GENO), all contributions published in this domain are evaluated. All documents published in GENO since its inception in 1974 are analysed, and 402 articles are selected. The most prolific areas in this field are production scheduling, production planning and control, transportation and logistics, routing, and cutting and packing problems. The main emerging trends include integrated production and distribution problems, the application of constraint programming methods, the incorporation of sustainable objective functions, and the use of machine learning combined with metaheuristics. [ABSTRACT FROM AUTHOR]

The Cutting Stock Problem (CSP) is an optimization challenge that involves dividing large objects into smaller components while considering various managerial objectives. The problem's complexity can differ based on factors such as object dimensionality, the number of cutting stages required, and any technological constraints. The demand for coils of varying sizes and quantities necessitates intermediate splitting and slitting stages to produce the finished rolls. Additionally, relationships between orders are affected by dimensional variations at each stage of processing. This specific variant of the problem is known as the One-and-a-Half Dimensional Two-Stage Cutting Stock Problem (1.5-D TSCSP). To address the 1.5-D TSCSP, two algorithmic approaches were developed: the Generate-and-Solve (G&S) method and a hybrid Row-and-Column Generation (R&CG) approach. Both aim to minimize total trim loss while navigating the complexities of the problem. Inspired by existing problems in the literature for simpler versions of the problem, a set of randomly generated test cases was prepared, as detailed in this paper. An implementation of the two approaches was used to obtain solutions for the generated test campaign. The simpler G&S approach demonstrated superior performance in solving smaller instances of the problem, while the R&CG approach exhibited greater efficiency and provided superior solutions for larger instances. [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]

It was conjectured by Gupta et al. that every planar graph can be embedded into \(\ell_{1}\) with constant distortion. However, given an \(n\) -vertex weighted planar graph, the best upper bound on the distortion is only \(O(\sqrt{\log n})\) , by Rao. In this article, we study the case where there is a set \(K\) of terminals, and the goal is to embed only the terminals into \(\ell_{1}\) with low distortion. In a seminal article, Okamura and Seymour showed that if all the terminals lie on a single face, they can be embedded isometrically into \(\ell_{1}\). The more general case, where the set of terminals can be covered by \(\gamma\) faces, was studied by Lee and Sidiropoulos and Chekuri et al. The state of the art is an upper bound of \(O(\log\gamma)\) by Krauthgamer, Lee and Rika. Our contribution is a further improvement on the upper bound to \(O(\sqrt{\log\gamma})\). Since every planar graph has at most \(O(n)\) faces, any further improvement on this result will be a major breakthrough, directly improving upon Rao's long standing upper bound. Moreover, it is well known that the flow-cut gap equals to the distortion of the best embedding into \(\ell_{1}\). Therefore, our result provides a polynomial time \(O(\sqrt{\log\gamma})\) -approximation to the sparsest cut problem on planar graphs, for the case where all the demand pairs can be covered by \(\gamma\) faces. [ABSTRACT FROM AUTHOR]

This paper details an investigation of the process of multi-axis high-speed milling of the surface of Ni-based superalloy Inconel 718 parts used the torus milling cutter. Presents the issues and development of the own models of the multi-axis milling in a kinematic variant of the TPl (Tool Pulling) type in terms of tool wear. Because the cutting speed in finishing high-speed milling is the parameter with the greatest influence on tool life and surface roughness, the dependence of the variation of the cutting speed at the torus part of the cutter was first determined as a function of the distance from the tip point along the axial direction and the geometrical parameters of the torus. A model for multi-axis milling of the TPl type was developed and described in a simplified manner, which forms the basis of an own ACACES strategy for segmenting the cutting edge of a torus milling cutter. The adaptation of a given segment to the active cutting edge during machining was based on tool wear and kinematic roughness criteria. Simulations and experiments of multi-axis milling were carried out, and the necessary analyses were performed. In this paper, in addition to testing an in-house strategy for multi-axis milling used the torus milling cutter, the problem of defining the cutting speed in relation to the nominal diameter and effective diameter of the tool is investigated for the first time. In addition, wear measurement was carried out using an in-house methodology, taking full advantage of the capabilities of the multi-axis machining centre, which significantly reduced measurement time and positively influenced the effectiveness of tool life assessment. Using the own ACACES strategy of the multi-axis surface milling of parts made of Ni-based superalloys, an almost fourfold increase in torus cutter life was achieved compared to the conventional strategy, while maintaining the required machined surface roughness parameters. • A novel strategy of adaptive change of the active cutting edge segment is presented. • The CWE is analyzed, revealing the uneven wear characteristics in multi-axis milling processes. • The wear is analyzed, revealing the uneven surface topography characteristics. • The ACACES strategy increases the torus milling cutter life. [ABSTRACT FROM AUTHOR]