Optimal reliability design (ORD) problem is challenging and fundamental to the study of system reliability. For a system with u components/stages where each of them can be set in m possible reliability levels, state-of-the-art linear reformulation models of ORD problem require O(um) binary variables, O(mn) continuous variables together with either O(mn) inequality constraints or O(um) equality constraints. Using the special property of prime factorization and adopting the logarithmic expression technique, in this article, we propose a novel linear reformulation model of the ORD problem requiring O(um) binary variables, O(mn n! ) continuous variables, and very few linear constraints. This theoretic reduction in variables and constraints can lead to significant savings in computational efforts. Our numerical experiments further confirm the drastic reduction in computational time for solving ORD problems in large size.

Polynomial discrete programming problems are commonly faced but hard to solve. Treating the nonconvex cross-product terms is the key. State-of-the-art methods usually convert such a problem into a 0-1 mixed-integer linear programming problem and then adopt the branch-and-bound scheme to find an optimal solution. Much effort has been spent on reducing the required numbers of variables and linear constraints as well as on avoiding unbalanced branch-and-bound trees. This study presents a set of equations that linearize the discrete cross-product terms in an extremely effective manner. It is shown that embedding the proposed “equations for linearizing discrete products” into those state-of-the-art methods in the literature not only significantly reduces the required number of linear constraints from O(h3n3) to O(hn) for a cubic polynomial discrete program with n variables in h possible values but also tighten these methods with much more balanced branch-and-bound trees. Numerical experiments confirm a two-order (102-times) reduction in computational time for some randomly generated cubic polynomial discrete programming problems. There is a Video Overview associated with this article, available as supplemental material.

This paper studies the classical task assignment problem (TAP) in which M unbreakable tasks are assigned to N agents with the objective to minimize the communication and process costs subject to each agent's capacity constraint. Because a large-size TAP involves many binary variables, most, if not all, traditional methods experience the difficulty in solving the problem within a reasonable time period. Recent works present a logarithmic approach to reduce the number of binary variables in problems with mixed-integer variables. This study proposes a new logarithmic method that significantly reduces the numbers of binary variables and inequality constraints in solving task assignment problems. Our numerical experiments demonstrate that the proposed method is superior to other known methods of this kind for solving large-size TAPs.