Fractional knapsack problems

The fractional knapsack problem to obtain an integer solution that maximizes a linear fractional objective function under the constraint of one linear inequality is considered. A modification of the Dinkelbach's algorithm [3] is proposed to exploit the fact that good feasible solutions are easily obtained for both the fractional knapsack problem and the ordinary knapsack problem. An upper bound of the number of iterations is derived. In particular it is clarified how optimal solutions depend on the right hand side of the constraint; a fractional knapsack problem reduces to an ordinary knapsack problem if the right hand side exceeds a certain bound.     

范数下无容量限制设施选址逆问题的求解方法

一个优化问题的逆问题是这样一类问题,在给定该优化问题的一个可行解时,通过最小化目标函数中参数的改变量(在某个范数下)使得该可行解成为改变参数后的该优化问题的最优解。对于本是NP-难问题的无容量限制设施选址问题,证明了其逆问题仍是NP-难的。研究了使用经典的行生成算法对无容量限制设施选址的逆问题进行计算,并给出了求得逆问题上下界的启发式方法。两种方法分别基于对子问题的线性松弛求解给出上界和利用邻域搜索以及设置迭代循环次数的方式给出下界。数值结果表明线性松弛法得到的上界与最优值差距较小,但求解效率提升不大;而启发式方法得到的下界与最优值差距极小,极大地提高了求解该逆问题的效率。     

A new lower bound for the linear knapsack problem with general integer variables

It is well known that the linear knapsack problem with general integer variables (LKP) is NP-hard. In this paper we first introduce a special case of this problem and develop an O(n) algorithm to solve it. We then show how this algorithm can be used efficiently to obtain a lower bound for a general instance of LKP and prove that it is at least as good as the linear programming lower bound. We also present the results of a computational study that show that for certain classes of problems the proposed bound on average is tighter than other bounds proposed in the literature.     

New error bound for linear complementarity problems for B-matrices

A new error bound for the linear complementarity problem is obtained when the involved matrix is a B-matrix. This bound improves existing results. Finally, two numerical examples are also given to show that the bound is better than some previous results.     

A piecewise linear upper bound on the network recourse function

We consider the optimal value of a pure minimum cost network flow problem as a function of supply, demand and arc capacities. We present a new piecewise linear upper bound on this function, which is called the network recourse function. The bound is compared to the standard Madansky bound, and is shown computationally to be a little weaker, but much faster to find. The amount of work is linear in the number of stochastic variables, not exponential as is the case for the Madansky bound. Therefore, the reduction in work increases as the number of stochastic variables increases. Computational results are presented.     

An Improved Lower Bound for the Multimedian Location Problem

We consider the problem of locating, on a network, n new facilities that interact with m existing facilities. In addition, pairs of new facilities interact. This problem, the multimedian location problem on a network, is known to be NP-hard. We give a new integer programming formulation of this problem, and show that its linear programming relaxation provides a lower bound that is superior to the bound provided by a previously published formulation. We also report results of computational testing with both formulations.     

A branch and bound algorithm for solving the multiple-choice knapsack problem

The multiple-choice knapsack problem is a binary knapsack problem with the addition of disjoint multiple-choice constraints. We describe a branch and bound algorithm based on embedding Glover and Klingman's method for the associated linear program within a depth-first search procedure. A heuristic is used to find a starting dual feasible solution to the associated linear program and a ‘pegging’ test is employed to reduce the size of the problem for the enumeration phase. Computational experience and comparisons with the code of Nauss and an algorithm of Armstrong et al. for the same problem are reported.     

A branch-and-bound algorithm to solve the linear ordering problem for weighted tournaments

The linear ordering problem consists in finding a linear order at minimum remoteness from a weighted tournament T, the remoteness being the sum of the weights of the arcs that we must reverse in T to transform it into a linear order. This problem, also known as the search of a median order, or of a maximum acyclic subdigraph, or of a maximum consistent set, or of a minimum feedback arc set, is NP-hard; when all the weights of T are equal to 1, the linear ordering problem is the same as Slater's problem. In this paper, we describe the principles and the results of an exact method designed to solve the linear ordering problem for any weighted tournament. This method, of which the corresponding software is freely available at the URL address http://www.enst.fr/~charon/tournament/median.html, is based upon a branch-and-bound search with a Lagrangean relaxation as the evaluation function and a noising method for computing the initial bound. Other components are designed to reduce the BB-search-tree.     

Computation of lower bounds on the network cost in location problems subject to distance constraints

Methods for the computation of lower bounds on the cost of the connecting network for the continuous and discrete variants of the problem of location of interconnected objects subject to minimal or maximal distances between them are proposed. For the continuous variant, the bound is found by solving a linear programming problem. For the discrete variant, an assignment problem with a rectangular matrix containing forbidden entries is constructed. An application of the assignment problem for locating objects of various sizes is described.     

Buyback problem with discrete concave valuation functions

We discuss an online discrete optimization problem called the buyback problem. In the literature of the buyback problem, the valuation function representing the total value of selected elements is given by a linear function. In this paper, we consider a generalization of the buyback problem using nonlinear valuation functions. We propose an online algorithm for the problem with discrete concave valuation functions, and show that it achieves the tight competitive ratio, i.e., the competitive ratio of the proposed algorithm is equal to the known lower bound for the problem.     

线性比式和规划问题的输出空间分支定界算法

本文旨在针对线性比式和规划这一NP-Hard非线性规划问题提出新的全局优化算法.首先,通过引入p个辅助变量把原问题等价的转化为一个非线性规划问题,这个非线性规划问题的目标函数是乘积和的形式并给原问题增加了p个新的非线性约束,再通过构造凸凹包络的技巧对等价问题的目标函数和约束条件进行相应的线性放缩,构成等价问题的一个下界线性松弛规划问题,从而提出了一个求解原问题的分支定界算法,并证明了算法的收敛性.最后,通过数值结果比较表明所提出的算法是可行有效的.     

一种基于匈牙利算法的二次分配问题求解方法

二次分配问题(Quadratic assignment problem,QAP)属于NP-hard组合优化难题.二次分配问题的线性化及下界计算方法,是求解二次分配问题的重要途径.以Frieze-Yadegar线性化模型和Gilmore-Lawler下界为基础,详细论述了二次分配问题线性化模型的结构特征,并分析了Gilmore-Lawler下界值往往远离目标函数最优值的原因.在此基础上,提出一种基于匈牙利算法的二次分配问题对偶上升下界求解法.通过求解QAPLIB中的部分实例,说明了方法的有效和可行性.     

A Cutting Plane Algorithm for Linear Reverse Convex Programs

In this paper, global optimization of linear programs with an additional reverse convex constraint is considered. This type of problem arises in many applications such as engineering design, communications networks, and many management decision support systems with budget constraints and economies-of-scale. The main difficulty with this type of problem is the presence of the complicated reverse convex constraint, which destroys the convexity and possibly the connectivity of the feasible region, putting the problem in a class of difficult and mathematically intractable problems. We present a cutting plane method within the scope of a branch-and-bound scheme that efficiently partitions the polytope associated with the linear constraints and systematically fathoms these portions through the use of the bounds. An upper bound and a lower bound for the optimal value is found and improved at each iteration. The algorithm terminates when all the generated subdivisions have been fathomed.     

ON THE ERROR ESTIMATE OF LINEAR FINITE ELEMENT APPROXIMATION TO THE ELASTIC CONTACT PROBLEM WITH CURVED CONTACT BOUNDARY

1. PreliminaryThe error estimate of linear finite element approximation to the elastic contact problem with curved contact boundary was considered in [2], in which the authors obtainedthe error bound of O(hl) with a much complex proof, requirement of three times continuously differentiable for contact boundary and extra regularities of triangulation (c.f. [2, Theorem 3.3, p.149]). In this paper, we obtained the error bound of O(hi) withonly requirement of two times continuously differentiable…     

Accuracy and Stability of the Null Space Method for Solving the Equality Constrained Least Squares Problem

The null space method is a standard method for solving the linear least squares problem subject to equality constraints (the LSE problem). We show that three variants of the method, including one used in LAPACK that is based on the generalized QR factorization, are numerically stable. We derive two perturbation bounds for the LSE problem: one of standard form that is not attainable, and a bound that yields the condition number of the LSE problem to within a small constant factor. By combining the backward error analysis and perturbation bounds we derive an approximate forward error bound suitable for practical computation. Numerical experiments are given to illustrate the sharpness of this bound.     

一类多商品设施选址问题的基于线性松弛解的启发式方法

多商品设施选址问题是众多设施选址问题中一类重要而困难的问题.在这一问题中,顾客的需求可能包含不止一种商品.对于大规模问题,成熟的商业求解器往往不能在满意的时间内找到高质量的可行解.研究了无容量限制的单货源多商品设施选址问题的一般形式,并给出了应用于此类问题的两个启发式方法.这两个方法基于原选址问题的线性规划松弛问题的最优解,分别通过求解紧问题和邻域搜索的方式给出了原问题的一个可行上界.理论分析指出所提方法可以实施于任意可行问题的实例.数值结果表明所提方法可以显著地提高求解器求解此类设施选址问题的求解效率.     

A comparison of lower bounds for the symmetric circulant traveling salesman problem

When the matrix of distances between cities is symmetric and circulant, the traveling salesman problem (TSP) reduces to the so-called symmetric circulant traveling salesman problem (SCTSP), that has applications in the design of reconfigurable networks, and in minimizing wallpaper waste. The complexity of the SCTSP is open, but conjectured to be NP-hard, and we compare different lower bounds on the optimal value that may be computed in polynomial time. We derive a new linear programming (LP) relaxation of the SCTSP from the semidefinite programming (SDP) relaxation in [E. de Klerk, D.V. Pasechnik, R. Sotirov, On semidefinite programming relaxation of the traveling salesman problem, SIAM Journal of Optimization 19 (4) (2008) 1559-1573]. Further, we discuss theoretical and empirical comparisons between this new bound and three well-known bounds from the literature, namely the Held-Karp bound [M. Held, R.M. Karp, The traveling salesman problem and minimum spanning trees, Operations Research 18 (1970) 1138-1162], the 1-tree bound, and the closed-form bound for SCTSP proposed in [J.A.A. van der Veen, Solvable cases of TSP with various objective functions, Ph.D. Thesis, Groningen University, The Netherlands, 1992].     

与P矩阵和LCP有关的量(英文)

发展了与P矩阵有关的基本量的一些新性质,并且改进了由Xiu和Zhang[A characteristic quantity ofP-matrices,Appl.Math.Lett.,2002,15:41-46]提出的水平线性余问题全局误差上限.     

Error bounds for analytic systems and their applications

Using a 1958 result of Lojasiewicz, we establish an error bound for analytic systems consisting of equalities and inequalities defined by real analytic functions. In particular, we show that over any bounded region, the distance from any vectorx in the region to the solution set of an analytic system is bounded by a residual function, raised to a certain power, evaluated atx. For quadratic systems satisfying certain nonnegativity assumptions, we show that this exponent is equal to 1/2. We apply the error bounds to the Karush—Kuhn—Tucker system of a variational inequality, the affine variational inequality, the linear and nonlinear complementarity problem, and the 0–1 integer feasibility problem, and obtain new error bound results for these problems. The latter results extend previous work for polynomial systems and explain why a certain square-root term is needed in an error bound for the (monotone) linear complementarity problem.The research of this author is based on work supported by the Natural Sciences and Engineering Research Council of Canada under grant OPG0090391.The research of this author is based on work supported by the National Science Foundation under grants DDM-9104078 and CCR-9213739 and by the Office of Naval Research under grant 4116687-01.