A Class of Algorithms for Solving LP Problems by Prioritizing the Constraints

Linear programming is a method for solving linear optimization problems with constraints, widely met in real-world applications. In the vast majority of these applications, the number of constraints is significantly larger than the number of variables. Since the crucial subject of these problems is to detect the constraints that will be verified as equality in an optimal solution, there are methods for investigating such constraints to accelerate the whole process. In this paper, a technique named proximity technique is addressed, which under a proposed theoretical framework gives an ascending order to the constraints in such a way that those with low ranking are characterized of high priority to be binding. Under this framework, two new Linear programming optimization algorithms are introduced, based on a proposed Utility matrix and a utility vector accordingly. For testing the addressed algorithms firstly a generator of 10,000 random linear programming problems of dimension n with m constraints, where , is introduced in order to simulate as many as possible real-world problems, and secondly, real-life linear programming examples from the NETLIB repository are tested. A discussion of the numerical results is given. Furthermore, already known methods for solving linear programming problems are suggested to be fitted under the proposed framework.

Coordinate scheduling approach for EDS observation tasks and data transmission jobs

Electromagnetic detection satellite（EDS） is a type of Earth observation satellite（EOS）. Satellites observation and data down-link scheduling plays a significant role in improving the efficiency of satellite observation systems. However, the current works mainly focus on the scheduling of imaging satellites, little work focuses on the scheduling of EDSes for its specific requirements.And current works mainly schedule satellite resources and data down-link resources separately, not considering them in a globally optimal perspective. The EDSes and data down-link resources are scheduled in an integrated process and the scheduling result is searched globally. Considering the specific constraints of EDS, a coordinate scheduling model for EDS observation tasks and data transmission jobs is established and an algorithm based on the genetic algorithm is proposed. Furthermore, the convergence of our algorithm is proved. To deal with some specific constraints, a solution repairing algorithm of polynomial computing time is designed. Finally, some experiments are conducted to validate the correctness and practicability of our scheduling algorithms.