𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An algorithm for concave integer minimization over a polyhedron

✍ Scribed by Harold P. Benson; S. Selcuk Erenguc

Publisher
John Wiley and Sons
Year
1990
Tongue
English
Weight
753 KB
Volume
37
Category
Article
ISSN
0894-069X

No coin nor oath required. For personal study only.

✦ Synopsis

We present an algorithm for solving the problem of globally minimizing a concave function over the integers contained in a compact polyhedron. The objective function of this problem need not be separable or even analytically defined. To our knowledge, the algorithm is the first ever proposed for this problem. Among the major advantages of the algorithm are that no nonlinear computations or optimizations are required, and that it allows one to exploit the polyhedral nature of X . We discuss these and other advantages and disadvantages of the algorithm, and we present some preliminary computational experience using our computer code for the algorithm. This computational experience seems to indicate that the algorithm is quite practical for solving many concave integer minimization problems over compact polyhedra.

πŸ“œ SIMILAR VOLUMES

A hybrid algorithm for finding minimal u
A hybrid algorithm for finding minimal unsatisfiable subsets in over-constrained CSPs
✍ I. Shah πŸ“‚ Article πŸ“… 2011 πŸ› John Wiley and Sons 🌐 English βš– 619 KB

Minimal Unsatisfiable Subsets (MUSes) are the subsets of constraints of an overconstrained constraint satisfaction problem (CSP) that cannot be satisfied simultaneously and therefore are responsible for the conflict in the CSP. In this paper, we present a hybrid algorithm for finding MUSes in overco

An algorithm for packing regular multist
An algorithm for packing regular multistrand polypeptide structures by energy minimization
✍ Kenneth D. Gibson; Harold A. Scheraga πŸ“‚ Article πŸ“… 1994 πŸ› John Wiley and Sons 🌐 English βš– 1008 KB

An algorithm has been developed for packing polypeptide chains by energy minimization subject to regularity conditions, in which regularity is maintained without the addition of pseudoenergy terms by defining the energy as a function of appropriately chosen independent variables. The gradient of the

An algorithm for the divisors of monic p
An algorithm for the divisors of monic polynomials over a commutative ring
✍ Ihsen Yengui πŸ“‚ Article πŸ“… 2003 πŸ› John Wiley and Sons 🌐 English βš– 147 KB

Gilmer and Heinzer proved that given a reduced ring R, a polynomial f divides a monic polynomial in R[X] if and only if there exists a direct sum decomposition of R = R0 βŠ• . . . βŠ• Rm (m ≀ deg f ), associated to a fundamental system of idempotents e0, . . . , em, such that the component of f in each

The minimized dead-end elimination crite
The minimized dead-end elimination criterion and its application to protein redesign in a hybrid scoring and search algorithm for computing partition functions over molecular ensembles
✍ Ivelin Georgiev; Ryan H. Lilien; Bruce R. Donald πŸ“‚ Article πŸ“… 2008 πŸ› John Wiley and Sons 🌐 English βš– 668 KB

## Abstract One of the main challenges for protein redesign is the efficient evaluation of a combinatorial number of candidate structures. The modeling of protein flexibility, typically by using a rotamer library of commonly‐observed low‐energy side‐chain conformations, further increases the comple