共查询到10条相似文献,搜索用时 116 毫秒
1.
Andrea Bettinelli Alberto Ceselli Giovanni Righini 《4OR: A Quarterly Journal of Operations Research》2008,6(4):361-374
The two-dimensional level strip packing problem (2LSPP) consists in packing rectangular items of given size into a strip of
given width divided into levels. Items packed into the same level cannot be put on top of one another and their overall width
cannot exceed the width of the strip. The objective is to accommodate all the items while minimizing the overall height of
the strip. The problem is -hard and arises from applications in logistics and transportation. We present a set covering formulation of the 2LSPP suitable
for a column generation approach, where each column corresponds to a feasible combination of items inserted into the same
level. For the exact optimization of the 2LSPP we present a branch-and-price algorithm, in which the pricing problem is a
penalized knapsack problem. Computational results are reported for benchmark instances with some hundreds items. 相似文献
2.
Corinne Feremans Alexander Grigoriev René Sitters 《4OR: A Quarterly Journal of Operations Research》2006,4(4):319-329
This paper is concerned with a special case of the generalized minimum spanning tree problem. The problem is defined on an undirected graph, where the vertex set is partitioned into clusters, and non-negative costs are associated with the edges. The problem is to find a tree of minimum cost containing at least one vertex in each cluster. We consider a geometric case of the problem where the graph is complete, all vertices are situated in the plane, and Euclidean distance defines the edge cost. We prove that the problem is strongly
-hard even in the case of a special structure of the clustering called grid clustering. We construct an exact exponential time dynamic programming algorithm and, based on this dynamic programming algorithm, we develop a polynomial time approximation scheme for the problem with grid clustering. 相似文献
3.
P. C. Pop 《Annals of Operations Research》2007,150(1):193-204
The prize-collecting generalized minimum spanning tree problem (PC-GMSTP), is a generalization of the generalized minimum
spanning tree problem (GMSTP) and belongs to the hard core of -hard problems. We describe an exact exponential time algorithm for the problem, as well we present several mixed integer and integer
programming formulations of the PC-GMSTP. Moreover, we establish relationships between the polytopes corresponding to their
linear relaxations and present an efficient solution procedure that finds the optimal solution of the PC-GMSTP for graphs
with up 240 nodes. 相似文献
4.
We consider the following problem. A set of vectors is given. We want to find the convex combination such that the statistical median of z is maximum. In the application that we have in mind, are the historical return arrays of asset j and are the portfolio weights. Maximizing the median on a convex set of arrays is a continuous non-differentiable, non-concave
optimization problem and it can be shown that the problem belongs to the APX-hard difficulty class. As a consequence, we are
sure that no polynomial time algorithm can ever solve the model, unless P = NP. We propose an implicit enumeration algorithm,
in which bounds on the objective function are calculated using continuous geometric properties of the median. Computational
results are reported. 相似文献
5.
We consider the Nonconvex Piecewise Linear Network Flow Problem (NPLNFP) which is known to be
-hard. Although exact methods such as branch and bound have been developed to solve the NPLNFP, their computational requirements increase exponentially with the size of the problem. Hence, an efficient heuristic approach is in need to solve large scale problems appearing in many practical applications including transportation, production-inventory management, supply chain, facility expansion and location decision, and logistics. In this paper, we present a new approach for solving the general NPLNFP in a continuous formulation by adapting a dynamic domain contraction. A Dynamic Domain Contraction (DDC) algorithm is presented and preliminary computational results on a wide range of test problems are reported. The results show that the proposed algorithm generates solutions within 0 to 0.94 % of optimality in all instances that the exact solutions are available from a branch and bound method. 相似文献
6.
A. Tiskin 《Journal of Mathematical Sciences》2009,158(5):759-769
Computation on compressed strings is one of the key approaches to processing massive data sets. We consider local subsequence
recognition problems on strings compressed by straight-line programs (SLP), which is closely related to Lempel–Ziv compression.
For an SLP-compressed text of length , and an uncompressed pattern of length n, Cégielski et al. gave an algorithm for local subsequence recognition running in time . We improve the running time to . Our algorithm can also be used to compute the longest common subsequence between a compressed text and an uncompressed pattern
in time ; the same problem with a compressed pattern is known to be NP-hard. Bibliography: 22 titles.
Published in Zapiski Nauchnykh Seminarov POMI, Vol. 358, 2008, pp. 282–300. 相似文献
7.
Wiesława T. Obuchowska 《Mathematical Methods of Operations Research》2008,68(3):445-467
In this paper we are concerned with the problem of boundedness and the existence of optimal solutions to the constrained integer
optimization problem. We present necessary and sufficient conditions for boundedness of either a faithfully convex or quasi-convex
polynomial function over the feasible set contained in , and defined by a system of faithfully convex inequality constraints and/or quasi-convex polynomial inequalities. The conditions
for boundedness are provided in the form of an implementable algorithm, terminating after a finite number of iterations, showing
that for the considered class of functions, the integer programming problem with nonempty feasible region is unbounded if
and only if the associated continuous optimization problem is unbounded. We also prove that for a broad class of objective
functions (which in particular includes polynomials with integer coefficients), an optimal solution set of the constrained
integer problem is nonempty over any subset of . 相似文献
8.
A convex optimization approach for minimizing the ratio of indefinite quadratic functions over an ellipsoid 总被引:1,自引:0,他引:1
We consider the nonconvex problem (RQ) of minimizing the ratio of two nonconvex quadratic functions over a possibly degenerate
ellipsoid. This formulation is motivated by the so-called regularized total least squares problem (RTLS), which is a special
case of the problem’s class we study. We prove that under a certain mild assumption on the problem’s data, problem (RQ) admits
an exact semidefinite programming relaxation. We then study a simple iterative procedure which is proven to converge superlinearly
to a global solution of (RQ) and show that the dependency of the number of iterations on the optimality tolerance grows as .
This research is partially supported by the Israel Science Foundation, ISF grant #489-06. 相似文献
9.
We examine the operator algebra
behind the boundary integral equation method for solving transmission problems. A new type of boundary integral operator, the rotation operator, is introduced, which is more appropriate than operators of double layer type for solving transmission problems for first order elliptic partial differential equations. We give a general invertibility criteria for operators in
by defining a Clifford algebra valued Gelfand transform on
. The general theory is applied to transmission problems with strongly Lipschitz interfaces for the two classical elliptic operators
and . We here use Rellich techniques in a new way to estimate the full complex spectrum of the boundary integral operators. For
we use the associated rotation operator to solve the Hilbert boundary value problem and a Riemann type transmission problem. For the Helmholtz equation, we demonstrate how Rellich estimates give an angular spectral estimate on the rotation operator, which with the general spectral mapping properties in
translates to a hyperbolic spectral estimate for the double layer potential operator. 相似文献
10.
In this paper, we propose a modification of Benson’s algorithm for solving multiobjective linear programmes in objective space
in order to approximate the true nondominated set. We first summarize Benson’s original algorithm and propose some small changes
to improve computational performance. We then introduce our approximation version of the algorithm, which computes an inner
and an outer approximation of the nondominated set. We prove that the inner approximation provides a set of -nondominated points. This work is motivated by an application, the beam intensity optimization problem of radiotherapy treatment
planning. This problem can be formulated as a multiobjective linear programme with three objectives. The constraint matrix
of the problem relies on the calculation of dose deposited in tissue. Since this calculation is always imprecise solving the
MOLP exactly is not necessary in practice. With our algorithm we solve the problem approximately within a specified accuracy
in objective space. We present results on four clinical cancer cases that clearly illustrate the advantages of our method. 相似文献