Satellite Component Layout Optimization(SCLO) is crucial in satellite system design.This paper proposes a novel Satellite Three-Dimensional Component Assignment and Layout Optimization(3D-SCALO) problem tailored to en...Satellite Component Layout Optimization(SCLO) is crucial in satellite system design.This paper proposes a novel Satellite Three-Dimensional Component Assignment and Layout Optimization(3D-SCALO) problem tailored to engineering requirements, aiming to optimize satellite heat dissipation while considering constraints on static stability, 3D geometric relationships between components, and special component positions. The 3D-SCALO problem is a challenging bilevel combinatorial optimization task, involving the optimization of discrete component assignment variables in the outer layer and continuous component position variables in the inner layer,with both influencing each other. To address this issue, first, a Mixed Integer Programming(MIP) model is proposed, which reformulates the original bilevel problem into a single-level optimization problem, enabling the exploration of a more comprehensive optimization space while avoiding iterative nested optimization. Then, to model the 3D geometric relationships between components within the MIP framework, a linearized 3D Phi-function method is proposed, which handles non-overlapping and safety distance constraints between cuboid components in an explicit and effective way. Subsequently, the Finite-Rectangle Method(FRM) is proposed to manage 3D geometric constraints for complex-shaped components by approximating them with a finite set of cuboids, extending the applicability of the geometric modeling approach. Finally, the feasibility and effectiveness of the proposed MIP model are demonstrated through two numerical examples"and a real-world engineering case, which confirms its suitability for complex-shaped components and real engineering applications.展开更多
Byproduct gas is an important secondary energy in iron and steel industry, and its optimization is vital to cost reduction. With the development of iron and steel industry to be more eco-friendly, it is necessary to c...Byproduct gas is an important secondary energy in iron and steel industry, and its optimization is vital to cost reduction. With the development of iron and steel industry to be more eco-friendly, it is necessary to construct an integrated optimized system, taking economics, energy consumption and environment into consideration. Therefore, the environmental cost caused by pollutants discharge should be factored in total cost when optimizing byproduct gas distribution. A green mixed integer linear programming （MILP） model for the optimization of byproduct gases was established to reduce total cost, including both operation cost and environmental cost. The operation cost included penalty for gas deviation, costs of fuel and water consumption, holder booster trip penalty, and so forth; while the environmental cost consisted of penalties for both direct and indirect pollutants discharge. Case study showed that the proposed model brought an optimum solution and 2.2% of the total cost could be reduced compared with previous one.展开更多
An integer linear bilevel programming problem is firstly transformed into a binary linear bilevel programming problem, and then converted into a single-level binary implicit programming. An orthogonal genetic algorith...An integer linear bilevel programming problem is firstly transformed into a binary linear bilevel programming problem, and then converted into a single-level binary implicit programming. An orthogonal genetic algorithm is developed for solving the binary linear implicit programming problem based on the orthogonal design. The orthogonal design with the factor analysis, an experimental design method is applied to the genetic algorithm to make the algorithm more robust, statistical y sound and quickly convergent. A crossover operator formed by the orthogonal array and the factor analysis is presented. First, this crossover operator can generate a smal but representative sample of points as offspring. After al of the better genes of these offspring are selected, a best combination among these offspring is then generated. The simulation results show the effectiveness of the proposed algorithm.展开更多
Two classes of mixed-integer nonlinear bilevel programming problems are discussed. One is that the follower＇s functions are separable with respect to the follower＇s variables, and the other is that the follower＇s f...Two classes of mixed-integer nonlinear bilevel programming problems are discussed. One is that the follower＇s functions are separable with respect to the follower＇s variables, and the other is that the follower＇s functions are convex if the follower＇s variables are not restricted to integers. A genetic algorithm based on an exponential distribution is proposed for the aforementioned problems. First, for each fixed leader＇s variable x, it is proved that the optimal solution y of the follower＇s mixed-integer programming can be obtained by solving associated relaxed problems, and according to the convexity of the functions involved, a simplified branch and bound approach is given to solve the follower＇s programming for the second class of problems. Furthermore, based on an exponential distribution with a parameter λ, a new crossover operator is designed in which the best individuals are used to generate better offspring of crossover. The simulation results illustrate that the proposed algorithm is efficient and robust.展开更多
Combined cycle plants (CCs) are broadly used all over the world. The inclusion of CCs into the optimal resource scheduling causes difficulties because they can be operated in different operating configuration modes ba...Combined cycle plants (CCs) are broadly used all over the world. The inclusion of CCs into the optimal resource scheduling causes difficulties because they can be operated in different operating configuration modes based on the number of combustion and steam turbines. In this paper a model CCs based on a mixed integer linear programming approach to be included into an optimal short term resource optimization problem is presented. The proposed method allows modeling of CCs in different modes of operation taking into account the non convex operating costs for the different combined cycle mode of operation.展开更多
In this study, we aimed to assess the solution quality for location-allocation problems from facilities generated by the software TransCAD®?, a Geographic Information System for Transportation (GIS-T). Such fa...In this study, we aimed to assess the solution quality for location-allocation problems from facilities generated by the software TransCAD®?, a Geographic Information System for Transportation (GIS-T). Such facilities were obtained after using two routines together: Facility Location and Transportation Problem, when compared with optimal solutions from exact mathematical models, based on Mixed Integer Linear Programming (MILP), developed externally for the GIS. The models were applied to three simulations: the first one proposes opening factories and customer allocation in the state of Sao Paulo, Brazil;the second involves a wholesaler and a study of location and allocation of distribution centres for retail customers;and the third one involves the location of day-care centers and allocation of demand (0 - 3 years old children). The results showed that when considering facility capacity, the MILP optimising model presents results up to 37% better than the GIS and proposes different locations to open new facilities.展开更多
Production scheduling has a major impact on the productivity of the manufacturing process. Recently, scheduling problems with deteriorating jobs have attracted increasing attentions from researchers. In many practical...Production scheduling has a major impact on the productivity of the manufacturing process. Recently, scheduling problems with deteriorating jobs have attracted increasing attentions from researchers. In many practical situations,it is found that some jobs fail to be processed prior to the pre-specified thresholds,and they often consume extra deteriorating time for successful accomplishment. Their processing times can be characterized by a step-wise function. Such kinds of jobs are called step-deteriorating jobs. In this paper,parallel machine scheduling problem with stepdeteriorating jobs( PMSD) is considered. Due to its intractability,four different mixed integer programming( MIP) models are formulated for solving the problem under consideration. The study aims to investigate the performance of these models and find promising optimization formulation to solve the largest possible problem instances. The proposed four models are solved by commercial software CPLEX. Moreover,the near-optimal solutions can be obtained by black-box local-search solver LocalS olver with the fourth one. The computational results show that the efficiencies of different MIP models depend on the distribution intervals of deteriorating thresholds, and the performance of LocalS olver is clearly better than that of CPLEX in terms of the quality of the solutions and the computational time.展开更多
The solar and wind renewable energy is developing very rapidly to fulfill the energy gap. This specific increasing share of renewable energy is a reaction to the ecological trepidations to conciliate economics with se...The solar and wind renewable energy is developing very rapidly to fulfill the energy gap. This specific increasing share of renewable energy is a reaction to the ecological trepidations to conciliate economics with security due to the new challenges in power system supply. In solar and wind renewable energy, the only partially predictable is the output with very low controllability which creates unit commitment problems in thermal units. In this research paper, a different linear formulation via mixed integer is presented that only requires “binary variables” and restraints concerning earlier stated models. The framework of this model allows precisely the costs of time-dependent startup & intertemporal limitations, for example, minimum up & down times and a ramping limit. To solve the unit commitment problem efficiently, a commercially available linear programming of mixed-integer is applied for sizeable practical scale. The results of the simulation are shown in conclusions.展开更多
A novel mixed integer linear programming (NMILP) model for detection of gross errors is presented in this paper. Yamamura et al.(1988) designed a model for detection of gross errors and data reconciliation based on Ak...A novel mixed integer linear programming (NMILP) model for detection of gross errors is presented in this paper. Yamamura et al.(1988) designed a model for detection of gross errors and data reconciliation based on Akaike information cri- terion (AIC). But much computational cost is needed due to its combinational nature. A mixed integer linear programming (MILP) approach was performed to reduce the computational cost and enhance the robustness. But it loses the super performance of maximum likelihood estimation. To reduce the computational cost and have the merit of maximum likelihood estimation, the simultaneous data reconciliation method in an MILP framework is decomposed and replaced by an NMILP subproblem and a quadratic programming (QP) or a least squares estimation (LSE) subproblem. Simulation result of an industrial case shows the high efficiency of the method.展开更多
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.展开更多
The flexible job shop scheduling problem(FJSP)is commonly encountered in practical manufacturing environments.A product is typically built by assembling multiple jobs during actual manufacturing.AGVs are normally used...The flexible job shop scheduling problem(FJSP)is commonly encountered in practical manufacturing environments.A product is typically built by assembling multiple jobs during actual manufacturing.AGVs are normally used to transport the jobs from the processing shop to the assembly shop,where they are assembled.Therefore,studying the integrated scheduling problem with its processing,transportation,and assembly stages is extremely beneficial and significant.This research studies the three-stage flexible job shop scheduling problem with assembly and AGV transportation(FJSP-T-A),which includes processing jobs,transporting them via AGVs,and assembling them.A mixed integer linear programming(MILP)model is established to obtain optimal solutions.As the MILP model is challenging for solving large-scale problems,a novel co-evolutionary algorithm(NCEA)with two different decoding methods is proposed.In NCEA,a restart operation is developed to improve the diversity of the population,and a multiple crossover strategy is designed to improve the quality of individuals.The validity of the MILP model is proven by analyzing its complexity.The effectiveness of the restart operator,multiple crossovers,and the proposed algorithm is demonstrated by calculating and analyzing the RPI values of each algorithm's results within the time limit and performing a paired t-test on the average values of each algorithm at the 95%confidence level.This paper studies FJSP-T-A by minimizing the makespan for the first time,and presents a MILP model and an NCEA with two different decoding methods.展开更多
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.展开更多
Finding the accurate solution for N-vehicle exploration problem is NP-hard in strong sense.In this paper,authors build a linear mixed integer programming model for N-vehicle exploration problem based on its properties...Finding the accurate solution for N-vehicle exploration problem is NP-hard in strong sense.In this paper,authors build a linear mixed integer programming model for N-vehicle exploration problem based on its properties.The model is then proved equivalent to the original problem.Given the model,one can apply the already existed methods and algorithms for mixed integer linear programming on N-vehicle exploration problem,which helps to enrich methods for solving N-vehicle exploration problem.展开更多
基金supported by the National Natural Science Foundation of China(No.92371206)the Postgraduate Scientific Research Innovation Project of Hunan Province,China(No.CX2023063).
文摘Satellite Component Layout Optimization(SCLO) is crucial in satellite system design.This paper proposes a novel Satellite Three-Dimensional Component Assignment and Layout Optimization(3D-SCALO) problem tailored to engineering requirements, aiming to optimize satellite heat dissipation while considering constraints on static stability, 3D geometric relationships between components, and special component positions. The 3D-SCALO problem is a challenging bilevel combinatorial optimization task, involving the optimization of discrete component assignment variables in the outer layer and continuous component position variables in the inner layer,with both influencing each other. To address this issue, first, a Mixed Integer Programming(MIP) model is proposed, which reformulates the original bilevel problem into a single-level optimization problem, enabling the exploration of a more comprehensive optimization space while avoiding iterative nested optimization. Then, to model the 3D geometric relationships between components within the MIP framework, a linearized 3D Phi-function method is proposed, which handles non-overlapping and safety distance constraints between cuboid components in an explicit and effective way. Subsequently, the Finite-Rectangle Method(FRM) is proposed to manage 3D geometric constraints for complex-shaped components by approximating them with a finite set of cuboids, extending the applicability of the geometric modeling approach. Finally, the feasibility and effectiveness of the proposed MIP model are demonstrated through two numerical examples"and a real-world engineering case, which confirms its suitability for complex-shaped components and real engineering applications.
基金Sponsored by Beijing Social Science Foundation of China(14JGC110)Social Science Research Common Program of Beijing Municipal Commission of Education of China(SM201510038011)CUEB Foundation of China(2014XJG005)
文摘Byproduct gas is an important secondary energy in iron and steel industry, and its optimization is vital to cost reduction. With the development of iron and steel industry to be more eco-friendly, it is necessary to construct an integrated optimized system, taking economics, energy consumption and environment into consideration. Therefore, the environmental cost caused by pollutants discharge should be factored in total cost when optimizing byproduct gas distribution. A green mixed integer linear programming （MILP） model for the optimization of byproduct gases was established to reduce total cost, including both operation cost and environmental cost. The operation cost included penalty for gas deviation, costs of fuel and water consumption, holder booster trip penalty, and so forth; while the environmental cost consisted of penalties for both direct and indirect pollutants discharge. Case study showed that the proposed model brought an optimum solution and 2.2% of the total cost could be reduced compared with previous one.
基金supported by the Fundamental Research Funds for the Central Universities(K50511700004)the Natural Science Basic Research Plan in Shaanxi Province of China(2013JM1022)
文摘An integer linear bilevel programming problem is firstly transformed into a binary linear bilevel programming problem, and then converted into a single-level binary implicit programming. An orthogonal genetic algorithm is developed for solving the binary linear implicit programming problem based on the orthogonal design. The orthogonal design with the factor analysis, an experimental design method is applied to the genetic algorithm to make the algorithm more robust, statistical y sound and quickly convergent. A crossover operator formed by the orthogonal array and the factor analysis is presented. First, this crossover operator can generate a smal but representative sample of points as offspring. After al of the better genes of these offspring are selected, a best combination among these offspring is then generated. The simulation results show the effectiveness of the proposed algorithm.
基金supported by the National Natural Science Fundation of China (60374063)
文摘Two classes of mixed-integer nonlinear bilevel programming problems are discussed. One is that the follower＇s functions are separable with respect to the follower＇s variables, and the other is that the follower＇s functions are convex if the follower＇s variables are not restricted to integers. A genetic algorithm based on an exponential distribution is proposed for the aforementioned problems. First, for each fixed leader＇s variable x, it is proved that the optimal solution y of the follower＇s mixed-integer programming can be obtained by solving associated relaxed problems, and according to the convexity of the functions involved, a simplified branch and bound approach is given to solve the follower＇s programming for the second class of problems. Furthermore, based on an exponential distribution with a parameter λ, a new crossover operator is designed in which the best individuals are used to generate better offspring of crossover. The simulation results illustrate that the proposed algorithm is efficient and robust.
文摘Combined cycle plants (CCs) are broadly used all over the world. The inclusion of CCs into the optimal resource scheduling causes difficulties because they can be operated in different operating configuration modes based on the number of combustion and steam turbines. In this paper a model CCs based on a mixed integer linear programming approach to be included into an optimal short term resource optimization problem is presented. The proposed method allows modeling of CCs in different modes of operation taking into account the non convex operating costs for the different combined cycle mode of operation.
文摘In this study, we aimed to assess the solution quality for location-allocation problems from facilities generated by the software TransCAD®?, a Geographic Information System for Transportation (GIS-T). Such facilities were obtained after using two routines together: Facility Location and Transportation Problem, when compared with optimal solutions from exact mathematical models, based on Mixed Integer Linear Programming (MILP), developed externally for the GIS. The models were applied to three simulations: the first one proposes opening factories and customer allocation in the state of Sao Paulo, Brazil;the second involves a wholesaler and a study of location and allocation of distribution centres for retail customers;and the third one involves the location of day-care centers and allocation of demand (0 - 3 years old children). The results showed that when considering facility capacity, the MILP optimising model presents results up to 37% better than the GIS and proposes different locations to open new facilities.
基金National Natural Science Foundation of China(No.51405403)the Fundamental Research Funds for the Central Universities,China(No.2682014BR019)the Scientific Research Program of Education Bureau of Sichuan Province,China(No.12ZB322)
文摘Production scheduling has a major impact on the productivity of the manufacturing process. Recently, scheduling problems with deteriorating jobs have attracted increasing attentions from researchers. In many practical situations,it is found that some jobs fail to be processed prior to the pre-specified thresholds,and they often consume extra deteriorating time for successful accomplishment. Their processing times can be characterized by a step-wise function. Such kinds of jobs are called step-deteriorating jobs. In this paper,parallel machine scheduling problem with stepdeteriorating jobs( PMSD) is considered. Due to its intractability,four different mixed integer programming( MIP) models are formulated for solving the problem under consideration. The study aims to investigate the performance of these models and find promising optimization formulation to solve the largest possible problem instances. The proposed four models are solved by commercial software CPLEX. Moreover,the near-optimal solutions can be obtained by black-box local-search solver LocalS olver with the fourth one. The computational results show that the efficiencies of different MIP models depend on the distribution intervals of deteriorating thresholds, and the performance of LocalS olver is clearly better than that of CPLEX in terms of the quality of the solutions and the computational time.
文摘The solar and wind renewable energy is developing very rapidly to fulfill the energy gap. This specific increasing share of renewable energy is a reaction to the ecological trepidations to conciliate economics with security due to the new challenges in power system supply. In solar and wind renewable energy, the only partially predictable is the output with very low controllability which creates unit commitment problems in thermal units. In this research paper, a different linear formulation via mixed integer is presented that only requires “binary variables” and restraints concerning earlier stated models. The framework of this model allows precisely the costs of time-dependent startup & intertemporal limitations, for example, minimum up & down times and a ramping limit. To solve the unit commitment problem efficiently, a commercially available linear programming of mixed-integer is applied for sizeable practical scale. The results of the simulation are shown in conclusions.
基金Project supported by the National Creative Research Groups Science Foundation of China (No. 60421002)the National "Tenth Five-Year" Science and Technology Research Program of China (No.2004BA204B08)
文摘A novel mixed integer linear programming (NMILP) model for detection of gross errors is presented in this paper. Yamamura et al.(1988) designed a model for detection of gross errors and data reconciliation based on Akaike information cri- terion (AIC). But much computational cost is needed due to its combinational nature. A mixed integer linear programming (MILP) approach was performed to reduce the computational cost and enhance the robustness. But it loses the super performance of maximum likelihood estimation. To reduce the computational cost and have the merit of maximum likelihood estimation, the simultaneous data reconciliation method in an MILP framework is decomposed and replaced by an NMILP subproblem and a quadratic programming (QP) or a least squares estimation (LSE) subproblem. Simulation result of an industrial case shows the high efficiency of the method.
文摘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.
基金Supported by National Natural Science Foundation of China(Grant Nos.52205529 and 62303204)the Youth Innovation Team Program of Shandong Higher Education Institution(Grant No.2023KJ206)the Guangyue Youth Scholar Innovation Talent Program support received from Liaocheng University(Grant No.LCUGYTD2022-03)。
文摘The flexible job shop scheduling problem(FJSP)is commonly encountered in practical manufacturing environments.A product is typically built by assembling multiple jobs during actual manufacturing.AGVs are normally used to transport the jobs from the processing shop to the assembly shop,where they are assembled.Therefore,studying the integrated scheduling problem with its processing,transportation,and assembly stages is extremely beneficial and significant.This research studies the three-stage flexible job shop scheduling problem with assembly and AGV transportation(FJSP-T-A),which includes processing jobs,transporting them via AGVs,and assembling them.A mixed integer linear programming(MILP)model is established to obtain optimal solutions.As the MILP model is challenging for solving large-scale problems,a novel co-evolutionary algorithm(NCEA)with two different decoding methods is proposed.In NCEA,a restart operation is developed to improve the diversity of the population,and a multiple crossover strategy is designed to improve the quality of individuals.The validity of the MILP model is proven by analyzing its complexity.The effectiveness of the restart operator,multiple crossovers,and the proposed algorithm is demonstrated by calculating and analyzing the RPI values of each algorithm's results within the time limit and performing a paired t-test on the average values of each algorithm at the 95%confidence level.This paper studies FJSP-T-A by minimizing the makespan for the first time,and presents a MILP model and an NCEA with two different decoding methods.
文摘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.
文摘Finding the accurate solution for N-vehicle exploration problem is NP-hard in strong sense.In this paper,authors build a linear mixed integer programming model for N-vehicle exploration problem based on its properties.The model is then proved equivalent to the original problem.Given the model,one can apply the already existed methods and algorithms for mixed integer linear programming on N-vehicle exploration problem,which helps to enrich methods for solving N-vehicle exploration problem.
