Approaches based on integer linear programming have been recently proposed for topology optimization in wireless sensor networks. They are, however, based on over-theoretical, unrealistic models. Our aim is to show th...Approaches based on integer linear programming have been recently proposed for topology optimization in wireless sensor networks. They are, however, based on over-theoretical, unrealistic models. Our aim is to show that it is possible to accommodate realistic models for energy consumption and communication protocols into integer linear programming. We analyze the maximum lifetime broadcasting topology problem and we present realistic models that are also shown to provide efficient and practical solving tools. We present a strategy to substantially speed up the convergence of the solving process of our algorithm. This strategy introduces a practical drawback, however, in the characteristics of the optimal solutions retrieved. A method to overcome this drawback is discussed. Computational experiments are reported.展开更多
This paper gives integer linear programming (ILP) models for scheduling the League Phase of one of the most popular professional club competitions in the world, UEFA Champion’s League. There are 36 teams in the compe...This paper gives integer linear programming (ILP) models for scheduling the League Phase of one of the most popular professional club competitions in the world, UEFA Champion’s League. There are 36 teams in the competition, but each team plays only 8 other teams in the League Phase. Thus, the difficulty or ease of a team’s opponents, known as strength of schedule (SOS), compared to other teams will be different. Our main ILP model aims to minimize the maximum difference between SOS of any two teams, thus making the schedule as fair as possible. We also give a model for creating a timetable of all the matchups obtained by the first model. The models were implemented and tested using optimization software AMPL. Our main model obtained a schedule with a difference 0.4 between the highest and the lowest SOS, while that difference is 19 for the actual 2024-2025 competition. Thus, our model returns a schedule that is significantly fairer compared to the actual competition.展开更多
Land scarcity has become the prominent obstacle on the way to sustainable development for China. Under the constraints of land shortage, how to allocate the finite land resources to the multiple land users in China co...Land scarcity has become the prominent obstacle on the way to sustainable development for China. Under the constraints of land shortage, how to allocate the finite land resources to the multiple land users in China considering various political, environmental, ecological and economic conditions have become research topics with great significance. In this study, an interval fuzzy national-scale land-use model(IFNLM) was developed for optimizing land systems of China. IFNLM is based on an integration of existing interval linear programming(ILP), and fuzzy flexible programming(FFP) techniques. IFNLM allows uncertainties expressed as discrete interval values and fuzzy sets to be incorporated within a general optimization framework. It can also facilitate national-scale land-use planning under various environmental, ecological, social conditions within a multi-period and multi-option context. Then, IFNLM was applied to a real case study of land-use planning in China. The satisfaction degree of environmental constraints is between 0.69 and 0.97, the system benefit will between 198.25 × 1012 USD and 229.67 × 1012 USD. The results indicated that the hybrid model can help generate desired policies for land-use allocation with a maximized economic benefit and minimized environmental violation risk. Optimized land-use allocation patterns can be generated from the proposed IFNLM.展开更多
The circle geometric constraint model （CGCM） was put forward for resolving the open-pit mine ore-matching problems （OMOMP）. By adopting the approaches of graph theory, block model of blasted piles was abstracted i...The circle geometric constraint model （CGCM） was put forward for resolving the open-pit mine ore-matching problems （OMOMP）. By adopting the approaches of graph theory, block model of blasted piles was abstracted into a set of nodes and directed edges, which were connected together with other nodes in the range of circle constraints, to describe the mining sequence. Also, the constructing method of CGCM was introduced in detail. The algorithm of CGCM has been realized in the DIM1NE system, and applied to a short-term （5 d） program calculation for ore-matching of a cement limestone mine in Hebei Province, China. The applications show that CGCM can well describe the mining sequence of ore blocks and its mining geometric constraints in the process of mining blasted piles. This model, which is applicable for resolving OMOMP under complicated geometric constraints with accurate results, provides effective ways to solve the problems of open-pit ore-matching.展开更多
With the rapid development of highway construction and formation of the highway network in China,the man- agement of pavement maintenance and rehabilitation （MR） activities has become important.In this paper,four di...With the rapid development of highway construction and formation of the highway network in China,the man- agement of pavement maintenance and rehabilitation （MR） activities has become important.In this paper,four discrete optimization models are proposed for different parties involved in the management system： government,highway agent,con- tractor and the common users.These four optimal decision models are formulated as linear integer programming problems with binary decision variables.The objective function and constraints are based on the pavement performance and prediction model using the pavement condition index （PCI）.Numerical experiments are carried out with the data from a highway system in Sichuan Province which show the feasibility and effectiveness of the proposed models.展开更多
In this paper we develop modeling techniques for a social partitioning problem. Different social interaction regulations are imposed during pandemics to prevent the spread of diseases. We suggest partitioning a set of...In this paper we develop modeling techniques for a social partitioning problem. Different social interaction regulations are imposed during pandemics to prevent the spread of diseases. We suggest partitioning a set of company employees as an effective way to curb the spread, and use integer programming techniques to model it. The goal of the model is to maximize the number of direct interactions between employees who are essential for company’s work subject to the constraint that all employees should be partitioned into components of no more than a certain size implied by the regulations. Then we further develop the basic model to take into account different restrictions and provisions. We also give heuristics for solving the problem. Our computational results include sensitivity analysis on some of the models and analysis of the heuristic performance.展开更多
This paper gives integer linear programming models for scheduling doubles tennis group competitions. The goal is to build a fair and competitive schedule for all players. Our basic model achieves that for each player ...This paper gives integer linear programming models for scheduling doubles tennis group competitions. The goal is to build a fair and competitive schedule for all players. Our basic model achieves that for each player the average ranking of his partners in all matches is as close as possible to the average ranking of his opponents in all matches. One of the variations of the basic model provides that each matchup is fair and competitive. We also give models for the case when the number of players is 4n<span style="font-family:;" "=""> </span><span style="font-family:;" "="">+</span><span style="font-family:;" "=""> </span><span style="font-family:;" "="">2, and thus one of the matches has to be singles. Our models were implemented and tested using optimization software AMPL. Computational results along with schedules for some typical situations are also given the paper.</span>展开更多
文摘Approaches based on integer linear programming have been recently proposed for topology optimization in wireless sensor networks. They are, however, based on over-theoretical, unrealistic models. Our aim is to show that it is possible to accommodate realistic models for energy consumption and communication protocols into integer linear programming. We analyze the maximum lifetime broadcasting topology problem and we present realistic models that are also shown to provide efficient and practical solving tools. We present a strategy to substantially speed up the convergence of the solving process of our algorithm. This strategy introduces a practical drawback, however, in the characteristics of the optimal solutions retrieved. A method to overcome this drawback is discussed. Computational experiments are reported.
文摘This paper gives integer linear programming (ILP) models for scheduling the League Phase of one of the most popular professional club competitions in the world, UEFA Champion’s League. There are 36 teams in the competition, but each team plays only 8 other teams in the League Phase. Thus, the difficulty or ease of a team’s opponents, known as strength of schedule (SOS), compared to other teams will be different. Our main ILP model aims to minimize the maximum difference between SOS of any two teams, thus making the schedule as fair as possible. We also give a model for creating a timetable of all the matchups obtained by the first model. The models were implemented and tested using optimization software AMPL. Our main model obtained a schedule with a difference 0.4 between the highest and the lowest SOS, while that difference is 19 for the actual 2024-2025 competition. Thus, our model returns a schedule that is significantly fairer compared to the actual competition.
基金Under the auspices of National Natural Science Foundation of China(No.41201164)Humanities and Social Science Research Planning Fund,Ministry of Education of China(No.12YJCZH299)
文摘Land scarcity has become the prominent obstacle on the way to sustainable development for China. Under the constraints of land shortage, how to allocate the finite land resources to the multiple land users in China considering various political, environmental, ecological and economic conditions have become research topics with great significance. In this study, an interval fuzzy national-scale land-use model(IFNLM) was developed for optimizing land systems of China. IFNLM is based on an integration of existing interval linear programming(ILP), and fuzzy flexible programming(FFP) techniques. IFNLM allows uncertainties expressed as discrete interval values and fuzzy sets to be incorporated within a general optimization framework. It can also facilitate national-scale land-use planning under various environmental, ecological, social conditions within a multi-period and multi-option context. Then, IFNLM was applied to a real case study of land-use planning in China. The satisfaction degree of environmental constraints is between 0.69 and 0.97, the system benefit will between 198.25 × 1012 USD and 229.67 × 1012 USD. The results indicated that the hybrid model can help generate desired policies for land-use allocation with a maximized economic benefit and minimized environmental violation risk. Optimized land-use allocation patterns can be generated from the proposed IFNLM.
基金Project(2011AA060407) supported by the National High Technology Research and Development Program of ChinaProject(51074073) supported by the National Natural Science Foundation of China
文摘The circle geometric constraint model （CGCM） was put forward for resolving the open-pit mine ore-matching problems （OMOMP）. By adopting the approaches of graph theory, block model of blasted piles was abstracted into a set of nodes and directed edges, which were connected together with other nodes in the range of circle constraints, to describe the mining sequence. Also, the constructing method of CGCM was introduced in detail. The algorithm of CGCM has been realized in the DIM1NE system, and applied to a short-term （5 d） program calculation for ore-matching of a cement limestone mine in Hebei Province, China. The applications show that CGCM can well describe the mining sequence of ore blocks and its mining geometric constraints in the process of mining blasted piles. This model, which is applicable for resolving OMOMP under complicated geometric constraints with accurate results, provides effective ways to solve the problems of open-pit ore-matching.
基金Project supported by the National Natural Science Foundation of China (Grant No.70671064)
文摘With the rapid development of highway construction and formation of the highway network in China,the man- agement of pavement maintenance and rehabilitation （MR） activities has become important.In this paper,four discrete optimization models are proposed for different parties involved in the management system： government,highway agent,con- tractor and the common users.These four optimal decision models are formulated as linear integer programming problems with binary decision variables.The objective function and constraints are based on the pavement performance and prediction model using the pavement condition index （PCI）.Numerical experiments are carried out with the data from a highway system in Sichuan Province which show the feasibility and effectiveness of the proposed models.
文摘In this paper we develop modeling techniques for a social partitioning problem. Different social interaction regulations are imposed during pandemics to prevent the spread of diseases. We suggest partitioning a set of company employees as an effective way to curb the spread, and use integer programming techniques to model it. The goal of the model is to maximize the number of direct interactions between employees who are essential for company’s work subject to the constraint that all employees should be partitioned into components of no more than a certain size implied by the regulations. Then we further develop the basic model to take into account different restrictions and provisions. We also give heuristics for solving the problem. Our computational results include sensitivity analysis on some of the models and analysis of the heuristic performance.
文摘This paper gives integer linear programming models for scheduling doubles tennis group competitions. The goal is to build a fair and competitive schedule for all players. Our basic model achieves that for each player the average ranking of his partners in all matches is as close as possible to the average ranking of his opponents in all matches. One of the variations of the basic model provides that each matchup is fair and competitive. We also give models for the case when the number of players is 4n<span style="font-family:;" "=""> </span><span style="font-family:;" "="">+</span><span style="font-family:;" "=""> </span><span style="font-family:;" "="">2, and thus one of the matches has to be singles. Our models were implemented and tested using optimization software AMPL. Computational results along with schedules for some typical situations are also given the paper.</span>
