The Study On Models And Algorithms For Several Combinatorial Optimization Problems

Combinatorial Optimization has been playing a fundamental role in our real life as well as in a variety of human activities. The problems that can be formulated as combinatorial optimization problems appear literally everywhere. For example, the best choice of a route in a network, an appropriate arrangement for flights and a reasonable investment in financial market, all these things can be formulated as combinatorial optimization problems. Establishing reasonable combinatorial optimization models and searching for efficient algorithms have been the research areas of many distinguished researchers for more than50years. Due to all the effort they have made over the years, combinatorial optimization has been one of the fastest growing branches of mathematics. So in order to learn and do research of the subjects in this field, people should familiar themselves with some classical combinatorial optimization problems for which the new insights often lie in. And rethinking some classical combinatorial optimization problems help people to generalize problems so that highly efficient algorithm for the real life could be possible. In this dissertation, we mainly discuss three kinds of models in combinatorial optimization, namely, the Chinese Postman Problem, the Scheduling Problem with Job Rejection Constraint and Combinatorial Investing Problem.The Chinese Postman Problem (CPP) in three different networks (undirected, directed and mixed graphs) has been considered. With the help of T-joins and T-cuts, we are able to state the structure of CPP clearly so that we could do research on this direction in the future. The sufficient and necessary conditions for deciding whether a given graph in three mentioned networks is an Eulerian has also been surveyed. A theorem together with a question about Eulerian in mixed graph have been formulated thereby. By constructing a minimal counterexample, we gave the question a negative answer, which may save time and energy for those who want to do the same thing, and which will point out the right path for future research.The Scheduling Problem with Job Rejection Constraint, which is a generalization of the classical scheduling problem, is NP-hard, so can not be solved exactly in polynomial time unless P=NP. In this dissertation, we proposed a strongly polynomial time algorithm for solving it. We proved that the algorithm is2-approximation algorithm for the problem, and we also showed that our analysis is best possible by providing a tight example. Based on this algorithm, we also pointed out the future research.The idea, perspective and methodology of combinatorial optimization can be applied to the field of investment. In this dissertation, the MV modle with certain constraints has been considered. We are able to show that our model is better than that classical model in terms of applications to the real market.