Search

Fractional variants of distance-based parameters have application in the fields of sensor networking, robot navigation, and integer programming problems. Complex networks are exceptional networks which exhibit significant topological features and have become quintessential research area in the field of computer science, biology, and mathematics. Owing to the possibility that many real-world systems can be intelligently modeled and represented as complex networks to examine, administer and comprehend the useful information from these real-world networks. In this paper, local fractional strong metric dimension of certain complex networks is computed. Building blocks of complex networks are considered as the symmetric networks such as cyclic networks C n , circulant networks C n 1,2 , mobious ladder networks M 2 n , and generalized prism networks G m n . In this regard, it is shown that LSFMD of C n n ≥ 3 and G m n n ≥ 6 is 1 when n is even and n / n − 1 when n is odd, whereas LSFMD of M 2 n is 1 when n is odd and n / n − 1 when n is even. Also, LSFMD of C n 1,2 is n / 2 ⌈ m + 1 / 2 ⌉ where n ≥ 6 and m = ⌈ n − 5 / 4 ⌉. [ABSTRACT FROM AUTHOR]

The metric dimension has various applications in several fields, such as computer science, image processing, pattern recognition, integer programming problems, drug discovery, and the production of various chemical compounds. The lowest number of vertices in a set with the condition that any vertex can be uniquely identified by the list of distances from other vertices in the set is the metric dimension of a graph. A resolving function of the graph G is a map ϑ : V (G) → [ 0 , 1 ] such that ∑ u ∈ R { v , w } ϑ (u) ≥ 1 , for every pair of adjacent distinct vertices v , w ∈ V (G) . The local fractional metric dimension of the graph G is defined as ldim f (G) = min { ∑ v ∈ V (G) ϑ (v) , where ϑ is a local resolving function of G } . This paper presents a new family of planar networks namely, rotationally heptagonal symmetrical graphs by means of up to four cords in the heptagonal structure, and then find their upper-bound sequences for the local fractional metric dimension. Moreover, the comparison of the upper-bound sequence for the local fractional metric dimension is elaborated both numerically and graphically. Furthermore, the asymptotic behavior of the investigated sequences for the local fractional metric dimension is addressed. [ABSTRACT FROM AUTHOR]

The Double Row Layout Problem (DRLP) is the problem of allocating a given set of machines on both sides of a straight line corridor so as to minimise the total cost of transporting materials among machines. The DRLP occurs in several manufacturing plants, particularly in semiconductor manufacturing. While it has a large practical importance, the problem is very difficult to solve to optimality. In this paper, we construct a mixed-integer programming (MIP) formulation of the problem, which favourably compares to a previously published MIP formulation. The new model is found to present similar performance to another published MIP formulation, and it has the advantage of being more intuitive for handling qualitative inputs that may be required in a layout refinement phase. [ABSTRACT FROM AUTHOR]

Metric dimension is one of the distance based graph - theoretic parameters which is widely used in the various disciplines of sciences such as computer science, chemistry, and engineering. The local fractional metric dimension is latest derived form of metric dimension and it is used to find the solutions of integer programming problems. In this paper, we have computed local fractional metric dimension of different families of Toeplitz networks. It is also proved that the local fractional metric dimension of these Toeplitz networks remain bounded when the order of the networks approaches to infinity. [ABSTRACT FROM AUTHOR]

With the rapid growth of the Web scale, large scale search engines have to set up a huge number of machines to place the index files of the Web contents. The index files are normally divided into smaller index shards which are often replicated so that queries can be processed in parallel. We observe from real systems that the index shard replication strategy could have a significant impact on the resource usage. In this paper, we investigate the index shard replication problem with the goal of minimizing the resource usage in search engine datacenters. We consider both the offline version and online version of the problem, and formulate the problems as non-linear integer programming problems. We propose several heuristic algorithms to approximate the optimal solution. The proposed algorithms are evaluated by extensive experiments using both synthetic data and real data from commercial search engines. The results demonstrate the effectiveness of the proposed algorithms. Our work also yields many insights about the impact of different input properties on the performance of each algorithm. We believe that this paper will provide valuable guidance to the design of the index shard replication strategy in practice. [ABSTRACT FROM AUTHOR]

For a string w ∈ {0,1, 2,..., d-1}*, let vald(w) denote the integer whose base d representation is the string w and let MSDd(x) denote the most significant or the leading digit of a positive integer x when x is written as a base d integer. Hirvensalo and Karhumäki [9] studied the problem of computing the leading digit in the ternary representation of 2x ans showed that this problem has a polynomial time algorithm. In [16], some applications are presented for the problem of computing the leading digit of AB for given inputs A and B. In this paper, we study this problem from a formal language point of view. Formally, we consider the language Lb,d,j = {w|w ∈ {0,1, 2,..., d-1}*, 1 ≤ j ≤ 9, MSDb(dvalb(w))) = j} (and some related classes of languages) and address the question of whether this and some related languages are context-free. Standard pumping lemma proofs seem to be very difficult for these languages. We present a unified and simple combinatorial technique that shows that these languages are not unambiguous context-free languages. The Benford-Newcomb distribution plays a central role in our proofs. [ABSTRACT FROM AUTHOR]

Data availability is one of the most important performance factors in cloud storage systems. To enhance data availability, replication is a common approach to handle the machine failures. However, previously proposed replication schemes cannot effectively handle both correlated and non-correlated machine failures, especially while increasing the data availability with limited resources. The schemes for correlated machine failures must create a constant number of replicas for each data object, which often neglects diverse data popularities and does not utilize the resource to maximize the expected data availability. Also, the previous schemes neglect the consistency maintenance cost and the storage cost caused by replication. It is critical for cloud providers to maximize data availability (hence minimize SLA violations) while minimizing costs caused by replication in order to maximize the revenue. In this paper, we build a nonlinear integer programming model to maximize data availability in both types of failures, and therefore minimize the cost caused by replication. Based on the model’s solution for the replication degree of each data object, we propose a low-cost multi-failure (correlated and non-correlated machine failures) resilient replication scheme (MRR). MRR can effectively handle both correlated and non-correlated machine failures, considers data popularities to enhance data availability, and also tries to minimize consistency maintenance and storage cost. Extensive numerical results from trace parameters and experiments from real-world Amazon S3 demonstrate that MRR achieves high data availability, low data loss probability and low consistency maintenance and storage costs when compared to previous replication schemes. [ABSTRACT FROM AUTHOR]

This document is a special issue of Mathematical Programming, Series B (MPB) that focuses on integer programming and combinatorial optimization. It contains 23 high-quality articles that were previously presented at the 23rd Conference on Integer Programming and Combinatorial Optimization (IPCO) in 2022. The IPCO conference is held annually and provides a platform for researchers and practitioners to share developments in theory, computation, and applications in these areas. The papers in this special issue underwent a rigorous refereeing process and represent the best of the field. The document also acknowledges the authors, referees, and the Editor-in-Chief of MPB for their contributions. [Extracted from the article]

When genetic algorithms are applied to large-scale optimization problems taking only integer-valued solutions, too often the chromosomes generated faily to satisfy the constraint conditions. In such cases, the selection operator is unable to produce high-quality chromosomes, worsening the search efficiency. As a consequence, many times good solutions cannot be obtained. In this paper, in order to cope with such a problem, a new algorithm with improved chromosome selection mechanism is proposed, taking into account the evaluation function including some information about chromosomes not contained in the feasible region of the nonlinear integer programming problem under consideration. The proposed method considers how far each unfeasible chromosome is from the feasible region. The improved algorithm was applied to a large-scale problem of optimal design of system realibility formulated as a nonlinear integer programming problem and numerical experiments confirmed the effectiveness of the method. [ABSTRACT FROM AUTHOR]

Network virtualization allows multiple heterogeneous virtual networks (VNs) to coexist on a shared infrastructure. Efficient mapping of virtual nodes and virtual links of a VN request onto substrate network resources, also known as the VN embedding problem, is the first step toward enabling such multiplicity. Since this problem is known to be \cal NP-hard, previous research focused on designing heuristic-based algorithms that had clear separation between the node mapping and the link mapping phases. In this paper, we present ViNEYard—a collection of VN embedding algorithms that leverage better coordination between the two phases. We formulate the VN embedding problem as a mixed integer program through substrate network augmentation. We then relax the integer constraints to obtain a linear program and devise two online VN embedding algorithms D-ViNE and R-ViNE using deterministic and randomized rounding techniques, respectively. We also present a generalized window-based VN embedding algorithm (WiNE) to evaluate the effect of lookahead on VN embedding. Our simulation experiments on a large mix of VN requests show that the proposed algorithms increase the acceptance ratio and the revenue while decreasing the cost incurred by the substrate network in the long run. [ABSTRACT FROM PUBLISHER]

This paper compares the System Performance Evaluation Cooperative (SPEC) Integer and Floating-Point suites to a set of real-world applications for high-performance computing at Sandia National Laboratories. These applications focus on the high-end scientific and engineering domains; however, the techniques presented in this paper are applicable to any application domain. The applications are compared in terms of three memory properties: 1) temporal locality (or reuse overtime), 2) spatial locality (or the use of data ‘near’ data that has already been accessed), and 3) data intensiveness (or the number of unique bytes the application accesses). The results show that real-world applications exhibit significantly less spatial locality, often exhibit less temporal locality, and have much larger data sets than the SPEC benchmark suite. They further quantitatively demonstrate the memory properties of real supercomputing applications. [ABSTRACT FROM AUTHOR]

Metric dimension is one of the distance-based parameter which is frequently used to study the structural and chemical properties of the different networks in the various fields of computer science and chemistry such as image processing, pattern recognition, navigation, integer programming, optimal transportation models, and drugs discovery. In particular, it is used to find the locations of robots with respect to shortest distance among the destinations, minimum consumption of time, and lesser number of the utilized nodes and to characterize the chemical compounds having unique presentation in molecular networks. The fractional metric dimension being a latest developed weighted version of the metric dimension is used in the distance-related problems of the aforementioned fields to find their nonintegral optimal solutions. In this paper, we have formulated the local resolving neighborhoods with their cardinalities for all the edges of the convex polytopes networks to compute their local fractional metric dimensions in the form of exact values and sharp bounds. Moreover, the boundedness of all the obtained results is also proved. [ABSTRACT FROM AUTHOR]

The different distance-based parameters are used to study the problems in various fields of computer science and chemistry such as pattern recognition, image processing, integer programming, navigation, drug discovery, and formation of different chemical compounds. In particular, distance among the nodes (vertices) of the networks plays a supreme role to study structural properties of networks such as connectivity, robustness, completeness, complexity, and clustering. Metric dimension is used to find the locations of machines with respect to minimum utilization of time, lesser number of the utilized nodes as places of the objects, and shortest distance among destinations. In this paper, lower bound of local fractional metric dimension for the connected networks is improved from unity and expressed in terms of ratio obtained by the cardinalities of the under-study network and the local resolving neighbourhood with maximum order for some edges of network. In the same context, the LFMDs of prism-related networks such as circular diagonal ladder, antiprism, triangular winged prism, and sun flower networks are computed with the help of obtained criteria. At the end, the bounded- and unboundedness of the obtained results is also shown numerically. [ABSTRACT FROM AUTHOR]

The networking-oblivious resource reservation model in today's public clouds cannot guarantee the performance of tenants' applications. Virtual networks that capture both computing and networking resource requirements of tenants have been proposed as better interfaces between cloud providers and tenants. In this paper, we propose a novel virtual network model that could specify not only absolute and relative location requirements but also time-varying resource demands. Building on top of our model, we study how to efficiently and flexibly place multiple virtual networks in a cloud, and we propose two algorithms, MIPA and SAPA, which focus on optimizing resource utilization and providing flexible placement, respectively. The mixed integer programming based MIPA transforms the placement problem into the multi-commodity flow problem through augmenting the physical network with shadow nodes and links. The simulated annealing-based SAPA achieves resource utilization efficiency through opportunistically sharing physical resources among multiple resource demands. Besides, SAPA allows cloud providers to control the trade-offs between performance guarantee and resource utilization, and between allocation optimality and running time, and allows tenants to control the trade-off between application performance and placement cost. Extensive simulation results confirm the efficiency of MIPA in resource utilization and the flexibility of SAPA in controlling trade-offs. [ABSTRACT FROM AUTHOR]

In rail-based intermodal freight operations, full containers are moved by truck from shipper locations to rail ramps, transported via train to destination ramps, and then moved again by truck to consignee locations. We commonly refer to the roadway portions of this activity as dray operations. In a large metropolitan hub area, such as Chicago or Los Angeles, this drayage activity may involve several hundred drivers and up to 500 daily container moves to or from several distinct rail ramps. Both cost and environmental considerations drive the need to maximize driver productivity and minimize the time and miles not directly associated with moving loaded containers to or from rail ramps. In this paper, we describe a solution to this problem using a set-partitioning formulation and column-generation heuristic and report on a large-scale implementation. We focus on real-world implementation details that include (1) fast solve times to support near-real-time re-solving in the face of constantly changing data, (2) adjustments to account for traffic congestion and other operational considerations, and (3) integration with a commercial transportation management system to provide real-time data to the optimizer and to send solution recommendations to a driver-assignment process. [ABSTRACT FROM AUTHOR]

Identification of communities in complex networks is an important topic and issue in many fields such as sociology, biology, and computer science. Communities are often defined as groups of related nodes or links that correspond to functional subunits in the corresponding complex systems. While most conventional approaches have focused on discovering communities of nodes, some recent studies start partitioning links to find overlapping communities straightforwardly. In this paper, we propose a new quantity function for link community identification in complex networks. Based on this quantity function we formulate the link community partition problem into an integer programming model which allows us to partition a complex network into overlapping communities. We further propose a genetic algorithm for link community detection which can partition a network into overlapping communities without knowing the number of communities. We test our model and algorithm on both artificial networks and real-world networks. The results demonstrate that the model and algorithm are efficient in detecting overlapping community structure in complex networks. [ABSTRACT FROM AUTHOR]

Multi-dimensional arrays with linear subscripts occur quite frequently in real programs. For multi-dimensional linear arrays under variable bounds as well as any given direction vectors, the generalized Lambda test is an efficient and precise data dependence method to check whether there exist real-valued solutions. In this paper, we propose a multi-dimensional generalized interval test—a polynomial-time dependence test that can be applied towards testing whether there are integer-valued solutions for multi-dimensional linear arrays under variable limits and any given direction vectors. Experimental results with benchmark showing the effects of the multi-dimensional generalized interval test over the generalized Lambda test are also presented. [ABSTRACT FROM AUTHOR]

This paper considers a lattice represented by integer coordinates in n-dimensional space (digital lattice). On the digital lattice, and automorphism is constructed by a newly proposed theory and algorithm, to enable the approximation of the arbitrarily given equivolume affine transformation. The equivolume affine transformation is a general affine transformation that satisfies the condition of volume invariance, and is characterized by the determinant of the representation matrix having an absolute value of 1. An equivolume affine transformation of reflection, rotation, equivolume expansion/contraction and skew deformation. These transformations often are employed as fundamental transformations in the handling of geometrical information in computers. This paper discusses first the geometrical characters of equivolume affine transformations. It then defines the fundamental reflection, skew and translations. It is shown that the equivolume affine transformations in n-dimensional space can be decomposed into the produce of (n²-1) fundamental skew transformations, n fundamental translations and a finite number of fundamental reflections. For the fundamental transformations, one-to-one integer approximation is defined, and a systematic method is proposed to evaluate the upper bound of the approximation error. With the proposed error estimation method, an algorithm is proposed to determine the decomposition suppressing the error in the overall system. One advantage of this theory is that it is no longer necessary to preserve the geometrical information before transformation in the computer, which has been commonplace up to now in computer programming. [ABSTRACT FROM AUTHOR]

Rank data, in which each row is a complete or partial ranking of available items (columns), is ubiquitous. Among others, it can be used to represent preferences of users, levels of gene expression, and outcomes of sports events. It can have many types of patterns, among which consistent rankings of a subset of the items in multiple rows, and multiple rows that rank the same subset of the items highly. In this article, we show that the problems of finding such patterns can be formulated within a single generic framework that is based on the concept of semiring matrix factorization. In this framework, we employ the max-product semiring rather than the plus-product semiring common in traditional linear algebra. We apply this semiring matrix factorization framework on two tasks: sparse rank matrix factorization and rank matrix tiling. Experiments on both synthetic and real world datasets show that the framework is capable of discovering different types of structure as well as obtaining high quality solutions. [ABSTRACT FROM PUBLISHER]

The concept of metric dimension is widely applied to solve various problems in the different fields of computer science and chemistry, such as computer networking, integer programming, robot navigation, and the formation of chemical structuring. In this article, the local fractional metric dimension (LFMD) of the cycle-based Sierpinski networks is computed with the help of its local resolving neighborhoods of all the adjacent pairs of vertices. In addition, the boundedness of LFMD is also examined as the order of the Sierpinski networks approaches infinity. [ABSTRACT FROM AUTHOR]

Abstract: This paper performs a comparison of several methods for Kemeny rank aggregation (104 algorithms and combinations thereof in total) originating in social choice theory, machine learning, and theoretical computer science, with the goal of establishing the best trade-offs between search time and performance. We find that, for this theoretically NP-hard task, in practice the problems span three regimes: strong consensus, weak consensus, and no consensus. We make specific recommendations for each, and propose a computationally fast test to distinguish between the regimes. In spite of the great variety of algorithms, there are few classes that are consistently Pareto optimal. In the most interesting regime, the integer program exact formulation, local search algorithms and the approximate version of a theoretically exact branch and bound algorithm arise as strong contenders. [Copyright &y& Elsevier]

Abstract: We introduce the vertex cover () problem, that is, the problem of finding a minimum weight set such that the graph has no , where is a path with vertices. The problem also has its application background. In this paper, we first show that the problem is NP-hard for any integer . Then we restrict our attention to the problem and give a 2-approximation algorithm using the primal–dual method. [Copyright &y& Elsevier]

Abstract: The parameterized pattern matching problem is to check if there exists a renaming bijection on the alphabet with which a given pattern can be transformed into a substring of a given text. A parameterized border array (p-border array) is a parameterized version of a standard border array, and we can efficiently solve the parameterized pattern matching problem using p-border arrays. In this paper, we present a linear time algorithm to verify if a given integer array is a valid p-border array for a binary alphabet. We also show a linear time algorithm to compute all binary parameterized strings sharing a given p-border array. In addition, we give an algorithm which computes all p-border arrays of length at most , where is a given threshold. This algorithm runs in time, where is the number of all p-border arrays of length for a binary parameter alphabet. The problems with a larger alphabet are much more difficult. Still, we present an –time –space algorithm to verify if a given integer array of length is a valid p-border array for an unbounded alphabet. The best previously known solution to this task takes time proportional to the -th Bell number , and hence our algorithm is much more efficient. Also, we show that it is possible to enumerate all p-border arrays of length at most for an unbounded alphabet in time, where denotes the number of p-border arrays of length . [Copyright &y& Elsevier]

Abstract: Let be a connected graph with vertices. Let be an integer. Suppose that a fire breaks out at a vertex of . A firefighter starts to protect vertices. At each time interval, the firefighter protects -vertices not yet on fire. At the end of each time interval, the fire spreads to all the unprotected vertices that have a neighbour on fire. Let sn denote the maximum number of vertices in that the firefighter can save when a fire breaks out at vertex . The -surviving rate of is defined to be , which is the average proportion of saved vertices. In this paper, we investigate the surviving rate of outerplanar graphs with vertices. The main results are as follows: (1) ; and (2) if , and if , which improves the result in [L.Cai, W.Wang, The surviving rate of a graph for the firefighter problem, SIAM J. Discrete Math. 23 (2009) 1814–1826]. [ABSTRACT FROM AUTHOR]

Abstract: Let be a graph without isolated vertices. For a positive integer , a set is a -distance paired-dominating set if each vertex in is within distance of a vertex in and the subgraph induced by contains a perfect matching. In this paper, we present two linear time algorithms to find a minimum cardinality -distance paired-dominating set in interval graphs and block graphs, which are two subclasses of chordal graphs. In addition, we present a characterization of trees with unique minimum -distance paired-dominating set. [Copyright &y& Elsevier]

This study discusses and compares grid proximity measures that use representative data points in grid cells and the average distance between the data points in grid cells. Basic theorems for the grid distance measure are formulated and proved. The grid distance measure is applied to the grid-based clustering problem where the number of clusters is dynamically determined by using a threshold value and by maximizing intra-similarity in a cluster and inter-dissimilarity between the clusters. In this study, the grid-based clustering problem is illustrated and formulated using a 0-1 integer programming approach. We perform numerical experiments on randomly generated problems and also for a clustering problem concerning microarray data of human fibroblasts in varying serum concentrations, with the latter data having been taken from a prior study. The theorems are applicable to the grid-based clustering of any data set. [ABSTRACT FROM AUTHOR]

Karchmer, Kushilevitz and Nisan formulated the formula size problem as an integer programming problem called the rectangle bound and introduced a technique called the LP bound, which gives a formula size lower bound by showing a feasible solution of the dual problem of its LP-relaxation. As extensions of the LP bound, we introduce novel general techniques proving formula size lower bounds, named a quasi-additive bound and the Sherali-Adams bound. While the Sherali-Adams bound is potentially strong enough to give a lower bound matching to the rectangle bound, we prove that the quasi-additive bound can surpass the rectangle bound. We also reveal that the quasi-additive bound is potentially strong enough to prove the matching formula size lower bound. [ABSTRACT FROM AUTHOR]

The goal of the COIN-OR Foundation is to serve the operations research community by providing both software and the necessary infrastructure to foster the development and deployment of cutting-edge computational operations research. Many people in the operations research community are either not familiar with just how much COIN-OR can benefit them, or do not know how to obtain and use COIN-OR software. In this tutorial, we first show how COIN-OR software can be applied in the workplace, in the classroom, and in research. We then show how to obtain and use COIN-OR software. We consider two classes of users: those who want to use the COIN-OR software but are not interested in compiling code and those who wish to write code that uses this software as a foundation for their applications. [ABSTRACT FROM AUTHOR]

We design a fully polynomial-time approximation scheme (FPTAS) for a single machine scheduling problem to minimize the total weighted earliness and tardiness with respect to a common restrictive due date. Notice that for this problem no constant-ratio approximation algorithm has been known so far. Our approach is based on adopting an FPTAS for a special version of the knapsack problem to minimize a convex quadratic non-separable function. For the continuous relaxation of such a knapsack problem we give an algorithm of a quadratic time complexity. The running time of the resulting FPTAS is strongly polynomial. [ABSTRACT FROM AUTHOR]

Abstract  We describe a weak quantifier elimination procedure for the full linear theory of the integers. This theory is a generalization of Presburger arithmetic, where the coefficients are arbitrary polynomials in non-quantified variables. The notion of weak quantifier elimination refers to the fact that the result possibly contains bounded quantifiers. For fixed choices of parameters these bounded quantifiers can be expanded into disjunctions or conjunctions. We furthermore give a corresponding extended quantifier elimination procedure, which delivers besides quantifier-free equivalents also sample values for quantified variables. Our methods are efficiently implemented within the computer logic system redlog, which is part of reduce. Various examples demonstrate the applicability of our methods. These examples include problems currently discussed in practical computer science. [ABSTRACT FROM AUTHOR]

Given is a sequence of n positive integers w1,w2,…,wn that are associated with the items 1, 2,… , n, respectively. In the windows scheduling problem, the goal is to schedule all the items (equal-length information pages) on broadcasting channels such that the gap between two consecutive appearances of page i on any of the channels is at most wi slots (a slot is the transmission time of one page). In the unit-fractions bin packing problem, the goal is to pack all the items in bins of unit size where the size (width) of item i is 1/wi . The optimization objective is to minimize the number of channels or bins. In the offline setting, the sequence is known in advance, whereas in the online setting, the items arrive in order and assignment decisions are irrevocable. Since a page requires at least 1/wi of a channel's bandwidth, it follows that windows scheduling without migration (i.e., all broadcasts of a page must be from the same channel) is a restricted version of unit-fractions bin packing. Let H = ⌈Σin=1(1/wi) ⌉ be the bandwidth lower bound on the required number of bins (channels). The best-known offline algorithm for the windows scheduling problem used H + O(ln H) channels. This article presents an offline algorithm for the unit-fractions bin packing problem with at most H +1 bins. In the online setting, this article presents algorithms for both problems with H + O(√H) channels or bins, where the one for the unit-fractions bin packing problem is simpler. On the other hand, this article shows that already for the unit-fractions bin packing problem, any online algorithm must use at least H+Ω(ln H) bins. For instances in which the window sizes form a divisible sequence, an optimal online algorithm is presented. Finally, this article includes a new NP-hardness proof for the windows scheduling problem. [ABSTRACT FROM AUTHOR]

Planning problems are crucial for providing an efficient use of a flexible manufacturing system (FMS). These include the decisions that have to be taken before the system starts to operate. This study entails joint operation of part selection, operation assignment and tool magazine configuration, which are among the planning problems, and develops a joint mixed integer programming model. Unfortunately, the combinatorial structure of the problem makes the solution difficult and time-consuming for real-world size problems by using the proposed model. Therefore, simulated annealing and tabu search algorithms are developed to solve the problem. The performance of the algorithms is tested on the random-generated problems with different sizes. The tabu search algorithm with long-term memory is found to be the most effective in respect of solution quality. [ABSTRACT FROM AUTHOR]

The knapsack problem and the minimum spanning tree problem are both fundamental in operations research and computer science. We are concerned with a combination of these two problems. That is, we are given a knapsack of a fixed capacity, as well as an undirected graph where each edge is associated with profit and weight. The problem is to fill the knapsack with a feasible spanning tree such that the tree profit is maximized. We prove this problem 𝒩𝒫-hard, present upper and lower bounds, develop a branch-and-bound algorithm to solve the problem to optimality and propose a shooting method to accelerate computation. We evaluate the developed algorithm through a series of numerical experiments for various types of test problems. [ABSTRACT FROM AUTHOR]

Examines the problem of performing the buffering of global multiterminal nets given an existing buffer block plan. Features of integer linear program formulations for the basic global routing via buffer blocks (GRBB) problem; Details of a subroutine of the algorithm for finding minimum weight feasible Steiner trees; Presentation of algorithms for optimal integral solutions; Implementations of several GRBB heuristics.

A positive integer code Fh,m,b(h&ges;3,m&ges;2,b&ges;3) is proposed. It codes recursive length information with two types of code. One codes repeatedly m length information each value of which is equal to or more than 2h&minus1. The end of codeword is expressed in b bits. The other codes length information each value of which is less than 2h&minus1. The codeword length of Fh,m,b(n) is not more than log*n+C1w*(n)+C2, where log*=log2n+log2log2n+log2log2log2n+⃛, w*(n) is the number of zero or positive terms of log*n, and C1,C2 are constants that depend on h, m, b. C1 is expressed as -log2log2e1<-logloge+2.0374/2h+(logloge-log(1-2403/(404ċ2b)))/m&les; -log2 log2e+2.0374/2h+2.4918/m. If C1 < 0, C2 is expressed as C2 < (w*(h-2)+m+ 1)log2log2e+b+2.5186. © 2001 Scripta Technica, Electron Comm Jpn Pt 3, 84(8): 46–56, 2001 [ABSTRACT FROM AUTHOR]

Integer Linear Programming (ILP) is among the most successful and general paradigms for solving computationally intractable optimization problems in computer science. ILP is NP-complete, and until recently we have lacked a systematic study of the complexity of ILP through the lens of variable-constraint interactions. This changed drastically in recent years thanks to a series of results that together lay out a detailed complexity landscape for the problem centered around the structure of graphical representations of instances. The aim of this survey is to summarize these recent developments, put them into context and a unified format, and make them more approachable for experts from many diverse backgrounds. [ABSTRACT FROM AUTHOR]