68-04 Explicit machine computation and programs (not the theory of computation or programming)
Refine
Document Type
- ZIB-Report (3)
Language
- English (3)
Has Fulltext
- yes (3)
Is part of the Bibliography
- no (3)
Keywords
Institute
Nonnegativity certificates can be used to obtain tight dual bounds for polynomial optimization problems. Hierarchies of certificate-based relaxations ensure convergence to the global optimum, but higher levels of such hierarchies can become very computationally expensive, and the well-known sums of squares hierarchies scale poorly with the degree of the polynomials. This has motivated research into alternative certificates and approaches to global optimization. We consider sums of nonnegative circuit polynomials (SONC) certificates, which are well-suited for sparse problems since the computational cost depends on the number of terms in the polynomials and does not depend on the degrees of the polynomials. We propose a method that guarantees that given finite variable domains, a SONC relaxation will yield a finite dual bound. This method opens up a new approach to utilizing variable bounds in SONC-based methods, which is particularly crucial for integrating SONC relaxations into branch-and-bound algorithms. We report on computational experiments with incorporating SONC relaxations into the spatial branch-and-bound algorithm of the mixed-integer nonlinear programming framework SCIP. Applying our strengthening method increases the number of instances where the SONC relaxation of the root node yielded a finite dual bound from 9 to 330 out of 349 instances in the test set.
Usually complete linear descriptions of polytopes consist of
an enormous number of facet-defining inequalities already
for very small problem sizes. In this paper, we describe a method
for dividing the inequalities into equivalence classes without resorting to a normal form. Within each
class, facets are related by certain symmetries and it is sufficient
to list one representative of each class to give a complete
picture of the structural properties of a polytope. We propose an algorithm
for the classification and illustrate its efficiency on a broad range of combinatorial optimization problems including the Traveling Salesman and the Linear Ordering Problem.
An algorithm is described to decide if a given polynomial differential expression $\Delta$ of multivariate functions is exact, i.e. whether there exists a first integral $P$ such that $D_xP = \Delta$ for any one of a set of variables $x$ and to provide the integral $P$. A generalization is given to allow integration in the case that the exactness is prohibited by terms which contain only functions of not all the independent variables.