The Maximum Balanced Biclique Problem (MBBP) is a prominent model with numerous applications. Yet. the problem is NP-hard and thus computationally challenging. We propose novel ideas for designing effective exact algo...
详细信息
The Maximum Balanced Biclique Problem (MBBP) is a prominent model with numerous applications. Yet. the problem is NP-hard and thus computationally challenging. We propose novel ideas for designing effective exact algorithms for MBBP in bipartite graphs. First, an Upper Bound Propagation (UBP) procedure to pre-compute an upper bound involving each vertex is introduced. Then we extend a simple Branchand-Bound (B&B) algorithm by integrating the pre-computed upper bounds. Based on UBP, we also study a new integer linear programming model of MBBP which is more compact than an existing formulation (Dawande, Keskinocak, Swaminathan, & Tayur, 2001). We introduce new valid inequalities induced from the upper bounds to tighten these mathematical formulations for MBBP. Experiments with random bipartite graphs demonstrate the efficiency of the extended B&B algorithm and the valid inequalities generated on demand. Further tests with 30 real-life instances show that, for at least three very large graphs, the new approaches improve the computational time with four orders of magnitude compared to the original B&B. (C) 2018 E(C)sevier B.V. All rights reserved.
In Schwerdfeger and Walter (2016), we proposed a subset sum based improvement procedure (denoted by LS) for solving the problem of minimizing the normalized sum of squared workload deviations on m identical machines. ...
详细信息
In Schwerdfeger and Walter (2016), we proposed a subset sum based improvement procedure (denoted by LS) for solving the problem of minimizing the normalized sum of squared workload deviations on m identical machines. In its core, the algorithm builds on an exact procedure (denoted by WB3) for the case of m = 3 machines. Although this approach proved to be superior to existing procedures in terms of solution quality, we identified room for further improvements. Building upon our prior work, in this follow-up paper we suggest an enhanced version of WB3 that leads to a significant speed-up of several orders of magnitude and we considerably improve on the performance of LS on difficult instances where the ratio of the number of jobs to the number of machines is small. Moreover, we investigate a simple surrogate balancing measure that can also be optimized by our algorithms with only a slight modification. Results of a comprehensive computational study on a large set of benchmark as well as random test instances demonstrate the effectiveness of the improved algorithms. (C) 2018 Elsevier Ltd. All rights reserved.
The Blocks Relocation Problem is an important problem in storage systems. An input instance for it consists of a set of blocks distributed in stacks where each block is identified by a retrieval number and each stack ...
详细信息
The Blocks Relocation Problem is an important problem in storage systems. An input instance for it consists of a set of blocks distributed in stacks where each block is identified by a retrieval number and each stack has a same maximum height limit. The objective is to retrieve all the blocks respecting their retrieval order and performing the minimum number of relocations. Only blocks at the top of a stack can be moved: either a block is retrieved, if it has the highest retrieval priority among the stacked blocks, or it is relocated to the top of another stack. Solving this problem is critical in storage systems because it saves operational time and resources. In this paper, we present two new lower bounds for the number of relocations of an optimal solution. We implemented an exact iterative deepening A* algorithm using these new proposed lower bounds and other well-known lower bounds from the literature. We performed several computational experiments to show that the new lower bounds improve the performance of the exact algorithm, solving to optimality more instances than when using other lower bounds when given the same amount of time. (C) 2018 Elsevier Ltd. All rights reserved.
An edge dominating set in a graph G=(V,E) is a subset of the edges DaS dagger E such that every edge in E is adjacent or equal to some edge in D. The problem of finding an edge dominating set of minimum cardinality is...
详细信息
An edge dominating set in a graph G=(V,E) is a subset of the edges DaS dagger E such that every edge in E is adjacent or equal to some edge in D. The problem of finding an edge dominating set of minimum cardinality is NP-hard. We present a faster exact exponential time algorithm for this problem. Our algorithm uses O(1.3226 (n) ) time and polynomial space. The algorithm combines an enumeration approach of minimal vertex covers in the input graph with the branch and reduce paradigm. Its time bound is obtained using the measure and conquer technique. The algorithm is obtained by starting with a slower algorithm which is refined stepwisely. In each of these refinement steps, the worst cases in the measure and conquer analysis of the current algorithm are reconsidered and a new branching strategy is proposed on one of these worst cases. In this way a series of algorithms appears, each one slightly faster than the previous one, ending in the O(1.3226 (n) ) time algorithm. For each algorithm in the series, we also give a lower bound on its running time. We also show that the related problems: minimum weight edge dominating set, minimum maximal matching and minimum weight maximal matching can be solved in O(1.3226 (n) ) time and polynomial space using modifications of the algorithm for edge dominating set. In addition, we consider the matrix dominating set problem which we solve in O(1.3226 (n+m) ) time and polynomial space for nxm matrices, and the parametrised minimum weight maximal matching problem for which we obtain an O (au)(2.4179 (k) ) time and space algorithm.
We consider a two-dimensional problem in which one is required to split a given rectangular bin into the smallest number of items. The resulting items must be squares to be packed, without overlapping, into the bin so...
详细信息
We consider a two-dimensional problem in which one is required to split a given rectangular bin into the smallest number of items. The resulting items must be squares to be packed, without overlapping, into the bin so as to cover all the given rectangle. We present a mathematical model and a heuristic algorithm that is proved to find the optimal solution in some special cases. Then, we introduce a relaxation of the problem and present different exact approaches based on this relaxation. Finally, we report computational experiments on the performances of the algorithms on a large set of randomly generated instances.
Co-operative learning in heterogeneous teams refers to learning methods in which teams are organised both to accomplish academic tasks and for individuals to gain knowledge. Competencies, personality and the gender of...
详细信息
Co-operative learning in heterogeneous teams refers to learning methods in which teams are organised both to accomplish academic tasks and for individuals to gain knowledge. Competencies, personality and the gender of team members are key factors that influence team performance. Here, we introduce a team composition problem, the so-called synergistic team composition problem (STCP), which incorporates such key factors when arranging teams. Thus, the goal of the STCP is to partition a set of individuals into a set of synergistic teams: teams that are diverse in personality and gender and whose members cover all required competencies to complete a task. Furthermore, the STCP requires that all teams are balanced in that they are expected to exhibit similar performances when completing the task. We propose two efficient algorithms to solve the STCP. Our first algorithm is based on a linear programming formulation and is appropriate to solve small instances of the problem. Our second algorithm is an anytime heuristic that is effective for large instances of the STCP. Finally, we thoroughly study the computational properties of both algorithms in an educational context when grouping students in a classroom into teams using actual-world data. (C) 2019 Elsevier B.V. All rights reserved.
We consider the problem of minimizing a linear function over an affine section of the cone of positive semidefinite matrices, with the additional constraint that the feasible matrix has prescribed rank. When the rank ...
详细信息
We consider the problem of minimizing a linear function over an affine section of the cone of positive semidefinite matrices, with the additional constraint that the feasible matrix has prescribed rank. When the rank constraint is active, this is a non-convex optimization problem, otherwise it is a semidefinite program. Both find numerous applications especially in systems control theory and combinatorial optimization, but even in more general contexts such as polynomial optimization or real algebra. While numerical algorithms exist for solving this problem, such as interior-point or Newton-like algorithms, in this paper we propose an approach based on symbolic computation. We design an exact algorithm for solving rank-constrained semidefinite programs, whose complexity is essentially quadratic on natural degree bounds associated to the given optimization problem: for subfamilies of the problem where the size of the feasible matrix, or the dimension of the affine section, is fixed, the algorithm is polynomial time. The algorithm works under assumptions on the input data: we prove that these assumptions are generically satisfied. We implement it in Maple and discuss practical experiments. (C) 2017 Elsevier Ltd. All rights reserved.
We investigate a number of recently reported exact algorithms for the maximum clique problem. The program code is presented and analyzed to show how small changes in implementation can have a drastic effect on perform...
详细信息
We investigate a number of recently reported exact algorithms for the maximum clique problem. The program code is presented and analyzed to show how small changes in implementation can have a drastic effect on performance. The computational study demonstrates how problem features and hardware platforms influence algorithm behaviour. The effect of vertex ordering is investigated. One of the algorithms (MCS) is broken into its constituent parts and we discover that one of these parts frequently degrades performance. It is shown that the standard procedure used for rescaling published results (i.e., adjusting run times based on the calibration of a standard program over a set of benchmarks) is unsafe and can lead to incorrect conclusions being drawn from empirical data.
We address some special cases of job shop and flow shop scheduling problems with s-precedence constraints. Unlike the classical setting, in which precedence constraints among the tasks of a job are finish-start, here ...
详细信息
We address some special cases of job shop and flow shop scheduling problems with s-precedence constraints. Unlike the classical setting, in which precedence constraints among the tasks of a job are finish-start, here the task of a job cannot start before the task preceding it has started. We give polynomial exact algorithms for the following problems: a two-machine job shop with two jobs when recirculation is allowed (i.e., jobs can visit the same machine many times), a two-machine flow shop, and an m-machine flow shop with two jobs. We also point out some special cases whose complexity status is open.
In this paper, we consider the (n,3)-MAXSAT problem. The problem is a special case of the Maximum Satisfiability problem with an additional requirement that in input formula each variable appears at most three times. ...
详细信息
ISBN:
(纸本)9783030046514;9783030046507
In this paper, we consider the (n,3)-MAXSAT problem. The problem is a special case of the Maximum Satisfiability problem with an additional requirement that in input formula each variable appears at most three times. Here, we improve previous upper bounds for (n,3)-MAXSAT in terms of n (number of variables) and in terms of k (number of clauses that we are required to satisfy). Moreover, we prove that satisfying more clauses than the simple all true assignment is an NP-hard problem.
暂无评论