In this paper, a branch-and-bound method for solving multi-dimensional quadratic 0-1 knapsack problems was studied. The method was based on the Lagrangian relaxation and the surrogate constraint technique for finding ...In this paper, a branch-and-bound method for solving multi-dimensional quadratic 0-1 knapsack problems was studied. The method was based on the Lagrangian relaxation and the surrogate constraint technique for finding feasible solutions. The Lagrangian relaxations were solved with the maximum-flow algorithm and the Lagrangian bounds was determined with the outer approximation method. Computational results show the efficiency of the proposed method for multi-dimensional quadratic 0-1 knapsack problems.展开更多
Generally, the procedure for Solving Security constrained unit commitment (SCUC) problems within Lagrangian Relaxation framework is partitioned into two stages: one is to obtain feasible SCUC states;the other is to so...Generally, the procedure for Solving Security constrained unit commitment (SCUC) problems within Lagrangian Relaxation framework is partitioned into two stages: one is to obtain feasible SCUC states;the other is to solve the economic dispatch of generation power among all the generating units. The core of the two stages is how to determine the feasibility of SCUC states. The existence of ramp rate constraints and security constraints increases the difficulty of obtaining an analytical necessary and sufficient condition for determining the quasi-feasibility of SCUC states at each scheduling time. However, a numerical necessary and sufficient numerical condition is proposed and proven rigorously based on Benders Decomposition Theorem. Testing numerical example shows the effectiveness and efficiency of the condition.展开更多
Storage is widely considered in economic dispatch(ED)problems.To prevent simultaneous charging and discharging of a storage device,a storage-concerned ED problem should involve complementarity constraints for every st...Storage is widely considered in economic dispatch(ED)problems.To prevent simultaneous charging and discharging of a storage device,a storage-concerned ED problem should involve complementarity constraints for every storage device to make the problem strongly non-convex.In this case,the conventional Karush-Kuhn-Tucker optimality conditions are unsuitable,and the methods that are normally effective are also invalid.In our recent paper,we proposed a new exact relaxation method that directly removes the complementarity constraints from a storageconcerned ED model to make it convex and easy to solve.This paper extends the previous study by presenting and analyzing two new groups of sufficient conditions that guarantee exact relaxation.Different application conditions of these groups of sufficient conditions are discussed.Numerical tests are performed to show the benefit of using the exact relaxation method and the different suitable application conditions of these groups of sufficient conditions.This paper contributes to a wide application of exact relaxation in storage-concerned ED problems.展开更多
This paper studies additive manufacturing(AM) oriented structural topology optimization(TO).The minimum compliance design subject to overhang angle constraint with overhang length relaxation and horizontal minimum len...This paper studies additive manufacturing(AM) oriented structural topology optimization(TO).The minimum compliance design subject to overhang angle constraint with overhang length relaxation and horizontal minimum length control is considered.Although the overhang length relaxation allows additional flexibility for AM product design,there have been very limited studies on it.This paper elucidates that the overhang angle constraint we proposed can identify the lower boundary element that violates the overhang angle constraint.Taking advantage of this fact,we achieve the overhang length relaxation by specifying that the volume fraction of the elements that violate the overhang angle constraint in each local area of the design domain is less than a specified upper bound.A formula for estimating the maximum allowable overhang length of this method is proposed and verified.The horizontal minimum length constraint is also employed in this paper.While controlling the horizontal length size of the structural member,this constraint together with the overhang angle constraint with overhang length relaxation suppresses the hanging feature.The gradient-based optimization algorithm method of moving asymptotic(MMA) is used to solve the TO formulation.Numerical examples show the effectiveness of this method.It is observed that the new constraint alleviates the main issues of traditional overhang angle constraints,i.e.,gray element issue,stress concentration issue,and shattered structure issue.Compared with the strict traditional overhang angle constraint,the new formulation reduces structural compliance.展开更多
基金Project supported by the National Natural Science Foundation of China （Grant No.10571116）
文摘In this paper, a branch-and-bound method for solving multi-dimensional quadratic 0-1 knapsack problems was studied. The method was based on the Lagrangian relaxation and the surrogate constraint technique for finding feasible solutions. The Lagrangian relaxations were solved with the maximum-flow algorithm and the Lagrangian bounds was determined with the outer approximation method. Computational results show the efficiency of the proposed method for multi-dimensional quadratic 0-1 knapsack problems.
文摘Generally, the procedure for Solving Security constrained unit commitment (SCUC) problems within Lagrangian Relaxation framework is partitioned into two stages: one is to obtain feasible SCUC states;the other is to solve the economic dispatch of generation power among all the generating units. The core of the two stages is how to determine the feasibility of SCUC states. The existence of ramp rate constraints and security constraints increases the difficulty of obtaining an analytical necessary and sufficient condition for determining the quasi-feasibility of SCUC states at each scheduling time. However, a numerical necessary and sufficient numerical condition is proposed and proven rigorously based on Benders Decomposition Theorem. Testing numerical example shows the effectiveness and efficiency of the condition.
基金This work was supported in part by Foundation for Innovative Research Groups of the National Natural Science Foundation of China(No.51621065)the National Natural Science Foundation of China(No.51537006)the China Postdoctoral Science Foundation(No.2016M600091 and 2017T100078).
文摘Storage is widely considered in economic dispatch(ED)problems.To prevent simultaneous charging and discharging of a storage device,a storage-concerned ED problem should involve complementarity constraints for every storage device to make the problem strongly non-convex.In this case,the conventional Karush-Kuhn-Tucker optimality conditions are unsuitable,and the methods that are normally effective are also invalid.In our recent paper,we proposed a new exact relaxation method that directly removes the complementarity constraints from a storageconcerned ED model to make it convex and easy to solve.This paper extends the previous study by presenting and analyzing two new groups of sufficient conditions that guarantee exact relaxation.Different application conditions of these groups of sufficient conditions are discussed.Numerical tests are performed to show the benefit of using the exact relaxation method and the different suitable application conditions of these groups of sufficient conditions.This paper contributes to a wide application of exact relaxation in storage-concerned ED problems.
基金supported by the National Natural Science Foundation of China (Grant Nos.52075070 and 12032008)。
文摘This paper studies additive manufacturing(AM) oriented structural topology optimization(TO).The minimum compliance design subject to overhang angle constraint with overhang length relaxation and horizontal minimum length control is considered.Although the overhang length relaxation allows additional flexibility for AM product design,there have been very limited studies on it.This paper elucidates that the overhang angle constraint we proposed can identify the lower boundary element that violates the overhang angle constraint.Taking advantage of this fact,we achieve the overhang length relaxation by specifying that the volume fraction of the elements that violate the overhang angle constraint in each local area of the design domain is less than a specified upper bound.A formula for estimating the maximum allowable overhang length of this method is proposed and verified.The horizontal minimum length constraint is also employed in this paper.While controlling the horizontal length size of the structural member,this constraint together with the overhang angle constraint with overhang length relaxation suppresses the hanging feature.The gradient-based optimization algorithm method of moving asymptotic(MMA) is used to solve the TO formulation.Numerical examples show the effectiveness of this method.It is observed that the new constraint alleviates the main issues of traditional overhang angle constraints,i.e.,gray element issue,stress concentration issue,and shattered structure issue.Compared with the strict traditional overhang angle constraint,the new formulation reduces structural compliance.
