The sparse linear programming(SLP) is a linear programming problem equipped with a sparsity constraint, which is nonconvex, discontinuous and generally NP-hard due to the combinatorial property involved.In this paper,...The sparse linear programming(SLP) is a linear programming problem equipped with a sparsity constraint, which is nonconvex, discontinuous and generally NP-hard due to the combinatorial property involved.In this paper, by rewriting the sparsity constraint into a disjunctive form, we present an explicit formula of the Lagrangian dual problem for the SLP, in terms of an unconstrained piecewise-linear convex programming problem which admits a strong duality under bi-dual sparsity consistency. Furthermore, we show a saddle point theorem based on the strong duality and analyze two classes of stationary points for the saddle point problem. At last,we extend these results to SLP with the lower bound zero replaced by a certain negative constant.展开更多
Multi-dimensional nonlinear knapsack problems are often encountered in resource allocation, industrial planning and computer networks. In this paper, a surrogate dual method was proposed for solving this class of prob...Multi-dimensional nonlinear knapsack problems are often encountered in resource allocation, industrial planning and computer networks. In this paper, a surrogate dual method was proposed for solving this class of problems. Multiply constrained problem was relaxed to a singly constrained problem by using the surrogate technique. To compute tighter bounds of the primal problem, the cutting plane method was used to solve the surrogate dual problem, where the surrogate relaxation problem was solved by the 0-1 linearization method. The domain cut technique was employed to eliminate the duality gap and thus to guarantee the convergence of tile algorithm. Numerical results were reported for large-scale multi-dimensional nonlinear knapsack problems.展开更多
In this paper,we consider nonlinear infinity-norm minimization problems.We device a reliable Lagrangian dual approach for solving this kind of problems and based on this method we propose an algorithm for the mixed li...In this paper,we consider nonlinear infinity-norm minimization problems.We device a reliable Lagrangian dual approach for solving this kind of problems and based on this method we propose an algorithm for the mixed linear and nonlinear infinity- norm minimization problems.Numerical results are presented.展开更多
The semi-Lagrangian relaxation （SLR）, a new exactmethod for combinatorial optimization problems with equality constraints,is applied to the quadratic assignment problem （QAP）.A dual ascent algorithm with finite co...The semi-Lagrangian relaxation （SLR）, a new exactmethod for combinatorial optimization problems with equality constraints,is applied to the quadratic assignment problem （QAP）.A dual ascent algorithm with finite convergence is developed forsolving the semi-Lagrangian dual problem associated to the QAP.We perform computational experiments on 30 moderately difficultQAP instances by using the mixed integer programming solvers,Cplex, and SLR＋Cplex, respectively. The numerical results notonly further illustrate that the SLR and the developed dual ascentalgorithm can be used to solve the QAP reasonably, but also disclosean interesting fact： comparing with solving the unreducedproblem, the reduced oracle problem cannot be always effectivelysolved by using Cplex in terms of the CPU time.展开更多
基金supported by National Natural Science Foundation of China(Grant Nos.11431002,11771038 and 11728101)the State Key Laboratory of Rail Traffic Control and Safety,Beijing Jiaotong University(Grant No.RCS2017ZJ001)China Scholarship Council(Grant No.201707090019)
文摘The sparse linear programming(SLP) is a linear programming problem equipped with a sparsity constraint, which is nonconvex, discontinuous and generally NP-hard due to the combinatorial property involved.In this paper, by rewriting the sparsity constraint into a disjunctive form, we present an explicit formula of the Lagrangian dual problem for the SLP, in terms of an unconstrained piecewise-linear convex programming problem which admits a strong duality under bi-dual sparsity consistency. Furthermore, we show a saddle point theorem based on the strong duality and analyze two classes of stationary points for the saddle point problem. At last,we extend these results to SLP with the lower bound zero replaced by a certain negative constant.
基金partially supported by the National Natural Science Foundation of China （Grant Nos.10271073, 10571116）
文摘Multi-dimensional nonlinear knapsack problems are often encountered in resource allocation, industrial planning and computer networks. In this paper, a surrogate dual method was proposed for solving this class of problems. Multiply constrained problem was relaxed to a singly constrained problem by using the surrogate technique. To compute tighter bounds of the primal problem, the cutting plane method was used to solve the surrogate dual problem, where the surrogate relaxation problem was solved by the 0-1 linearization method. The domain cut technique was employed to eliminate the duality gap and thus to guarantee the convergence of tile algorithm. Numerical results were reported for large-scale multi-dimensional nonlinear knapsack problems.
文摘In this paper,we consider nonlinear infinity-norm minimization problems.We device a reliable Lagrangian dual approach for solving this kind of problems and based on this method we propose an algorithm for the mixed linear and nonlinear infinity- norm minimization problems.Numerical results are presented.
基金supported by the National Natural Science Foundation of China(71401106)the Innovation Program of Shanghai Municipal Education Commission(14YZ090)+4 种基金the Shanghai Natural Science Foundation(14ZR1418700)the Shanghai First-class Academic Discipline Project(S1201YLXK)the Hujiang Foundation of China(A14006)the grant S2009/esp-1594 from the Comunidad de Madrid(Spain)the grant MTM2012-36163-C06-06 from the Spanish government
文摘The semi-Lagrangian relaxation （SLR）, a new exactmethod for combinatorial optimization problems with equality constraints,is applied to the quadratic assignment problem （QAP）.A dual ascent algorithm with finite convergence is developed forsolving the semi-Lagrangian dual problem associated to the QAP.We perform computational experiments on 30 moderately difficultQAP instances by using the mixed integer programming solvers,Cplex, and SLR＋Cplex, respectively. The numerical results notonly further illustrate that the SLR and the developed dual ascentalgorithm can be used to solve the QAP reasonably, but also disclosean interesting fact： comparing with solving the unreducedproblem, the reduced oracle problem cannot be always effectivelysolved by using Cplex in terms of the CPU time.
