Search

Dual-functional radar–communication systems are extensively employed for the detection and control of unmanned aerial vehicle groups and play crucial roles in scenario monitoring. In this study, we address the downlink precoding problem in large-scale multi-user multiple-input multiple-output dual-function radar–communication systems equipped with low-resolution quantized digital-to-analog converters. To tackle this issue, we develop a weighted optimization framework that minimizes the mean squared error between the transmitted symbols and their estimates while satisfying specific radar performance requirements. Due to the complexity introduced by discrete constraints, we decompose the original problem into three sub-problems to reduce computational burden. Furthermore, we propose a dynamic projection refinement algorithm within the alternating direction method of multiplier framework to efficiently solve these sub-problems. Numerical experiments demonstrate that our proposed method outperforms existing state-of-the-art techniques, particularly in terms of bit error rate in low signal-to-noise ratio scenarios. [ABSTRACT FROM AUTHOR]

Spatial optimization is an integral part of GIS and spatial analysis. It involves making various decisions in space, ranging from the location of public facilities to vehicle routing and political districting. While useful, such problems (especially large problem instances) are often difficult to solve using general mathematical programming (due to their generality). Traditionally, an alternative solution method is Lagrangian relaxation, which, if well-designed, can be fast and optimal. One has to derive the Lagrangian dual problem and its (sub)gradients, and move towards the optimal solution via a search process such as gradient descent. Despite its merits, Lagrangian relaxation as a solution algorithm requires one to derive the (sub)gradients manually, which is error-prone and makes the solution algorithm difficult to develop and highly dependent on the model at hand. This paper aims to ease the development of Lagrangian relaxation algorithms for GIS practitioners by employing the automatic (sub)gradient (autograd) computation capabilities originally developed in modern Deep Learning. Using the classic p-median problem as an example, we demonstrate how Lagrangian relaxation can be developed with paper and pencil, and how the (sub)gradient computation derivation can be automated using autograd. As such, the human expert only needs to implement the Lagrangian problem in a scientific computing language (such as Python), and the system can find the (sub)gradients of this code, even if it contains complex loops and conditional statements. We verify that the autograd version of the algorithm is equivalent to the original version with manually derived gradients. By automating the (sub)gradient computation, we significantly lower the cost of developing a Lagrangian algorithm for the p-median. And such automation can be applied to numerous other optimization problems. [ABSTRACT FROM AUTHOR]

In this work, we consider a combinatorial optimization problem with direct applications in blockchain mining, namely finding the most lucrative blocks for Bitcoin miners, and propose optimal algorithmic solutions. Our experiments show that our algorithms increase the miners’ revenues by more than a million dollars per month. Modern blockchains reward their miners in two ways: (i) a base reward for each block that is mined, and (ii) the transaction fees of those transactions that are included in the mined block. The base reward is fixed by the respective blockchain’s protocol and is not under the miner’s control. Hence, for a miner who wishes to maximize earnings, the fundamental problem is to form a valid block with maximal total transaction fees and then try to mine it. Moreover, in many protocols, including Bitcoin itself, the base reward halves at predetermined intervals, hence increasing the importance of maximizing transaction fees and mining an optimal block. This problem is further complicated by the fact that transactions can be prerequisites of each other or have conflicts (in case of double-spending). In this work, we consider the problem of forming an optimal block, i.e. a valid block with maximal total transaction fees, given a set of unmined transactions. On the theoretical side, we first formally model our problem as an extension of Knapsack and then show that, unlike classical Knapsack, our problem is strongly NP-hard. We also show a hardness-of-approximation result. As such, there is no hope in solving it efficiently for general instances. However, we observe that its real-world instances are quite sparse, i.e. the transactions have very few dependencies and conflicts. Using this fact, and exploiting three well-known graph sparsity parameters, namely treedepth, treewidth and pathwidth, we present exact linear-time parameterized algorithms that are applicable to the real-world instances and obtain optimal results. On the practical side, we provide an extensive experimental evaluation demonstrating that our approach vastly outperforms the current Bitcoin miners in practice, obtaining a significant per-block average increase of 11.34 percent in transaction fee revenues which amounts to almost one million dollars per month. [ABSTRACT FROM AUTHOR]

The development of metaheuristic algorithms has led to the solution of various optimization problems. Bioinspired optimization algorithms like the New Caledonian crow learning algorithm (NCCLA) are primarily designed to address continuous problems. As most real‐world problems are discrete, some operators have been proposed to convert continuous algorithms into discrete ones to address these problems. These operators include evolutionary operators such as crossover and mutation, transformation operators such as symmetry, swap, and shift, and K‐opt algorithms such as 2‐opt, 2‐opt and a half, and 3‐opt. Employing some of these operators usually accompanies changing the algorithm's rules or the movement patterns of its search agents. However, mathematical operators such as modular arithmetic and set theory and random permutation provide an ability to keep the same algorithm's agent proposed in its continuous version and K‐opt algorithms usually balance the algorithm's exploration and exploitation capabilities. Thus, this paper converts the NCCLA into a discrete version by utilizing a combination of those mathematical operators and the 3‐opt algorithm. This combination allows the algorithm to maintain a balance between exploration and exploitation. The resulting algorithm, called the discrete New Caledonian crow learning algorithm (DNCCLA), is employed to solve the traveling salesman problem (TSP). In addition, the paper investigates the best combination of mathematical operators with K‐opt algorithms or the symmetry operator. The performance results demonstrate that DNCCLA outperforms state‐of‐the‐art discrete algorithms, exhibiting a good balance between exploration and exploitation. The algorithm successfully solves 20 TSP instances of varying scales, and it consistently achieved the top rank among the tested algorithms. [ABSTRACT FROM AUTHOR]

Kidney transplantation is vital for treating end-stage renal disease, impacting roughly one in a thousand Europeans. The search for a suitable deceased donor often leads to prolonged and uncertain wait times, making living donor transplants a viable alternative. However, approximately 40% of living donors are incompatible with their intended recipients. Therefore, many countries have established kidney exchange programs, allowing patients with incompatible donors to participate in "swap" arrangements, exchanging donors with other patients in similar situations. Several variants of the vertex-disjoint cycle cover problem model the above problem, which deals with different aspects of kidney exchange as required. This paper discusses several specific vertex-disjoint cycle cover variants and deals with finding the exact solution. We employ the dataless neural networks framework to establish single differentiable functions for each variant. Recent research highlights the framework's effectiveness in representing several combinatorial optimization problems. Inspired by these findings, we propose customized dataless neural networks for vertex-disjoint cycle cover variants. We derive a differentiable function for each variant and prove that the function will attain its minimum value if an exact solution is found for the corresponding problem variant. We also provide proof of the correctness of our approach. [ABSTRACT FROM AUTHOR]

The Double Row Layout Problem (DRLP) asks for an arrangement of machines on both sides of a straight line corridor so as to minimize the total cost for transferring materials among machines. The DRLP is NP-Hard and has practical relevance, specially in manufacturing systems design. In this paper, we drastically reduce the time required to solve the problem by constructing a new and effective mixed-integer linear programming (MILP) model of the DRLP. The new model was obtained by reformulating an existing MILP model. This includes tightening some constraints, introducing new variables, implementing constraints to link the new and original variables; and adding valid inequalities and a valid system of equations. To reduce the size of the reformulated model, we eliminate several of the new introduced variables by a substitution using the system of equations. The computational results demonstrate that the proposed model requires considerably smaller computational times compared to the ones in the literature. As a consequence, optimal solutions can now be efficiently found for larger instances of the problem. Previous studies have been able to optimally solve, within reasonable time, instances with size up to 16 machines, while with the new model four instances with 20 machines could be optimally solved. [ABSTRACT FROM AUTHOR]

Problems of search optimization in a discrete space, particularly, in a binary space where a variable can take only two values, are of great practical importance. This paper proposes a new population-based discrete optimization algorithm that uses probability distributions of variables. The distributions determine the probability of taking one or another discrete value and are generated by transforming target values of solutions into their weight coefficients. The performance of the algorithm is evaluated using unimodal and multimodal test functions with binary variables. The experimental results demonstrate the high efficiency of the proposed algorithm in terms of convergence rate and stability. [ABSTRACT FROM AUTHOR]

This study introduces Gaussian Binary Particle Swarm Optimization (G-BPSO), designed to address binary optimization challenges effectively. G-BPSO employs new transfer functions of the Gaussian type derived from the power functions to enable mapping of real-valued vectors of individual encodings into binary form. This ensures smooth change between steps and improved convergence. To assess the effectiveness of G-BPSO, a host of complex optimization problems such as the un-capacitated facility location problem are investigated. Enhanced efficiency and improvement over existing methods in binary optimization is observed. The MATLAB code of G-BPSO is made open-access through https://github.com/kanak02/GBPSO. [ABSTRACT FROM AUTHOR]

The Canadian Armed Forces (CAF) is currently facing recruitment challenges. Similar to target market advertising in other industries, military recruitment can be optimized by aiming recruitment efforts at populations with high enrolment success potential. Using historical data, geographical regions with high potential for recruitment can be identified. This can be used to optimize the reach of recruitment events to high potential geographical regions. This paper looks at applications of facility location optimization in recruitment attraction event planning activities where there are intersections in regions each venue can attract audiences from (venue reach areas), and the probability that the events will attract targeted audience varies by geographical location. This study models the problem as a mixed integer nonlinear problem (MINLP) and provides an exact solution method. This is followed by a case study applying the model to the CAF’s recruitment events for a sample geographical area of the Canadian National Capital Region (NCR). [ABSTRACT FROM AUTHOR]

In this paper, an entirely novel discrete probabilistic model is presented to generate 0-1 Knapsack Problem instances. We analyze the expected behavior of the greedy algorithm, the eligible-first algorithm and the linear relaxation algorithm for these instances; all used to bound the solution of the 0-1 Knapsack Problem (0-1 KP) and/or its approximation. The probabilistic setting is given and the main random variables are identified. The expected performance for each of the aforementioned algorithms is analytically established in closed forms in an unprecedented way. [ABSTRACT FROM AUTHOR]

Unsupervised hashing has attracted extensive attention in effectively and efficiently tackling large-scale cross-modal retrieval task. Existing methods typically try to mine the latent common subspace across multimodal data without any category annotation. Despite the exciting progress, there are still three challenges that need to be further addressed: (1) efficiently improving the robustness during latent common subspace learning; (2) harmoniously embedding the intra-modal inherence and inter-modal relevance of multimodal data into Hamming space; and (3) effectively reducing the training time complexity and making the model scalable for large-scale datasets. To well address the above challenges, this study proposes a method named Fast Unsupervised Cross-Modal Hashing (FUCH). Specifically, FUCH proposes a semantic-aware collective matrix factorization to learn robust representation via exploiting latent category-specific attributes, and introduces Cauchy loss to measure the factorization process. Accordingly, the above process can effectively embed potential discriminative information into common space, while making the model insensitive for outliers. Moreover, FUCH designs a dual projection learning scheme, which not only learns modality-unique hash functions to excavate individual properties but also learns modality-mutual hash functions to multimodal correlational properties. Experimental results on three benchmark datasets verify the effectiveness of FUCH under various scenarios. [ABSTRACT FROM AUTHOR]

In this study, we present a deep reinforcement learning framework for solving scenario-based two-stage stochastic programming problems. Stochastic programs have numerous real-time applications, such as scheduling, disaster management, and route planning, yet they are computationally challenging to solve and require specially designed solution strategies such as hand-crafted heuristics. To the extent of our knowledge, this is the first study that decomposes two-stage stochastic programs with a multi-agent structure in a deep reinforcement learning algorithmic framework to solve them faster. Specifically, we propose a general two-stage deep reinforcement learning framework that can generate high-quality solutions within a fraction of a second, in which two different learning agents sequentially learn to solve each stage of the problem. The first-stage agent is trained with the feedback of the second-stage agent using a new policy gradient formulation since the decisions are interconnected through the stages. We demonstrate our framework through a general multi-dimensional stochastic knapsack problem. The results show that solution time can be reduced up to five orders of magnitude with sufficiently good optimality gaps of around 7%. Also, a decision-making agent can be trained with a few scenarios and can solve problems with many scenarios and achieve a significant reduction in solution times. Considering the vast state and action space of the problem of interest, the results show a promising direction for generating fast solutions for stochastic online optimization problems without expert knowledge. [ABSTRACT FROM AUTHOR]

The branch-and-bound algorithm based on decision diagrams is a framework for solving discrete optimization problems with a dynamic programming formulation. It works by compiling a series of bounded-width decision diagrams that can provide lower and upper bounds for any given subproblem. Eventually, every part of the search space will be either explored or pruned by the algorithm, thus proving optimality. This paper presents new ingredients to speed up the search by exploiting the structure of dynamic programming models. The key idea is to prevent the repeated expansion of nodes corresponding to the same dynamic programming states by querying expansion thresholds cached throughout the search. These thresholds are based on dominance relations between partial solutions previously found and on pruning inequalities given by rough upper bounds and local bounds — two additional filtering techniques recently introduced. Computational experiments show that the pruning brought by this caching mechanism allows for significantly reducing the number of nodes expanded by the algorithm. This results in more benchmark instances of difficult optimization problems being solved in less time while using narrower decision diagrams. History: Accepted by Andrea Lodi, Area Editor for Design and Analysis of Algorithms–Discrete. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0340), as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2022.0340). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]

Data clustering can find similarities and hidden patterns within data. Given a predefined number of groups, most partitional clustering algorithms use representative centers to determine their corresponding clusters. These algorithms, such as K-means and optimization-based algorithms, create and update centroids to give (hyper) spherical shape clusters. This research proposes a noncentroid-based discrete differential evolution (NCDDE) algorithm to solve clustering problems and provide non-spherical shape clusters. The algorithm directs the population of discrete vectors to search for data group labels. It uses a novel discrete mutation strategy analogous to the continuous mutation in classical differential evolution. It also combines a sorting mutation to enhance convergence speed. The algorithm adaptively selects crossover rates in high and low ranges. We use the UCI datasets to compare the NCDDE with other continuous centroidbased algorithms by intra-cluster distance and clustering accuracy. The results show that NCDDE outperforms the compared algorithms overall by intra-cluster distance and achieves the best accuracy for several datasets. [ABSTRACT FROM AUTHOR]

Achieving long-wavelength infrared (LWIR) cameras with high sensitivity and shorter exposure times faces challenges due to series reflections from high-refractive index lenses within compact optical systems. However, designing effective antireflective coatings to maximize light throughput in these systems is complicated by the limited range of transparent materials available for the LWIR. This scarcity narrows the degrees of freedom in design, complicating the optimization process for a system that aims to minimize the number of physical layers and address the inherent large refractive mismatch from high-index lenses. In this study, we use discrete-to-continuous optimization to design a subwavelength-thick antireflective multilayer coating on high-refractive index Si substrate for LWIR cameras, where the coating consists of few (e.g., five) alternating stacks of high- and low-refractive-index thin films (e.g., Ge-YF3, Ge-ZnS, or ZnS-YF3). Discrete optimization efficiently reveals the configuration of physical layers through binary optimization supported by a machine learning model. Continuous optimization identifies the optimal thickness of each coating layer using the conventional gradient method. As a result, considering the responsivity of a LWIR camera, the discrete-to-continuous strategy finds the optimal design of a 2.3-μm-thick antireflective coating on Si substrate consisting of five physical layers based on the Ge-YF3 high-low index pair, showing an average reflectance of 0.54 % within the wavelength range of 8–13 μm. Moreover, conventional thin-film deposition (e.g., electron-beam evaporator) techniques successfully realize the designed structure, and Fourier-transform infrared spectroscopy (FTIR) and thermography confirm the high performance of the antireflective function.

This article extends recently developed finite variation sensitivity analysis (FVSA) approaches to an inverse homogenization problem. The design of metamaterials with prescribed mechanical properties is stated as a discrete density‐based topology optimization problem, in which the design variables define the microstructure of the periodic base cell. The FVSA consists in estimating the finite variations of the objective and constraint functions after independently switching the state of each variable. It is used to properly linearize the functions of binary variables so the optimization problem can be solved through sequential integer linear programming. Novel sensitivity expressions were developed and it was shown that they are more accurate than the ones conventionally used in literature. Referred to as the conjugate gradient sensitivity (CGS) approach, the proposed strategy was quantitatively evaluated through numerical examples. In these examples, metamaterials with prescribed homogenized Poisson's ratios and minimal homogenized Young's moduli were obtained. A hexagonal base cell with dihedral D3$$ {D}_3 $$ symmetry was used to produce only metamaterials with isotropic properties. It was shown that, by using the CGS approach instead of the conventional sensitivity analysis, the sensitivity error was substantially reduced for the considered problem. The proposed developments effectively improved the stability and robustness of the discrete optimization procedures. In all the considered examples, when more accurate sensitivity analyses were performed, the parameters of the topology optimization method could be tuned more easily, yielding effective solutions even if the settings were not ideal. [ABSTRACT FROM AUTHOR]

Lagrangian heuristics for discrete optimization work by modifying Lagrangian relaxed solutions into feasible solutions to an original problem. They are designed to identify feasible, and hopefully also near-optimal, solutions and have proven to be highly successful in many applications. Based on a primal-dual global optimality condition for non-convex optimization problems, we develop a meta-heuristic extension of the Lagrangian heuristic framework. The optimality condition characterizes (near-)optimal solutions in terms of near-optimality and near-complementarity measures for Lagrangian relaxed solutions. The meta-heuristic extension amounts to constructing a weighted combination of these measures, thus creating a parametric auxiliary objective function, which is a close relative to a Lagrangian function, and embedding a Lagrangian heuristic in a search procedure in the space of the weight parameters. We illustrate and make a first assessment of this meta-heuristic extension by applying it to the generalized assignment and set covering problems. Our computational experience show that the meta-heuristic extension of a standard Lagrangian heuristic can significantly improve upon solution quality. [ABSTRACT FROM AUTHOR]

Crew scheduling is typically performed in two stages. First, solving the crew pairing problem generates sequences of flights called pairings. Then, the pairings are assigned to crew members to provide each person with a full schedule. A common way to do this is to solve an optimization problem called the crew rostering problem (CRP). However, before solving the CRP, the problem instance must be parameterized appropriately while taking different factors such as preassigned days off, crew training, sick leave, reserve duty, or unusual events into account. In this paper, we present a new method for the parameterization of CRP instances for pilots by scheduling planners. A machine learning-based sequential assignment procedure (seqAsg) whose arc weights are computed using a policy over state–action pairs for pilots is implemented to generate very fast solutions. We establish a relationship between the quality of the solutions generated by seqAsg and that of solutions produced by a state-of-the-art solver. Based on those results, we formulate recommendations for instance parameterization. Given that the seqAsg procedure takes only a few seconds to run, this allows scheduling workers to reparameterize crew rostering instances many times over the course of the planning process as needed. [ABSTRACT FROM AUTHOR]

AbstractGiven a time series in Rn with a piecewise constant mean and independent noises, we propose an exact dynamic programming algorithm for minimizing a least-squares criterion with a multiscale penalty, favoring well-spread changepoints. This penalty was proposed by Verzelen et al. and achieves optimal rates for changepoint detection and changepoint localization in a non-asymptotic scenario. Our proposed algorithm, Multiscale Functional Pruning Optimal Partitioning (Ms.FPOP), extends functional pruning ideas presented in Rigaill and Maidstone et al. to multiscale penalties. For large signals (n≥105) with sparse changepoints, Ms.FPOP is shown empirically to be quasi-linear and faster than the Pruned Exact Linear Time (PELT) method of Killick et al. applied to the multiscale penalty of Verzelen et al. which exhibits quadratic slowdown in these cases. We propose an efficient implementation of Ms.FPOP coded in C++ interfaced with R that can segment profiles of up to n=106 in a matter of seconds. Our algorithm works for slightly more general multiscale penalties. In particular, it allows a minimum segment length to be imposed. Using simple simulations we then show that where profiles are sufficiently large (n≥104), Ms.FPOP using the multiscale penalty of Verzelen et al. is typically more powerful than optimizing a least-squares criterion with the BIC penalty of Yao, a criterion that was shown by Fearnhead and Rigaill to perfom well across a wide range of scenarios. Supplementary materials for this article are available online. [ABSTRACT FROM AUTHOR]

The dung beetle optimization (DBO) algorithm is acknowledged for its robust optimization capabilities and rapid convergence as an efficient swarm intelligence optimization technique. Nevertheless, DBO, similar to other swarm intelligence algorithms, often gets trapped in local optima during the later stages of optimization. To mitigate this challenge, we propose the Move-to-Escape dung beetle optimization (MEDBO) algorithm in this paper. MEDBO utilizes a good point set strategy for initializing the swarm's initial population, ensuring a more uniform distribution and diminishing the risk of local optima entrapment. Moreover, it incorporates convergence factors and dynamically balances the number of offspring and foraging individuals, prioritizing global exploration initially and local exploration subsequently. This dynamic adjustment not only enhances the search speed but also prevents local optima stagnation. The algorithm's performance was assessed using the CEC2017 benchmark suite, which confirmed MEDBO's significant improvements. Additionally, we applied MEDBO to three engineering problems: pressure vessel design, three-bar truss design, and spring design. MEDBO exhibited an excellent performance in these applications, demonstrating its practicality and efficacy in real-world problem-solving contexts. [ABSTRACT FROM AUTHOR]

Various metaheuristic algorithms inspired by nature have been designed to deal with a variety of practical optimization problems. As an excellent metaheuristic algorithm, the improved particle swarm optimization algorithm based on grouping (IPSO) has strong global search capabilities. However, it lacks a strong local search ability and the ability to solve constrained discrete optimization problems. This paper focuses on improving these two aspects of the IPSO algorithm. Based on IPSO, we propose an improved particle swarm optimization algorithm based on variable neighborhood search (VN-IPSO) and design a 0-1 integer programming solution with constraints. In the experiment, the performance of the VN-IPSO algorithm is fully tested and analyzed using 23 classic benchmark functions (continuous optimization), 6 knapsack problems (discrete optimization), and 10 CEC2017 composite functions (complex functions). The results show that the VN-IPSO algorithm wins 18 first places in the classic benchmark function test set, including 6 first places in the solutions for seven unimodal test functions, indicating a good local search ability. In solving the six knapsack problems, it wins four first places, demonstrating the effectiveness of the 0-1 integer programming constraint solution and the excellent solution ability of VN-IPSO in discrete optimization problems. In the test of 10 composite functions, VN-IPSO wins first place four times and ranks the first in the comprehensive ranking, demonstrating its excellent solving ability for complex functions. [ABSTRACT FROM AUTHOR]

Achieving long-wavelength infrared (LWIR) cameras with high sensitivity and shorter exposure times faces challenges due to series reflections from high-refractive index lenses within compact optical systems. However, designing effective antireflective coatings to maximize light throughput in these systems is complicated by the limited range of transparent materials available for the LWIR. This scarcity narrows the degrees of freedom in design, complicating the optimization process for a system that aims to minimize the number of physical layers and address the inherent large refractive mismatch from high-index lenses. In this study, we use discrete-to-continuous optimization to design a subwavelength-thick antireflective multilayer coating on high-refractive index Si substrate for LWIR cameras, where the coating consists of few (e.g., five) alternating stacks of high- and low-refractive-index thin films (e.g., Ge-YF3, Ge-ZnS, or ZnS-YF3). Discrete optimization efficiently reveals the configuration of physical layers through binary optimization supported by a machine learning model. Continuous optimization identifies the optimal thickness of each coating layer using the conventional gradient method. As a result, considering the responsivity of a LWIR camera, the discrete-to-continuous strategy finds the optimal design of a 2.3-μm-thick antireflective coating on Si substrate consisting of five physical layers based on the Ge-YF3 high-low index pair, showing an average reflectance of 0.54 % within the wavelength range of 8–13 μm. Moreover, conventional thin-film deposition (e.g., electron-beam evaporator) techniques successfully realize the designed structure, and Fourier-transform infrared spectroscopy (FTIR) and thermography confirm the high performance of the antireflective function. [ABSTRACT FROM AUTHOR]

AbstractWe present a stochastic programming model for informing the deployment of ad hoc flood mitigation measures to protect electric substations prior to an imminent and uncertain hurricane. The first stage captures the deployment of a fixed number of mitigation resources, and the second stage captures grid operation in response to a contingency. The primary objective is to minimize expected load shed. We develop methods for simulating flooding induced by extreme rainfall and construct two geographically realistic case studies, one based on Tropical Storm Imelda and the other on Hurricane Harvey. Applying our model to those case studies, we investigate the effect of the mitigation budget on the optimal objective value and solutions. Our results highlight the sensitivity of the optimal mitigation to the budget, a consequence of those decisions being discrete. We additionally assess the value of having better mitigation options and the spatial features of the optimal mitigation. [ABSTRACT FROM AUTHOR]

The objective of this study is to utilize the geometric mean optimizer (GMO) for mass optimization of structural trusses. By harnessing the GMO's mutation mechanism rooted in a Gaussian framework, the model effectively addresses the discrete nature of truss structure optimization. Through a comprehensive evaluation involving four distinct problem scenarios including 10, 15, 25, and 52-bar truss structures with both discrete and continuous variables, the effectiveness of the GMO technique is thoroughly demonstrated. The optimization findings underscore that the GMO consistently generates improved designs in comparison to conventional population-based techniques. Furthermore, the GMO model demonstrates remarkable computational efficiency in specific cases. This research emphasizes the potential of the GMO-based approach as a potent tool in the domain of truss structure optimization. It holds the capability to revolutionize the manner in which engineers approach the intricate balance between structural integrity, minimal weight, and cost-effectiveness. [ABSTRACT FROM AUTHOR]

Simultaneous optimization of a family of related products can yield significant benefits compared to individual product optimization. Standardization of parts across different products and streamlining assembly and manufacturing processes can lead to reduced overall costs for the product family. In this study, we introduce a methodology for optimizing the design of a product family while considering detailed CAD models of individual products. The motivation arises from the challenge of achieving optimal product standardization without compromising individual product performance. Existing methods often impose predefined levels of commonality and seldom account for detailed CAD models and computationally expensive metrics of interest. To address this gap, we propose a novel approach that utilizes surrogate models to mitigate computational complexity and optimize the product family configuration based on total production cost, ensuring economically viable configurations while meeting performance requirements. The objective function incorporates the total production cost of the product family, including manufacturing and assembly process costs and volume discounts. Assembly process complexity and associated costs are quantified using Design for Assembly rules, while individual product performance, evaluated through finite element models, serves as a constraint. The results of the single-objective optimization, applied to a case study involving a product family comprising multiple gearboxes, demonstrate that by considering the product family, a better design in terms of the total production cost can be found compared to optimizing each product individually. Results indicate that the suggested method can efficiently identify optimal product family configurations, balancing standardization benefits with individual product performance. Overall, this study contributes to advancing methodologies for product family optimization and underscores the importance of considering detailed product designs in the optimization process. [ABSTRACT FROM AUTHOR]

The optimization of Multidimensional Knapsacks with Family‐Split Penalties has been introduced in the literature as a variant of the more classical Multidimensional Knapsack and Multi‐Knapsack problems. This problem deals with a set of items partitioned in families, and when a single item is picked to maximize the utility, then all items in its family must be picked. Items from the same family can be assigned to different knapsacks, and in this situation split penalties are paid. This problem arises in real applications in various fields. This paper proposes a new exact and fast algorithm based on a specific Combinatorial Benders Cuts scheme. An extensive experimental campaign computationally shows the validity of the proposed method and its superior performance compared to both commercial solvers and state‐of‐the‐art approaches. The paper also addresses algorithmic flexibility and scalability issues, investigates challenging cases, and analyzes the impact of problem parameters on the algorithm behavior. Moreover, it shows the applicability of the proposed approach to a wider class of realistic problems, including fixed costs related to each knapsack utilization. Finally, further possible research directions are considered. [ABSTRACT FROM AUTHOR]

Local search methods are convenient alternatives for solving discrete optimization problems (DOPs). These easy-to-implement methods are able to find approximate optimal solutions within a tolerable time limit. It is known that the quality of the initial solution greatly affects the quality of the approximated solution found by a local search method. In this paper, we propose to take the initial solution as a random variable and learn its preferable probability distribution. The aim is to sample a good initial solution from the learned distribution so that the local search can find a high-quality solution. We develop two different deep network models to deal with DOPs established on set (the knapsack problem) and graph (the maximum clique problem), respectively. The deep neural network learns the representation of an optimization problem instance and transforms the representation to its probability vector. Experimental results show that given the initial solution sampled from the learned probability distribution, a local search method can acquire much better approximate solutions than the randomly-sampled initial solution on the synthesized knapsack instances and the Erdős-Rényi random graph instances. Furthermore, with sampled initial solutions, a classical genetic algorithm can achieve better solutions than a random initialized population in solving the maximum clique problems on DIMACS instances. Particularly, we emphasize that the developed models can generalize in dimensions and across graphs with various densities, which is an important advantage on generalizing deep-learning-based optimization algorithms. [ABSTRACT FROM AUTHOR]

Lagrangian relaxation is a common and often successful way to approach computationally challenging single-objective discrete optimization problems with complicating side constraints. Its aim is often twofold; first, it provides bounds for the optimal value, and, second, it can be used to heuristically find near-optimal feasible solutions, the quality of which can be assessed by the bounds. We consider bi-objective discrete optimization problems with complicating side constraints and extend this Lagrangian bounding and heuristic principle to such problems. The Lagrangian heuristic here produces non-dominated candidates for points on the Pareto frontier, while the bounding forms a polyhedral outer approximation of the Pareto frontier, which can be used to assess the quality of the candidate points. As an illustration example we consider a facility location problem in which both CO2 emission and cost should be minimized. The computational results are very encouraging, both with respect to bounding and the heuristically found non-dominated solutions. In particular, the Lagrangian bounding is much stronger than the outer approximation given by the Pareto frontier of the problem’s linear programming relaxation. [ABSTRACT FROM AUTHOR]

A robust two-stage problem of selecting a single minimum cost representative out of n candidates is studied. Each candidate is associated with an uncertain cost that is described by a lower bound and a deviation from it. In the first stage, at most k representatives have to be selected. After that, an adversary distributes the worst costs to all representatives so that the sum of the cost deviation ratios (the uncertainty budget) does not exceed a given upper bound. In the second stage, the cost of the cheapest representative is paid. An O (n 2 log n) time algorithm is proposed for this problem. [ABSTRACT FROM AUTHOR]

The composition of Web services represents a critical challenge in the development of business process. It consists of creating new functionalities by selecting individual services from a set of abstract activities and merging them into massive services. With the increasing number of available similar functionalities, the quality-of-service parameters, provided by Web services, have become criteria for selecting a composite web service plan that provides best possible service quality values among other possible compositions. As, the problem of Web service selection is a time-consuming optimization problem, we present, in this work, an enhanced version of the Balanced Teaching-Learning-Based optimization algorithm, called Discrete Balanced Teaching-Learning-Based optimization algorithm 'DBTLBO', which supports the discrete nature of the web service selection problem, by selecting a specific composition of web services from a set of candidate services, while meeting user needs and QoS preferences. several experiments were performed in a simulated environment. The obtained results were compared with those of TLBO, GA and PSO algorithms under the same conditions and clearly demonstrated the effectiveness of the proposed algorithm compared to the other algorithms mentioned above. [ABSTRACT FROM AUTHOR]

Linear assignment problems hold a pivotal role in combinatorial optimization, offering a broad spectrum of applications within the field of data sciences. They consist of assigning "agents" to "tasks" in a way that leads to a minimum total cost associated with the assignment. The assignment is balanced when the number of agents equals the number of tasks, with a one-to-one correspondence between agents and tasks, and it is and unbalanced otherwise. Additional options and constraints may be imposed, such as allowing agents to perform multiple tasks or allowing tasks to be performed by multiple agents. In this paper, we propose a novel framework that can solve all these assignment problems employing methodologies derived from the field of statistical physics. We describe this formalism in detail and validate all its assertions. A major part of this framework is the definition of a concave effective free energy function that encapsulates the constraints of the assignment problem within a finite temperature context. We demonstrate that this free energy monotonically decreases as a function of a parameter β representing the inverse of temperature. As β increases, the free energy converges to the optimal assignment cost. Furthermore, we demonstrate that when β values are sufficiently large, the exact solution to the assignment problem can be derived by rounding off the elements of the computed assignment matrix to the nearest integer. We describe a computer implementation of our framework and illustrate its application to multi-task assignment problems for which the Hungarian algorithm is not applicable. [ABSTRACT FROM AUTHOR]

This paper proposes a method for simultaneous evaluation of the assembly process complexity together with the performance of the future product. It allows for product design optimization, considering different aspects of the future design at the early stage of the development process. The proposed method, embodied in a fully automated framework, substitutes the traditional sequential development process with a more efficient and rapid combined procedure, which addresses multiple design aspects simultaneously. Design for assembly (DFA) rules, used as quantitative metrics of the ease-of-assembly of the whole product and individual assembly operations, are automatically evaluated together with performance metrics, estimated based on finite element (FE) simulations. The direct solution to this optimization problem might be inefficient or impossible since it requires the recurrent evaluation of computationally expensive discrete and continuous functions with unknown behavior that represent the optimization objectives and constraints. For that reason, the proposed framework employs regression models based on the Gaussian process and artificial neural networks, thus achieving the optimal design of a product as a result of metamodel-based design optimization (MBDO). The suggested approach is demonstrated in the optimization of a gearbox assembly, considering its mechanical performance and assembly process. Comparing the results of the metamodel-based and direct design optimization shows that MBDO allows finding a better solution using a three times smaller computational budget. In addition, analysis of the results obtained using stationary sampling data sets of different sizes highlighted the limitations of the employed sampling procedure. [ABSTRACT FROM AUTHOR]

Many variations of the classical graph coloring model have been intensively studied due to their multiple applications; scheduling problems and aircraft assignments, for instance, motivate the robust coloring problem. This model gets to capture natural constraints of those optimization problems by combining the information provided by two colorings: a vertex coloring of a graph and the induced edge coloring on a subgraph of its complement; the goal is to minimize, among all proper colorings of the graph for a fixed number of colors, the number of edges in the subgraph with the endpoints of the same color. The study of the robust coloring model has been focused on the search for heuristics due to its NP-hard character when using at least three colors, but little progress has been made in other directions. We present a new approach on the problem obtaining the first collection of non-heuristic results for general graphs; among them, we prove that robust coloring is the model that better approaches the equitable partition of the vertex set, even when the graph does not admit a so-called equitable coloring. We also show the NP-completeness of its decision problem for the unsolved case of two colors, obtain bounds on the associated robust coloring parameter, and solve a conjecture on paths that illustrates the complexity of studying this coloring model. [ABSTRACT FROM AUTHOR]