排序方式: 共有47条查询结果,搜索用时 31 毫秒
1.
Graver's optimality conditions based on Hilbert bases apply to an integer program with linear equations and a linear objective function. We generalize this result to include a fairly large class of nonlinear objective functions. Our extension provides in particular a link between the superadditivity of the difference-objective function and the Hilbert bases of conic subpartitions of . 相似文献
2.
Jesús A. De Loera Raymond Hemmecke Matthias Köppe Robert Weismantel 《Mathematical Programming》2008,115(2):273-290
We show the existence of a fully polynomial-time approximation scheme (FPTAS) for the problem of maximizing a non-negative
polynomial over mixed-integer sets in convex polytopes, when the number of variables is fixed. Moreover, using a weaker notion
of approximation, we show the existence of a fully polynomial-time approximation scheme for the problem of maximizing or minimizing
an arbitrary polynomial over mixed-integer sets in convex polytopes, when the number of variables is fixed.
A conference version of this article, containing a part of the results presented here, appeared in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, Miami, FL, January 22–24, 2006, pp. 743–748. The first author gratefully acknowledges support from NSF grant DMS-0608785, a 2003 UC-Davis Chancellor’s fellow award,
the Alexander von Humboldt foundation, and IMO Magdeburg. The remaining authors were supported by the European TMR network
ADONET 504438. 相似文献
3.
4.
The multi-transshipment problem is NP-hard already for two commodities over bipartite networks. Nonetheless, using our recent
theory of n-fold integer programming and extensions developed herein, we are able to establish the polynomial time solvability of the
problem in two broad situations. First, for any fixed number of commodities and number of suppliers, we solve the problem
over bipartite networks with variable number of consumers in polynomial time. This is very natural in operations research
applications where few facilities serve many customers. Second, for every fixed network, we solve the problem with variable
number of commodities in polynomial time. 相似文献
5.
We consider $N$ -fold $4$ -block decomposable integer programs, which simultaneously generalize $N$ -fold integer programs and two-stage stochastic integer programs with $N$ scenarios. In previous work (Hemmecke et al. in Integer programming and combinatorial optimization. Springer, Berlin, 2010), it was proved that for fixed blocks but variable $N$ , these integer programs are polynomial-time solvable for any linear objective. We extend this result to the minimization of separable convex objective functions. Our algorithm combines Graver basis techniques with a proximity result (Hochbaum and Shanthikumar in J. ACM 37:843–862,1990), which allows us to use convex continuous optimization as a subroutine. 相似文献
6.
In this paper we consider the solution of certain convex integer minimization problems via greedy augmentation procedures.
We show that a greedy augmentation procedure that employs only directions from certain Graver bases needs only polynomially
many augmentation steps to solve the given problem. We extend these results to convex N-fold integer minimization problems and to convex 2-stage stochastic integer minimization problems. Finally, we present some
applications of convex N-fold integer minimization problems for which our approach provides polynomial time solution algorithms. 相似文献
7.
We consider mixed integer linear sets defined by two equations involving two integer variables and any number of non-negative continuous variables. We analyze the benefit from adding a non-split inequality on top of the split closure. Applying a probabilistic model, we show that the importance of a type 2 triangle inequality decreases with decreasing lattice width, on average. Our results suggest that this is also true for type 3 triangle and quadrilateral inequalities. 相似文献
8.
Steffen Borchers Sandro Bosio Rolf Findeisen Utz-Uwe Haus Philipp Rumschinski Robert Weismantel 《Mathematical Methods of Operations Research》2011,73(3):381-400
This paper focuses on combinatorial feasibility and optimization problems that arise in the context of parameter identification
of discrete dynamical systems. Given a candidate parametric model for a physical system and a set of experimental observations,
the objective of parameter identification is to provide estimates of the parameter values for which the model can reproduce
the experiments. To this end, we define a finite graph corresponding to the model, to each arc of which a set of parameters
is associated. Paths in this graph are regarded as feasible only if the sets of parameters corresponding to the arcs of the
path have nonempty intersection. We study feasibility and optimization problems on such feasible paths, focusing on computational
complexity. We show that, under certain restrictions on the sets of parameters, some of the problems become tractable, whereas
others are NP-hard. In a similar vein, we define and study some graph problems for experimental design, whose goal is to support
the scientist in optimally designing new experiments. 相似文献
9.
In this paper we describe a cutting plane algorithm for the Steiner tree packing problem. We use our algorithm to solve some
switchbox routing problems of VLSI-design and report on our computational experience. This includes a brief discussion of
separation algorithms, a new LP-based primal heuristic and implementation details. The paper is based on the polyhedral theory
for the Steiner tree packing polyhedron developed in our companion paper (this issue) and meant to turn this theory into an
algorithmic tool for the solution of practical problems. 相似文献
10.
We address optimization of parametric nonlinear functions of the form f(Wx), where ${f : \mathbb {R}^d \rightarrow \mathbb {R}}$ is a nonlinear function, W is a d × n matrix, and feasible x are in some large finite set ${\mathcal {F}}$ of integer points in ${\mathbb {R}^n}$ . Generally, such problems are intractable, so we obtain positive algorithmic results by looking at broad natural classes of f, W and ${\mathcal {F}}$ . One of our main motivations is multi-objective discrete optimization, where f trades off the linear functions given by the rows of W. Another motivation is that we want to extend as much as possible the known results about polynomial-time linear optimization over trees, assignments, matroids, polymatroids, etc. to nonlinear optimization over such structures. We assume that ${\mathcal {F}}$ is well described (i.e., we can efficiently optimize a linear objective function on ${\mathcal {F}}$ ; equivalently, we have an efficient separation oracle for the convex hull of ${\mathcal {F}}$ ). For example, the sets of characteristic vectors of (i) matchings of a graph, and (ii) common bases of a pair of matroids on a common ground set satisfy this property. In this setting, the problem is already known to be intractable (even for a single matroid), for general f (given by a comparison oracle), for (i) d = 1 and binary-encoded W, and for (ii) d = n and W = I. Our main results (a few technicalities and some generality suppressed):
- When ${\mathcal {F}}$ is well described, f is convex (or even quasi-convex), and W has a fixed number of rows and is unary encoded or with entries in a fixed set, we give an efficient deterministic algorithm for maximization.
- When ${\mathcal {F}}$ is well described, f is a norm, and W is binary-encoded, we give an efficient deterministic constant-approximation algorithm for maximization (Note that the approximation factor depends on the norm, and hence implicitly on the number of rows of W, while the running time increases only linearly in the number of rows of W).
- When non-negative ${\mathcal {F}}$ is well described, f is “ray concave” and non-decreasing, and non-negative W has a fixed number of rows and is unary encoded or with entries in a fixed set, we give an efficient deterministic constant-approximation algorithm for minimization.
- When ${\mathcal {F}}$ is the set of characteristic vectors of common independent sets or bases of a pair of rational vectorial matroids on a common ground set, f is arbitrary, and W has a fixed number of rows and is unary encoded, we give an efficient randomized algorithm for optimization.