THE one-dimensional bin-packing problem is defined as follows: for a given list L={p<sub>1</sub>, p<sub>2</sub>,…, P<sub>n</sub>}, where 0【p<sub>i</sub>≤1 denotes the...THE one-dimensional bin-packing problem is defined as follows: for a given list L={p<sub>1</sub>, p<sub>2</sub>,…, P<sub>n</sub>}, where 0【p<sub>i</sub>≤1 denotes the item and its size as well, we are to pack all the items in-to bins, each of which has a capacity 1, and the goal is to minimize the number of bins used.The first-fit-decreasing (FFD) algorithm is a famous approximate algorithm for the bin-pack-ing problem. The FFD algorithm first sorts all the list into non-increasing order and then pro-cesses the pieces in that order by placing each item into the first bin into which it fits.展开更多
An \%S\%_dependent GFR method and a generalized conjugate gradient method are designed. Two estimated values of upper bounds for the ratio of β k to β FR k are given. The two convergence theorems are proved. The glo...An \%S\%_dependent GFR method and a generalized conjugate gradient method are designed. Two estimated values of upper bounds for the ratio of β k to β FR k are given. The two convergence theorems are proved. The global convergent properties of \%s\%_dependent GFR method are obtained adopting several choice strategies of steplength and some results in recent literature are extended.展开更多
A trust region algorithm is proposed for solving bilevel programming problems where the lower level programming problem is a strongly convex programming problem with linear constraints. This algorithm is based on a tr...A trust region algorithm is proposed for solving bilevel programming problems where the lower level programming problem is a strongly convex programming problem with linear constraints. This algorithm is based on a trust region algorithm for nonsmooth unconstrained optimization problems, and its global convergence is also proved.展开更多
文摘THE one-dimensional bin-packing problem is defined as follows: for a given list L={p<sub>1</sub>, p<sub>2</sub>,…, P<sub>n</sub>}, where 0【p<sub>i</sub>≤1 denotes the item and its size as well, we are to pack all the items in-to bins, each of which has a capacity 1, and the goal is to minimize the number of bins used.The first-fit-decreasing (FFD) algorithm is a famous approximate algorithm for the bin-pack-ing problem. The FFD algorithm first sorts all the list into non-increasing order and then pro-cesses the pieces in that order by placing each item into the first bin into which it fits.
文摘An \%S\%_dependent GFR method and a generalized conjugate gradient method are designed. Two estimated values of upper bounds for the ratio of β k to β FR k are given. The two convergence theorems are proved. The global convergent properties of \%s\%_dependent GFR method are obtained adopting several choice strategies of steplength and some results in recent literature are extended.
文摘A trust region algorithm is proposed for solving bilevel programming problems where the lower level programming problem is a strongly convex programming problem with linear constraints. This algorithm is based on a trust region algorithm for nonsmooth unconstrained optimization problems, and its global convergence is also proved.