When a system of one-sided max-plus linear equations is inconsistent, its right-hand side vector may be slightly modified to reach a consistent one. It is handled in this note by minimizing the sum of absolute deviations in the right-hand side vector. It turns out that this problem may be reformulated as a mixed integer linear programming problem. Although solving such a problem requires much computational effort, it may propose a solution that just modifies few elements of the right-hand side vector,...
This paper demonstrates that the sensor cover energy problem in wireless communication can be transformed into a linear programming problem with max-plus linear inequality constraints. Consequently, by a well-developed preprocessing procedure, it can be further reformulated as a 0-1 integer linear programming problem and hence tackled by the routine techniques developed in linear and integer optimization. The performance of this two-stage solution approach is evaluated on a set of randomly generated...
When a system of one-sided max-plus linear equations is inconsistent, the approximate solutions within an admissible error bound may be desired instead, particularly with some sparsity property. It is demonstrated in this paper that obtaining the sparsest approximate solution within a given error bound may be transformed in polynomial time into the set covering problem, which is known to be NP-hard. Besides, the problem of obtaining the sparsest approximate solution within a given error bound...
This paper investigates bipolar max-min equations which can be viewed as a generalization of fuzzy relational equations with max-min composition. The relation between the consistency of bipolar max-min equations and the classical boolean satisfiability problem is revealed. Consequently, it is shown that the problem of determining whether a system of bipolar max-min equations is consistent or not is NP-complete. Moreover, a consistent system of bipolar max-min equations, as well as its solution set,...
Download Results (CSV)