The bipartite Boolean quadratic programming problem (BBQP) is a generalization of the well-studied NP-hard Boolean quadratic programming problem and can be regarded as a unified model for many graph theoretic optimization problems, including maximum weight-induced subgraph problems, maximum weight biclique problems, matrix factorization problems, and maximum cut problems on bipartite graphs. This paper introduces three main algorithms for solving the BBQP, based on three variants of tabu search, the first two consisting of strategic oscillation–tabu search (SO-TS) algorithms, which use destructive and constructive procedures to guide the search into unexplored and promising areas. The third algorithm, whichDoes also incorporates the SO-TS algorithms as solution improvement methods, uses a path relinking (PR) algorithm that is capable of further enhancing search performance. Experimental results demonstrate that all three algorithms perform very effectively compared with the best methods in the literature, and the PR algorithm joined with tabu search is able to discover new best solutions for two-thirds of the large problem instances and match the previous best known solutions for the other instances. Additional analysis discloses the contributions of the key ingredients of each of the proposed algorithms.

We study a sensor–weapon–target assignment (S-WTA) problem that considers the desired probability of target destruction and aims to minimize the total cost of combat resources. Lower and upper bounds for the S-WTA problem are obtained by constructing linear approximation models. We also propose an adaptive large neighborhood search (ALNS) algorithm characterized by a model-driven repair phase to solve this problem. The destruction phase adaptively selects a destruction operator to remove partial resource assignments and produces an incomplete reference solution. For the destroyed solution, the repair phase generates a reduced subproblem that optimizes only the destroyed parts while keeping the other parts fixed. Each subproblem is formulated as a mixed integer programming model and solved by a general-purpose solver to repair the destroyed solution. Computational experiments show that the approximation formulations can obtain tight lower and upper bounds for most problem instances. Moreover, our proposed ALNS algorithm is competitive with the solver for small instances and effectively solves large instances. In addition, we experimentally demonstrate that our ALNS outperforms state-of-the-art algorithms in the literature, and the proposed model-driven solution repair phase outperforms the traditional heuristic repair operators.

In recent years, black-box distributed optimization (DBO) has been widely studied to solve complex optimization problems in multi-agent systems, such as hyperparameter optimization of distributed machine learning. However, most existing methods use a fixed or diminishing step size to sample and search in the black box optimization space, which makes it challenging to maintain optimization efficiency on different optimization problems. In this work, we propose a multi-agent evolution strategy with cooperative and cumulative step adaptation (). In, each agent executes the algorithm to sample and explores its local objective function, and communicates with other agents to optimize the global objective function cooperatively, which is the sum of local objective functions. To improve the sampling adaptability, we design a cooperative and cumulative step adaptation method (CCSA) consisting of inner adaptation and outer adaptation. By detecting the evolution path of the multi-agent system, CCSA decreases the step size when the evolution directions of agents are conflicting and increases the step size when consistent. In terms of theoretical analysis, we first discuss the working principle of CCSA, and then discuss the system consensus of . In terms of experimental verification, achieves better consensus performance and competitive solution quality compared with state-of-the-art algorithms for DBO.