Pareto local search (PLS) is a basic building block in many metaheuristics for a multiobjective combinatorial optimization problem. In this paper, an enhanced PLS variant called parallel PLS based on ...decomposition (PPLS/D) is proposed. PPLS/D improves the efficiency of PLS using the techniques of parallel computation and problem decomposition. It decomposes the original search space into L subregions and executes L parallel processes searching in these subregions simultaneously. Inside each subregion, the PPLS/D process is guided by a unique scalar objective function. PPLS/D differs from the well-known two phase PLS in that it uses the scalar objective function to guide every move of the PLS procedure in a fine-grained manner. In the experimental studies, PPLS/D is compared against the basic PLS and a recently proposed PLS variant on the multiobjective unconstrained binary quadratic programming problems and the multiobjective traveling salesman problems with, at most, four objectives. The experimental results show that regardless of whether the initial solutions are randomly generated or generated by heuristic methods, PPLS/D always performs significantly better than the other two PLS variants.
In glass furnace boosting, particularly in the tin bath and annealing lehr heating systems, an ac-ac power converter is normally employed by the industry. This Triac-based converter driven by ...integral cycle control (ICC) is employed to provide highly accurate power to the resistive heating elements distributed into the furnace. The advantages of ICC include low inrush current and increased reliability; although its impact on power quality (PQ), due to the subharmonic distortion produced, is significant. While different strategies for energy demand management have been implemented to date, they have not adequately addressed this PQ issue. Thus, the goal of this research is to establish an optimal electrical load scheduling strategy considering criteria about PQ and thermal behavior through a mixed-binary quadratic programming problem which exploits the ICC advantages avoiding PQ degradation.
Metaheuristics have been widely utilized for solving NP-hard optimization problems. However, these algorithms usually perform differently from one problem to another, i.e., one may be effective on a ...problem but performs badly on another problem. Therefore, it is difficult to choose the best algorithm in advance for a given problem. In contrast to selecting the best algorithm for a problem, selection hyper-heuristics aim at performing well on a set of problems (instances). This paper proposes a selection hyper-heuristic based algorithm for multi-objective optimization problems. In the proposed algorithm, multiple metaheuristics exhibiting different search behaviors are managed and controlled as low-level metaheuristics in an algorithm pool, and the most appropriate metaheuristic is selected by means of a performance indicator at each search stage. To assess the performance of the proposed algorithm, an implementation of the algorithm containing four metaheuristics is proposed and tested for solving multi-objective unconstrained binary quadratic programming problem. Experimental results on 50 benchmark instances show that the proposed algorithm can provide better overall performance than single metaheuristics, which demonstrates the effectiveness of the proposed algorithm.
•A selection hyper-heuristic based algorithm is proposed for multi-objective optimization problem.•Multiple metaheuristics exhibiting different search behaviors are mixed and controlled in an algorithm pool.•At each search stage, the most appropriate metaheuristic is selected by a performance indicator.•An implementation of the proposed algorithm containing four metaheuristics is provided to solve combinatorial multi-objective optimization problems.•Experimental results for multi-objective unconstrained binary quadratic programming problem confirm the effectiveness of the proposed algorithm.
The standard linearization of a binary quadratic program yields an equivalent reformulation as an integer linear program, but the resulting LP-bounds are very weak in general. We concentrate on ...applications where the underlying linear problem is tractable and exploit the fact that, in this case, the optimization problem is still tractable in the presence of a single quadratic term in the objective function. We propose to strengthen the standard linearization by the use of cutting planes that are derived from jointly considering each single quadratic term with the underlying combinatorial structure. We apply this idea to the quadratic minimum spanning tree and spanning forest problems and present complete polyhedral descriptions of the corresponding problems with one quadratic term, as well as efficient separation algorithms for the resulting polytopes. Computationally, we observe that the new inequalities significantly improve dual bounds with respect to the standard linearization, particularly for sparse graphs.
•We study the query batching problem in database systems.•We develop a mixed binary quadratic program for the problem.•Our model relies on a novel regression-based processing-time prediction ...function.•We prove the proposed mixed binary quadratic program is an NP-hard problem.•We develop two heuristics and show their efficacy on three database benchmarks.
Techniques based on sharing data and computation among queries have been an active research topic in database systems. While work in this area developed algorithms and systems that are shown to be effective, there is a lack of rigorous modeling and theoretical study for query processing and optimization. Query batching in database systems has strong resemblance to order batching in the warehousing context. While the latter is a well-studied problem, the literature on optimization techniques for query batching problem is quite scarce/nonexistent. In this study, we develop a Mixed Binary Quadratic Program (MBQP) to optimize query-batching in a database system. This model uses the coefficients of a linear regression on the query retrieval time, trained by a large set of randomly generated query sets. We also propose two heuristics, the so-called restricted-cardinality search methods I and II, for solving the proposed MBQP. To demonstrate the effectiveness of our proposed techniques, we conduct a comprehensive computational study over randomly generated instances of three well-known database benchmarks. The computational results show that when the proposed MBQP is solved using the designed heuristics, an improvement of up to 61.8% in retrieving time is achieved.
•We propose two closed-form formulas to quickly reevaluate r-flip moves.•Algorithms are designed which are simple to implement and fast to compute.•We test our results using local search and Variable ...Neighborhood Search heuristics.•Experiments show relatively large reductions in time consumption using our formulas.
The Unconstrained Binary Quadratic Programming problem (UBQP) belongs to the NP-hard class and has become a framework for modeling a variety of combinatorial optimization problems. The methods most commonly used to solve instances of the UBQP explore the concept of neighborhood of a solution. Given a binary vector x ∈ {0, 1}n, solution to a UBQP instance, a neighborhood of x can be defined by flip moves. Flip moves consist on selecting one or more elements (positions) of x and “flip” their values to their complementary values (i.e., from 1 to 0 or from 0 to 1). Normally, those methods compute a large number of flip moves, and so the whole process to solve an instance can be quite time consuming. In order to reduce this time, some works have proposed ways to efficiently evaluate one or two flip moves, and also extensions to higher order moves. In this paper we propose two closed-form formulas for evaluating quickly any order of flip moves. To test our theoretical findings, we executed an extensive set of computational experiments over well-known instances for the problem. Against common belief, our results show that it is possible to compute high order flip moves very fast.
The computational utility of inductive linearizations for binary quadratic programs when combined with a mixed-integer programming solver is investigated for several combinatorial optimization ...problems and established benchmark instances.
Existing methods for forecasting the productivity of a factory are subject to a major drawback—the lower and upper bounds of productivity are usually determined by a few extreme cases, which ...unacceptably widens the productivity range. To address this drawback, an interval fuzzy number (IFN)-based mixed binary quadratic programming (MBQP)–ordered weighted average (OWA) approach is proposed in this study for modeling an uncertain productivity learning process. In the proposed methodology, the productivity range is divided into the inner and outer sections, which correspond to the lower and upper membership functions of an IFN-based fuzzy productivity forecast, respectively. In this manner, all actual values are included in the outer section, whereas most of the values are included within the inner section to fulfill different managerial purposes. According to the percentages of outlier cases, a suitable forecasting strategy can be selected. To derive the values of parameters in the IFN-based fuzzy productivity learning model, an MBQP model is proposed and optimized. Subsequently, according to the selected forecasting strategy, the OWA method is applied to defuzzify a fuzzy productivity forecast. The proposed methodology has been applied to the real case of a dynamic random access memory factory to evaluate its effectiveness. The experimental results indicate that the proposed methodology was superior to several existing methods, especially in terms of mean absolute error, mean absolute percentage error, and root mean square error in evaluating the forecasting accuracy. The forecasting precision achieved using the proposed methodology was also satisfactory.
•Propose a multiple phase tabu search algorithm for BBQP-PV.•Combine the SN-TS phase and the VLSN-TS phase for search intensification.•Design a hybrid perturbation phase for search ...diversification.•Find improved lower bounds for 5 instances.
The Bipartite Boolean Quadratic Programming Problem with Partitioned Variables (BBQP-PV) is an NP-hard problem with many practical applications. In this study, we present an effective multiple phase tabu search algorithm for solving BBQP-PV. The algorithm is characterized by a joint use of three key components: two tabu search phases that employ a simple neighborhood and a very large-scale neighborhood to achieve search intensification, and a hybrid perturbation phase that adaptively chooses a greedy perturbation or a recency-based perturbation for search diversification. Experimental assessment on 50 standard benchmarks indicates that the proposed algorithm is able to obtain improved lower bounds for 5 instances and match the previously best solutions for most instances, while achieving this performance within competitive time. Additional analysis confirms the importance of the innovative search components.
This study proposes a novel optimal phasor measurement unit (PMU) placement method for dynamic vulnerability assessment with minimum number of PMUs. PMU measurements should reflect the change of ...power system status as earlier as possible when a contingency occurs. Therefore, those buses which are sensitive to the change of power system status have to be equipped with PMUs to monitor the fragile areas of power systems. First, a large power system is partitioned into several coherent clusters. Next, a probabilistic vulnerability index defined as the objective function and a binary quadratic programming model are proposed for this purpose. Finally, the proposed method is tested on IEEE 9-, 39-, and 145-bus systems. Results show that this method results in a PMU configuration with minimum number of devices and high vulnerability index. Such a PMU placement is able to estimate the vulnerability of power systems.
PDF
