Multi-dimensional nonlinear knapsack problem is a bounded nonlinear integer programming problem that maximizes a separable nondecreasing function subject to multiple separable nondecreasing constraints. This problem i...Multi-dimensional nonlinear knapsack problem is a bounded nonlinear integer programming problem that maximizes a separable nondecreasing function subject to multiple separable nondecreasing constraints. This problem is often encountered in resource allocation, industrial planning and computer network. In this paper, a new convergent Lagrangian dual method was proposed for solving this problem. Cutting plane method was used to solve the dual problem and to compute the Lagrangian bounds of the primal problem. In order to eliminate the duality gap and thus to guarantee the convergence of the algorithm, domain cut technique was employed to remove certain integer boxes and partition the revised domain to a union of integer boxes. Extensive computational results show that the proposed method is efficient for solving large-scale multi-dimensional nonlinear knapsack problems. Our numerical results also indicate that the cutting plane method significantly outperforms the subgradient method as a dual search procedure.展开更多
Concave resource allocation problem is an integer programming problem of minimizing a nonincreasing concave function subject to a convex nondecreasing constraint and bounded integer variables. This class of problems a...Concave resource allocation problem is an integer programming problem of minimizing a nonincreasing concave function subject to a convex nondecreasing constraint and bounded integer variables. This class of problems are encountered in optimization models involving economies of scale. In this paper, a new hybrid dynamic programming method was proposed for solving concave resource allocation problems. A convex underestimating function was used to approximate the objective function and the resulting convex subproblem was solved with dynamic programming technique after transforming it into a 0-1 linear knapsack problem. To ensure the convergence, monotonicity and domain cut technique was employed to remove certain integer boxes and partition the revised domain into a union of integer boxes. Computational results were given to show the efficiency of the algorithm.展开更多
In this paper, a new method named as the gradually descent method was proposed to solve the discrete global optimization problem. With the aid of an auxiliary function, this method enables to convert the problem of fi...In this paper, a new method named as the gradually descent method was proposed to solve the discrete global optimization problem. With the aid of an auxiliary function, this method enables to convert the problem of finding one discrete minimizer of the objective function f to that of finding another at each cycle. The auxiliary function can ensure that a point, except a prescribed point, is not its integer stationary point if the value of objective function at the point is greater than the scalar which is chosen properly. This property leads to a better minimizer of f found more easily by some classical local search methods. The computational results show that this algorithm is quite efficient and reliable for solving nonlinear integer programming problems.展开更多
Component reallocation(CR)is receiving increasing attention in many engineering systems with functionally interchangeable and unbalanced degradation components.This paper studies a CR and system replacement maintenanc...Component reallocation(CR)is receiving increasing attention in many engineering systems with functionally interchangeable and unbalanced degradation components.This paper studies a CR and system replacement maintenance policy of series repairable systems,which undergoes minimal repairs for each emergency failure of components,and considers constant downtime and cost of minimal repair,CR and system replacement.Two binary mixed integer nonlinear programming models are respectively established to determine the assignment of CR,and the uptime right before CR and system replacement with the objective of minimizing the system average maintenance cost and maximizing the system availability.Further,we derive the optimal uptime right before system replacement with maximization of the system availability,and then give the relationship between the system availability and the component failure rate.Finally,numerical examples show that the CR and system replacement maintenance policy can effectively reduce the system average maintenance cost and improve the system availability,and further give the sensitivity analysis and insights of the CR and system replacement maintenance policy.展开更多
In a medium-term electricity market,in order to reduce the risks of price and inflow uncertainties, the cascade hydropower stations may use the options contract with electricity supply companies. A profit-based model ...In a medium-term electricity market,in order to reduce the risks of price and inflow uncertainties, the cascade hydropower stations may use the options contract with electricity supply companies. A profit-based model for risk management of cascade hydropower stations in the medium-term electricity market is presented. The objective function is profit maximization of cascade hydropower stations. In order to avoid the risks of price and inflow uncertainties, two different risk-aversion constraints: a minimum profit constraint and a minimum conditional value-at-risk, are introduced in the model. In addition, the model takes into account technology constraints of the generating units, which includes reservoir flow balance, reservoir capacity limits, water discharge constraints, etc. The model is formulated as a mixed integer nonlinear programming problem. Because the search space of the solution is very large, a genetic algorithm is used to deal with the problem.展开更多
This paper considers discrete global optimization problems.The traditional definition of the discrete filled function is modified in this paper.Based on the modified definition,a new discrete filled function is presen...This paper considers discrete global optimization problems.The traditional definition of the discrete filled function is modified in this paper.Based on the modified definition,a new discrete filled function is presented and an algorithm for discrete global optimization is developed from the discrete filled function.Numerical experiments reported in this paper on several test problems with up to 200 variables have demonstrated the efficiency of the algorithm.展开更多
In this paper,a new transformation function was proposed for finding global minimizer of discrete optimization problems.We proved that under some general assumptions the new transformation function possesses the prope...In this paper,a new transformation function was proposed for finding global minimizer of discrete optimization problems.We proved that under some general assumptions the new transformation function possesses the properties of both the tunneling functions and the filled functions.Only one parameter was included in the proposed function,and it can be adjusted easily in the realization.Numerical results demonstrate the effectiveness of the proposed method.展开更多
文摘Multi-dimensional nonlinear knapsack problem is a bounded nonlinear integer programming problem that maximizes a separable nondecreasing function subject to multiple separable nondecreasing constraints. This problem is often encountered in resource allocation, industrial planning and computer network. In this paper, a new convergent Lagrangian dual method was proposed for solving this problem. Cutting plane method was used to solve the dual problem and to compute the Lagrangian bounds of the primal problem. In order to eliminate the duality gap and thus to guarantee the convergence of the algorithm, domain cut technique was employed to remove certain integer boxes and partition the revised domain to a union of integer boxes. Extensive computational results show that the proposed method is efficient for solving large-scale multi-dimensional nonlinear knapsack problems. Our numerical results also indicate that the cutting plane method significantly outperforms the subgradient method as a dual search procedure.
基金Project supported by the National Natural Science Foundation oChina (Grant os.79970107 and 10271073)
文摘Concave resource allocation problem is an integer programming problem of minimizing a nonincreasing concave function subject to a convex nondecreasing constraint and bounded integer variables. This class of problems are encountered in optimization models involving economies of scale. In this paper, a new hybrid dynamic programming method was proposed for solving concave resource allocation problems. A convex underestimating function was used to approximate the objective function and the resulting convex subproblem was solved with dynamic programming technique after transforming it into a 0-1 linear knapsack problem. To ensure the convergence, monotonicity and domain cut technique was employed to remove certain integer boxes and partition the revised domain into a union of integer boxes. Computational results were given to show the efficiency of the algorithm.
基金Project supported by the National Natural Science Foundation of China(Grant No.10271073)
文摘In this paper, a new method named as the gradually descent method was proposed to solve the discrete global optimization problem. With the aid of an auxiliary function, this method enables to convert the problem of finding one discrete minimizer of the objective function f to that of finding another at each cycle. The auxiliary function can ensure that a point, except a prescribed point, is not its integer stationary point if the value of objective function at the point is greater than the scalar which is chosen properly. This property leads to a better minimizer of f found more easily by some classical local search methods. The computational results show that this algorithm is quite efficient and reliable for solving nonlinear integer programming problems.
基金supported by the National Natural Science Foundation of China(72101025,72271049)the Fundamental Research Funds for the Central Universities(FRF-TP-20-073A1)the China Postdoct oral Science Foundation(2021M690349)。
文摘Component reallocation(CR)is receiving increasing attention in many engineering systems with functionally interchangeable and unbalanced degradation components.This paper studies a CR and system replacement maintenance policy of series repairable systems,which undergoes minimal repairs for each emergency failure of components,and considers constant downtime and cost of minimal repair,CR and system replacement.Two binary mixed integer nonlinear programming models are respectively established to determine the assignment of CR,and the uptime right before CR and system replacement with the objective of minimizing the system average maintenance cost and maximizing the system availability.Further,we derive the optimal uptime right before system replacement with maximization of the system availability,and then give the relationship between the system availability and the component failure rate.Finally,numerical examples show that the CR and system replacement maintenance policy can effectively reduce the system average maintenance cost and improve the system availability,and further give the sensitivity analysis and insights of the CR and system replacement maintenance policy.
基金The National Natural Science Foundation of China (No.50579101)
文摘In a medium-term electricity market,in order to reduce the risks of price and inflow uncertainties, the cascade hydropower stations may use the options contract with electricity supply companies. A profit-based model for risk management of cascade hydropower stations in the medium-term electricity market is presented. The objective function is profit maximization of cascade hydropower stations. In order to avoid the risks of price and inflow uncertainties, two different risk-aversion constraints: a minimum profit constraint and a minimum conditional value-at-risk, are introduced in the model. In addition, the model takes into account technology constraints of the generating units, which includes reservoir flow balance, reservoir capacity limits, water discharge constraints, etc. The model is formulated as a mixed integer nonlinear programming problem. Because the search space of the solution is very large, a genetic algorithm is used to deal with the problem.
基金This work was supported by the National Natural Science Foundation of China(No.11471062)Ningxia Foundation for Key Disciplines of Computational Mathematics.
文摘This paper considers discrete global optimization problems.The traditional definition of the discrete filled function is modified in this paper.Based on the modified definition,a new discrete filled function is presented and an algorithm for discrete global optimization is developed from the discrete filled function.Numerical experiments reported in this paper on several test problems with up to 200 variables have demonstrated the efficiency of the algorithm.
基金the National Natural Science Foundation of China(Nos.11471102 and 10971053).
文摘In this paper,a new transformation function was proposed for finding global minimizer of discrete optimization problems.We proved that under some general assumptions the new transformation function possesses the properties of both the tunneling functions and the filled functions.Only one parameter was included in the proposed function,and it can be adjusted easily in the realization.Numerical results demonstrate the effectiveness of the proposed method.