In this paper,quadratic 0-1 programming problem (I) is considered, in terms of its features quadratic 0-1 programming problem is solved by linear approxity heurstic algrothm and a developed tabu search ahgrothm .
Quadratic 0-1 problems with linear inequality constraints are briefly considered in this paper.Global optimality conditions for these problems,including a necessary condition and some sufficient conditions,are present...Quadratic 0-1 problems with linear inequality constraints are briefly considered in this paper.Global optimality conditions for these problems,including a necessary condition and some sufficient conditions,are presented.The necessary condition is expressed without dual variables.The relations between the global optimal solutions of nonconvex quadratic 0-1 problems and the associated relaxed convex problems are also studied.展开更多
In this paper, we consider the socalled k-coloring problem in general case.Firstly, a special quadratic 0-1 programming is constructed to formulate k-coloring problem. Secondly, by use of the equivalence between above...In this paper, we consider the socalled k-coloring problem in general case.Firstly, a special quadratic 0-1 programming is constructed to formulate k-coloring problem. Secondly, by use of the equivalence between above quadratic0-1 programming and its relaxed problem, k-coloring problem is converted intoa class of (continuous) nonconvex quadratic programs, and several theoreticresults are also introduced. Thirdly, linear programming approximate algorithmis quoted and verified for this class of nonconvex quadratic programs. Finally,examining problems which are used to test the algorithm are constructed andsufficient computation experiments are reported.展开更多
It is well known that general 0-1 programming problems are NP-Complete and their optimal solutions cannot be found with polynomial-time algorithms unless P=NP. In this paper, we identify a specific class of 0-1 progra...It is well known that general 0-1 programming problems are NP-Complete and their optimal solutions cannot be found with polynomial-time algorithms unless P=NP. In this paper, we identify a specific class of 0-1 programming problems that is polynomially solvable, and propose two polynomial-time algorithms to find its optimal solutions. This class of 0-1 programming problems commits to a wide range of real-world industrial applications. We provide an instance of representative in the field of supply chain management.展开更多
A 0-1 integer programming model for weekly fleet assignment was put forward based on linear network and weekly flight scheduling in China. In this model, the objective function is to maximize the total profit of fleet...A 0-1 integer programming model for weekly fleet assignment was put forward based on linear network and weekly flight scheduling in China. In this model, the objective function is to maximize the total profit of fleet assignment, subject to the constraints of coverage, aircraft flow balance, fleet size, aircraft availability, aircraft usage, flight restriction, aircraft seat capacity, and stopover. Then the branch-and-bound algorithm based on special ordered set was applied to solve the model. At last, a real- wofld case study on an airline with 5 fleets, 48 aircrafts and 1 786 flight legs indicated that the profit increase was ￥ 1 591276 one week and the running time was no more than 4 rain, which shows that the model and algorithm are fairly good for domestic airline.展开更多
On the foundation of analyzing the closed loop logistics chain of product with multi-lifecycle, the connotation of environmental value is set forth, recurring to such conceptions as supply chain and value chain. The p...On the foundation of analyzing the closed loop logistics chain of product with multi-lifecycle, the connotation of environmental value is set forth, recurring to such conceptions as supply chain and value chain. The plotting rules about disassembly tree are discussed in detail. The reachable matrix R of components’ disas- sembly is introduced into distinguishing if disassembly is needed, in combination with disassembly-deciding vector X. Furthermore, the arithmetic of disassembly cost is put forward. And the cost-benefits of components’ reusing, materials’ recycling, safety disposing are dissertated based on the activity-based costing. Then the 0-1 goal-programming model on product recovery processing is established, with components’ demotion calculated. In addition, taking the PC’s recovery processing for example, we put it into application.展开更多
In this paper, the open queueing network model is proposed for solving the problem of public transportation in cities. The vertices of the networks(i.e., the bus stops) are determined by means of the fuzzy clusteri...In this paper, the open queueing network model is proposed for solving the problem of public transportation in cities. The vertices of the networks(i.e., the bus stops) are determined by means of the fuzzy clustering method. The arcs (i.e., the paths of the public transportation) can be set up by using the shortest path model in the time sense or the 0 1 integer programming method.Applying the statistics method, we can calculate the parameters(such as the passenger flow's distribution, passenger flow's transition probability, mean waiting time for the bus etc. ) of the public transportation network. In this paper, we suggest to divide the network into two or three stages to implement the public transportation system in the form of ``frog jumping' fast transfer and ``permeation' fast dispersion.Combining the computer simulation and the evaluation of the achievement and effect of public transportation system, we modify the model so as to solve the public transportation problem better.展开更多
Logistics network design influences the efficiency and cost of Logistics directly.Some manufacturing enterprises not only have warehouse hubs,but also build component processing workshops which are usually located in ...Logistics network design influences the efficiency and cost of Logistics directly.Some manufacturing enterprises not only have warehouse hubs,but also build component processing workshops which are usually located in those places where the costs of materials and workforce are lower.This paper establishes a logistics network design model for the manufacturing enterprises with component processing workshops based on 0-1 mixture integer programming.The model optimizes the logistics network in an integrated view,by which the selection of the nodes,the manufacturing plan,and transportation plan can be obtained.An example is given to verify its feasibility.The approach is helpful for designing of the logistics network in manufacturing enterprises.展开更多
This paper presents the formulation and solution of a train routing and makeupmodel.This formulation results in a large scale 0-1 integer programmingproblem with nonlinear objective function, and linear and nonlinearc...This paper presents the formulation and solution of a train routing and makeupmodel.This formulation results in a large scale 0-1 integer programmingproblem with nonlinear objective function, and linear and nonlinearcoastraints. We know this problem is NP-complete;hence,it is diffieult to solvefor a globelly optimal solution. In this paper we propose a simulated annealingalgorithm for the train routing and makeup problem. This method avoidsentrapment in the local minima of the objective function. The effectiveness ofthis approach has been demonstrasted by results from test casee,展开更多
Mathematical programming problems with semi-continuous variables and cardinality constraint have many applications,including production planning,portfolio selection,compressed sensing and subset selection in regressio...Mathematical programming problems with semi-continuous variables and cardinality constraint have many applications,including production planning,portfolio selection,compressed sensing and subset selection in regression.This class of problems can be modeled as mixed-integer programs with special structures and are in general NP-hard.In the past few years,based on new reformulations,approximation and relaxation techniques,promising exact and approximate methods have been developed.We survey in this paper these recent developments for this challenging class of mathematical programming problems.展开更多
This paper proposed the optimized three-stage strategy of orderly management of file stream in network printing workflow. In first stage the customer preflight was added to the conventional prepress preflight, which s...This paper proposed the optimized three-stage strategy of orderly management of file stream in network printing workflow. In first stage the customer preflight was added to the conventional prepress preflight, which set quick-type, general-type, stable-type and comprehensive-type preflight scheme for customers by investigating the possibility of occurrence of errors of various preflight entries and customer relevancy. Based on four types of preflight schemes, four customer preflight applications were created by using Pitstop Pro and Connector You. Customers can select one of the appropriate applications for quick preflight before delivering to reduce the probability of returning the files back for correction when errors occur in preflight. Second stage is printing enterprise prepress preflight,which proposed the concept of the prepress preflight tolerance. In addition, according to the different requirements of printing technology and quality, this paper established the prepress preflight scheme based on the printing enterprises’ tolerance for preflight error. Third stage is to manage the optimized sorting of prepress file stream. To achieve it, the SPT rule and the 0-1 programming model were adopted, time spend of preflight, printing process and post-press finishing was also taken into account.Moreover, Enfocus Switch software was applied to establish automated network printing workflow and complete the file stream sorting. Finally, the result of simulation analysis of the optimized strategy shows that the optimized three-stage strategy can effectively shorten the file processing time.展开更多
文摘In this paper,quadratic 0-1 programming problem (I) is considered, in terms of its features quadratic 0-1 programming problem is solved by linear approxity heurstic algrothm and a developed tabu search ahgrothm .
文摘Quadratic 0-1 problems with linear inequality constraints are briefly considered in this paper.Global optimality conditions for these problems,including a necessary condition and some sufficient conditions,are presented.The necessary condition is expressed without dual variables.The relations between the global optimal solutions of nonconvex quadratic 0-1 problems and the associated relaxed convex problems are also studied.
文摘In this paper, we consider the socalled k-coloring problem in general case.Firstly, a special quadratic 0-1 programming is constructed to formulate k-coloring problem. Secondly, by use of the equivalence between above quadratic0-1 programming and its relaxed problem, k-coloring problem is converted intoa class of (continuous) nonconvex quadratic programs, and several theoreticresults are also introduced. Thirdly, linear programming approximate algorithmis quoted and verified for this class of nonconvex quadratic programs. Finally,examining problems which are used to test the algorithm are constructed andsufficient computation experiments are reported.
基金supported by National Natural Science Foundation of China (Grant Nos.70471008, 70971072)
文摘It is well known that general 0-1 programming problems are NP-Complete and their optimal solutions cannot be found with polynomial-time algorithms unless P=NP. In this paper, we identify a specific class of 0-1 programming problems that is polynomially solvable, and propose two polynomial-time algorithms to find its optimal solutions. This class of 0-1 programming problems commits to a wide range of real-world industrial applications. We provide an instance of representative in the field of supply chain management.
基金The National Natural Science Foundationof China (70473037)
文摘A 0-1 integer programming model for weekly fleet assignment was put forward based on linear network and weekly flight scheduling in China. In this model, the objective function is to maximize the total profit of fleet assignment, subject to the constraints of coverage, aircraft flow balance, fleet size, aircraft availability, aircraft usage, flight restriction, aircraft seat capacity, and stopover. Then the branch-and-bound algorithm based on special ordered set was applied to solve the model. At last, a real- wofld case study on an airline with 5 fleets, 48 aircrafts and 1 786 flight legs indicated that the profit increase was ￥ 1 591276 one week and the running time was no more than 4 rain, which shows that the model and algorithm are fairly good for domestic airline.
基金Supported by the National Natural Science Foundation of China(No.70472080)and Shanghai Shuguang Planning Program(No.70472080).
文摘On the foundation of analyzing the closed loop logistics chain of product with multi-lifecycle, the connotation of environmental value is set forth, recurring to such conceptions as supply chain and value chain. The plotting rules about disassembly tree are discussed in detail. The reachable matrix R of components’ disas- sembly is introduced into distinguishing if disassembly is needed, in combination with disassembly-deciding vector X. Furthermore, the arithmetic of disassembly cost is put forward. And the cost-benefits of components’ reusing, materials’ recycling, safety disposing are dissertated based on the activity-based costing. Then the 0-1 goal-programming model on product recovery processing is established, with components’ demotion calculated. In addition, taking the PC’s recovery processing for example, we put it into application.
文摘In this paper, the open queueing network model is proposed for solving the problem of public transportation in cities. The vertices of the networks(i.e., the bus stops) are determined by means of the fuzzy clustering method. The arcs (i.e., the paths of the public transportation) can be set up by using the shortest path model in the time sense or the 0 1 integer programming method.Applying the statistics method, we can calculate the parameters(such as the passenger flow's distribution, passenger flow's transition probability, mean waiting time for the bus etc. ) of the public transportation network. In this paper, we suggest to divide the network into two or three stages to implement the public transportation system in the form of ``frog jumping' fast transfer and ``permeation' fast dispersion.Combining the computer simulation and the evaluation of the achievement and effect of public transportation system, we modify the model so as to solve the public transportation problem better.
基金Supported by the National High Technology Research and Development Program of China (863 Program) (2007AA04Z105)the Innovation Action Project from Science and Technology Commission of Shanghai Municipality (08170511300)
文摘Logistics network design influences the efficiency and cost of Logistics directly.Some manufacturing enterprises not only have warehouse hubs,but also build component processing workshops which are usually located in those places where the costs of materials and workforce are lower.This paper establishes a logistics network design model for the manufacturing enterprises with component processing workshops based on 0-1 mixture integer programming.The model optimizes the logistics network in an integrated view,by which the selection of the nodes,the manufacturing plan,and transportation plan can be obtained.An example is given to verify its feasibility.The approach is helpful for designing of the logistics network in manufacturing enterprises.
文摘This paper presents the formulation and solution of a train routing and makeupmodel.This formulation results in a large scale 0-1 integer programmingproblem with nonlinear objective function, and linear and nonlinearcoastraints. We know this problem is NP-complete;hence,it is diffieult to solvefor a globelly optimal solution. In this paper we propose a simulated annealingalgorithm for the train routing and makeup problem. This method avoidsentrapment in the local minima of the objective function. The effectiveness ofthis approach has been demonstrasted by results from test casee,
基金supported by the National Natural Science Foundation of China grants(Nos.11101092,10971034)the Joint National Natural Science Foundation of China/Research Grants Council of Hong Kong grant(No.71061160506)the Research Grants Council of Hong Kong grants(Nos.CUHK414808 and CUHK414610).
文摘Mathematical programming problems with semi-continuous variables and cardinality constraint have many applications,including production planning,portfolio selection,compressed sensing and subset selection in regression.This class of problems can be modeled as mixed-integer programs with special structures and are in general NP-hard.In the past few years,based on new reformulations,approximation and relaxation techniques,promising exact and approximate methods have been developed.We survey in this paper these recent developments for this challenging class of mathematical programming problems.
基金Supported by Science and Technology Industry Trade and Information Bureau of Zhuhai City(2011B050102013and 2012D050199033)by Education Bureau of Zhuhai City(Premier-Discipline Enhancement Scheme of Packaging Engineering and Premier-Key Laboratory of Products Packaging and Logistics)
文摘This paper proposed the optimized three-stage strategy of orderly management of file stream in network printing workflow. In first stage the customer preflight was added to the conventional prepress preflight, which set quick-type, general-type, stable-type and comprehensive-type preflight scheme for customers by investigating the possibility of occurrence of errors of various preflight entries and customer relevancy. Based on four types of preflight schemes, four customer preflight applications were created by using Pitstop Pro and Connector You. Customers can select one of the appropriate applications for quick preflight before delivering to reduce the probability of returning the files back for correction when errors occur in preflight. Second stage is printing enterprise prepress preflight,which proposed the concept of the prepress preflight tolerance. In addition, according to the different requirements of printing technology and quality, this paper established the prepress preflight scheme based on the printing enterprises’ tolerance for preflight error. Third stage is to manage the optimized sorting of prepress file stream. To achieve it, the SPT rule and the 0-1 programming model were adopted, time spend of preflight, printing process and post-press finishing was also taken into account.Moreover, Enfocus Switch software was applied to establish automated network printing workflow and complete the file stream sorting. Finally, the result of simulation analysis of the optimized strategy shows that the optimized three-stage strategy can effectively shorten the file processing time.
