We present algorithm MIQCR-CB that is an advancement of MIQCR. MIQCR is a method for solving mixed-integer quadratic programs and works in two phases: the first phase determines an equivalent quadratic formulation with a convex objective function by solving a semidefinite problem (SDP); in the second phase, the equivalent formulation is solved by a standard solver. Because the reformulation relies on the solution of a large-scale semidefinite program, it is not tractable by existing semidefinite solvers even for medium-sized problems. To surmount this difficulty, we present in MIQCR-CB a subgradient algorithm within a Lagrangian duality framework for solving (SDP) that substantially speeds up the first phase. Moreover, this algorithm leads to a reformulated problem of smaller size than the one obtained by the original MIQCR method, which results in a shorter time for solving the second phase. We present extensive computational results to show the efficiency of our algorithm. First, we apply MIQCR-CB to the k-cluster problem that can be formulated by a binary quadratic program. As an illustration of the efficiency of our new algorithm, for instances of size 80 and of density 25%, MIQCR-CB is on average 78 times faster for phase 1 and 24 times faster for phase 2 than the original MIQCR. We also compare MIQCR-CB with QCR and with BiqCrunch, two methods devoted to binary quadratic programming. We show that MIQCR-CB is able to solve most of the 225 considered instances within three hours of CPU time. We also present experiments on two classes of general integer instances where we compare MIQCR-CB with MIQCR, Couenne, and Cplex12.6. We demonstrate the significant improvement over the original MIQCR approach. Finally, we show that MIQCR-CB is able to solve almost all of the considered instances, whereas Couenne and Cplex12.6 are not able to solve half of them.

We consider the problem of maximizing the reliability of a series-parallel system given cost and weight constraints on the system. The number of components in each subsystem, and the choice of components are the decision variables. In this paper, we propose an integer linear programming approach that gives an approximate feasible solution, close to the optimal solution, together with an upper bound on the optimal reliability. We show that integer linear programming is a useful approach for solving this reliability problem. The mathematical programming model is relatively simple. Its implementation is immediate by using a mathematical programming language, and integer linear programming software. And the computational experiments show that the performance of this approach is excellent based on a comparison with previous results.

In this paper we will consider the 0–1 quadratic knapsack problem (QKP). Our purpose is to show that using a linear reformulation of this problem and a standard mixed integer programming tool, it is possible to solve the QKP efficiently in terms of computation time and the size of problems considered, in comparison to existing methods. Considering a problem involving n variables, the linearization technique we propose has the advantage of adding only (n – 1) real variables and 2(n – 1) constraints. We present extensive computational results on randomly generated instances and on structured problems coming from applications. For example, the method allows us to solve randomly generated QKP instances exactly with up to 140 variables.

Studies the complexity of the problem of allocating m modules to n processors in a distributed system to minimize total communication and execution costs. When the communication graph is a tree, Bokhari has shown that the optimum allocation can be determined in O(mn/sup 2/) time. Recently, this result has been generalized by Fernandez-Baca, who has proposed an allocation algorithm in O(mn/sup k+1/) when the communication graph is a partial k-tree. The author shows that in the case where communication costs are uniform, the module allocation problem can be solved in O(mn) time if the communication graph is a tree. This algorithm is asymptotically optimum.>

This paper presents an efficient algorithm to solve one of the task allocation problems. Task assignment in an heterogeneous multiple processors system is investigated. The cost function is formulated in order to measure the intertask communication and processing costs in an uncapacited network. A formulation of the problem in terms of the minimization of a submodular quadratic pseudo-Boolean function with assignment constraints is then presented. The use of a branch-and-bound algorithm using a Lagrangean relaxation of these constraints is proposed. The lower bound is the value of an approximate solution to the Lagrangean dual problem. A zero-duality gap, that is, a saddle point, is characterized by checking the consistency of a pseudo-Boolean equation. A solution is found for large-scale problems (e.g., 20 processors, 50 tasks, and 200 task communications or 10 processors, 100 tasks, and 300 task communications). Excellent experimental results were obtained which are due to the weak frequency of a duality gap and the efficient characterization of the zero-gap (for practical purposes, this is achieved in linear time). Moreover, from the saddle point, it is possible to derive the optimal task assignment.