An intensive line of research on fixed parameter tractability of integer programming is focused on exploiting the relation between the sparsity of a constraint matrix A and the norm of the elements of its Graver basis. In particular, integer programming is fixed parameter tractable when parameterized by the primal tree-depth and the entry complexity of A, and when parameterized by the dual tree-depth and the entry complexity of A; both these parameterization imply that A is sparse, in particular, the number of its non-zero entries is linear in the number of columns or rows, respectively. We study preconditioners transforming a given matrix to a row-equivalent sparse matrix if it exists and provide structural results characterizing the existence of a sparse row-equivalent matrix in terms of the structural properties of the associated column matroid. In particular, our results imply that the ℓ 1 -norm of the Graver basis is bounded by a function of the maximum ℓ 1 -norm of a circuit of A. We use our results to design a parameterized algorithm that constructs a matrix row-equivalent to an input matrix A that has small primal/dual tree-depth and entry complexity if such a row-equivalent matrix exists. Our results yield parameterized algorithms for integer programming when parameterized by the ℓ 1 -norm of the Graver basis of the constraint matrix, when parameterized by the ℓ 1 -norm of the circuits of the constraint matrix, when parameterized by the smallest primal tree-depth and entry complexity of a matrix row-equivalent to the constraint matrix, and when parameterized by the smallest dual tree-depth and entry complexity of a matrix row-equivalent to the constraint matrix.

• Keywords
• Fixed parameter tractability, Graver basis, Integer programming, Matroids, Tree-depth, Width parameters,
• Publication type
• Journal Article MeSH

Wang tiles enable efficient pattern compression while avoiding the periodicity in tile distribution via programmable matching rules. However, most research in Wang tilings has considered tiling the infinite plane. Motivated by emerging applications in materials engineering, we consider the bounded version of the tiling problem and offer four integer programming formulations to construct valid or nearly-valid Wang tilings: a decision, maximum-rectangular tiling, maximum cover, and maximum adjacency constraint satisfaction formulations. To facilitate a finer control over the resulting tilings, we extend these programs with tile-based, color-based, packing, and variable-sized periodic constraints. Furthermore, we introduce an efficient heuristic algorithm for the maximum-cover variant based on the shortest path search in directed acyclic graphs and derive simple modifications to provide a 1/2 approximation guarantee for arbitrary tile sets, and a 2/3 guarantee for tile sets with cyclic transducers. Finally, we benchmark the performance of the integer programming formulations and of the heuristic algorithms showing that the heuristics provide very competitive outputs in a fraction of time. As a by-product, we reveal errors in two well-known aperiodic tile sets: the Knuth tile set contains a tile unusable in two-way infinite tilings, and the Lagae corner tile set is not aperiodic.

• Publication type
• Journal Article MeSH

Fragmentation of the forests affects forest ecosystems by changing the composition, shape, and configuration of the resulting patches. Subsequently, the prevailing conditions vary between patches. The exposure to the sun decreases from the patch boundary to the patch interior and this forms core and edge areas within each patch. Forest harvesting and, in particular, the clear-cut management system which is still preferred in many European countries has a significant impact on forest fragmentation. There are many indices of measuring fragmentation: non-spatial and spatial. The non-spatial indices measure the composition of patches, while the spatial indices measure both the shape and configuration of the resulting patches. The effect of forest harvesting on fragmentation, biodiversity, and the environment is extensively studied; however, the integration of fragmentation indices in the harvest scheduling model is a new, novel approach. This paper presents a multi-objective integer model of harvest scheduling for clear-cut management system and presents a case study demonstrating its use. Harvest balance and sustainability are ensured by the addition of constraints from the basic principle of the regulated forest model. The results indicate that harvest balance and sustainability can be also achieved in minimizing fragmentation of forest ecosystems. From the analyses presented in this study, it can be concluded that integration of fragmentation into harvest scheduling can provide better spatial structure. It depends on the initial spatial and age structure. It was confirmed that it is possible to find compromise solution while minimizing fragmentation and maximizing harvested area.

• Keywords
• Ecological intensification, Forest management, Multi-objective integer programming, Optimization, Spatial indices,
• MeSH
• Biodiversity MeSH
• Forestry methods   MeSH
• Forests * MeSH
• Picea growth & development   MeSH
• Models, Theoretical * MeSH
• Conservation of Natural Resources * MeSH
• Publication type
• Journal Article MeSH
• Research Support, Non-U.S. Gov't MeSH

Due to the outbreak of the COVID-19 pandemic, the manufacturing sector has been experiencing unprecedented issues, including severe fluctuation in demand, restrictions on the availability and utilization of the workforce, and governmental regulations. Adopting conventional manufacturing practices and planning approaches under such circumstances cannot be effective and may jeopardize workers' health and satisfaction, as well as the continuity of businesses. Reconfigurable Manufacturing System (RMS) as a new manufacturing paradigm has demonstrated a promising performance when facing abrupt market or system changes. This paper investigates a joint workforce planning and production scheduling problem during the COVID-19 pandemic by leveraging the adaptability and flexibility of an RMS. In this regard, workers' COVID-19 health risk arising from their allocation, and workers' preferences for flexible working hours are incorporated into the problem. Accordingly, first, novel Mixed-Integer Linear Programming (MILP) and Constraint Programming (CP) models are developed to formulate the problem. Next, exploiting the problem's intrinsic characteristics, two properties of an optimal solution are identified. By incorporating these properties, the initial MILP and CP models are considerably improved. Afterward, to benefit from the strengths of both improved models, a novel hybrid MILP-CP solution approach is devised. Finally, comprehensive computational experiments are conducted to evaluate the performance of the proposed models and extract useful managerial insights on the system flexibility.

• Keywords
• COVID-19 pandemic, Constraint programming, Reconfigurable machine tool, Reconfigurable manufacturing system, Scheduling, Workforce planning,
• Publication type
• Journal Article MeSH

Combating the COVID-19 pandemic has raised the demand for and disposal of personal protective equipment in the United States. This work proposes a novel waste personal protective equipment processing system that enables energy recovery through producing renewable fuels and other basic chemicals. Exergy analysis and environmental assessment through a detailed life cycle assessment approach are performed to evaluate the energy and environmental sustainability of the processing system. Given the environmental advantages in reducing 35.42% of total greenhouse gas emissions from the conventional incineration and 43.50% of total fossil fuel use from landfilling processes, the optimal number, sizes, and locations of establishing facilities within the proposed personal protective equipment processing system in New York State are then determined by an optimization-based site selection methodology, proposing to build two pre-processing facilities in New York County and Suffolk County and one integrated fast pyrolysis plant in Rockland County. Their optimal annual treatment capacities are 1,708 t/y, 8,000 t/y, and 9,028 t/y. The proposed optimal personal protective equipment processing system reduces 31.5% of total fossil fuel use and 35.04% of total greenhouse gas emissions compared to the personal protective equipment incineration process. It also avoids 41.52% and 47.64% of total natural land occupation from the personal protective equipment landfilling and incineration processes.

• Keywords
• CAPEX, Capital expenditure, Fossil fuel reduction, GAO US, Government Accountability Office, GHG emissions, GHG, Greenhouse gas, GWP, Global warming potential, HEPA, High-Efficiency Particulate Arrestance, HEX, Heat exchangers, HP, High-pressure steam, LCA, Life cycle assessment, LCI, Life cycle inventory, LP, Low-pressure steam, Life cycle assessment, MEA, Monoethanolamine, MILP, Mixed-integer linear programming, MINLP, Mixed-integer nonlinear programming, MP, Mid-pressure steam, MSDS, Material Safety Data Sheet, NMVOC, Non-methane volatile organic compound, NPV, Net present value, NYS, New York State, O&M, Operation and maintenance cost, OPEX, Operating expenditure, PPE processing system, PPE, Personal protective equipment, PSA, Pressure-swing adsorption, Process design, SD, Solid waste disposal fee MUSD, TEA, Techno-economic analysis, Techno-economic analysis, fec, Feedstock cost MUSD, inc, revenue from downstream products MUSD, obj, Annualized cost MUSD, omc, Operation and maintenance cost MUSD, stor, The total storage cost MUSD, tci, Total capital cost MUSD, tran, Total transportation cost MUSD, uc, Total utility cost MUSD,
• Publication type
• Journal Article MeSH

Over the last decade, the usage of Internet of Things (IoT) enabled applications, such as healthcare, intelligent vehicles, and smart homes, has increased progressively. These IoT applications generate delayed- sensitive data and requires quick resources for execution. Recently, software-defined networks (SDN) offer an edge computing paradigm (e.g., fog computing) to run these applications with minimum end-to-end delays. Offloading and scheduling are promising schemes of edge computing to run delay-sensitive IoT applications while satisfying their requirements. However, in the dynamic environment, existing offloading and scheduling techniques are not ideal and decrease the performance of such applications. This article formulates joint and scheduling problems into combinatorial integer linear programming (CILP). We propose a joint task offloading and scheduling (JTOS) framework based on the problem. JTOS consists of task offloading, sequencing, scheduling, searching, and failure components. The study's goal is to minimize the hybrid delay of all applications. The performance evaluation shows that JTOS outperforms all existing baseline methods in hybrid delay for all applications in the dynamic environment. The performance evaluation shows that JTOS reduces the processing delay by 39% and the communication delay by 35% for IoT applications compared to existing schemes.

• Keywords
• CLIP, JTOS, SDN, dynamic environment, framework, task scheduling,
• MeSH
• Cloud Computing * MeSH
• Internet of Things * MeSH
• Delivery of Health Care MeSH
• Publication type
• Journal Article MeSH

Delay represents a significant phenomenon in the dynamics of many human-related systems-including biological ones. It has i.a. a decisive impact on system stability, and the study of this influence is often mathematically demanding. This paper presents a computationally simple numerical gridding algorithm for the determination of stability margin delay values in multiple-delay linear systems. The characteristic quasi-polynomial-the roots of which decide about stability-is subjected to iterative discretization by means of pre-warped bilinear transformation. Then, a linear and a quadratic interpolation are applied to obtain the associated characteristic polynomial with integer powers. The roots of the associated characteristic polynomial are closely related to the estimation of roots of the original characteristic quasi-polynomial which agrees with the system's eigenvalues. Since the stability border is crossed by the leading one, the switching root locus is enhanced using the Regula Falsi interpolation method. Our methodology is implemented on-and verified by-a numerical bio-cybernetic example of the stabilization of a human-being's movement on a controlled swaying bow. The advantage of the proposed novel algorithm lies in the possibility of the rapid computation of polynomial zeros by means of standard programs for technical computing; in the low level of mathematical knowledge required; and, in the sufficiently high precision of the roots loci estimation. The relationship to the direct search QuasiPolynomial (mapping) Rootfinder algorithm and computational complexity are discussed as well. This algorithm is also applicable for systems with non-commensurate delays.

• MeSH
• Algorithms * MeSH
• Humans MeSH
• Movement physiology   MeSH
• Check Tag
• Humans MeSH
• Publication type
• Journal Article MeSH