NONLINEAR OPTIMIZATION IN MODELING ENVIRONMENTS: Software Implementations for Compilers, Spreadsheets, Modeling Languages, and Integrated Computing Systems

  • János Pintér
    • Categories Applications - Science and Engineering, Global Optimization, Optimization Software and Modeling Systems Tags ,

    We present a review of several professional software products that serve to analyze and solve nonlinear (global and local) optimization problems across a variety of hardware and software environments. The product versions discussed have been implemented for compiler platforms, spreadsheets, algebraic (optimization) modeling languages, and for integrated scientific-technical computing systems. The discussion highlights some of … Read more

    Active Set Identification in Nonlinear Programming

  • Christina Oberlin
  • Stephen Wright
    • Categories Constrained Nonlinear Optimization Tags , ,

    Techniques that identify the active constraints at a solution of a nonlinear programming problem from a point near the solution can be a useful adjunct to nonlinear programming algorithms. They have the potential to improve the local convergence behavior of these algorithms, and in the best case can reduce an inequality constrained problem to an … Read more

    A Full-Newton Step (n)$ Infeasible Interior-Point Algorithm for Linear Optimization

  • Cornelis Roos
    • Categories Linear Programming Tags ,

    We present a full-Newton step infeasible interior-point algorithm. It is shown that at most $O(n)$ (inner) iterations suffice to reduce the duality gap and the residuals by the factor $\frac1{e}$. The bound coincides with the best known bound for infeasible interior-point algorithms. It is conjectured that further investigation will improve the above bound to $O(\sqrt{n})$. … Read more

    Strengthened Semidefinite Bounds for Codes

  • Monique Laurent
    • Categories Combinatorial Optimization, Semi-definite Programming Tags , , ,

    We give a hierarchy of semidefinite upper bounds for the maximum size $A(n,d)$ of a binary code of word length $n$ and minimum distance at least $d$. At any fixed stage in the hierarchy, the bound can be computed (to an arbitrary precision) in time polynomial in $n$; this is based on a result of … Read more

    A Population Based Approach for Hard Global Optimization Problems Based on Dissimilarity Measures

  • Andrea Grosso
  • Marco Locatelli
  • Fabio Schoen
    • Categories Chemical Engineering, Global Optimization, Stochastic Approaches Tags , , , , ,

    When dealing with extremely hard global optimization problems, i.e. problems with a large number of variables and a huge number of local optima, heuristic procedures are the only possible choice. In this situation, lacking any possibility of guaranteeing global optimality for most problem instances, it is quite difficult to establish rules for discriminating among different … Read more

    A PTAS for the minimization of polynomials of fixed degree over the simplex

  • Etienne de Klerk
  • Monique Laurent
  • Pablo A. Parrilo
    • Categories Approximation Algorithms, Global Optimization Theory, Semi-definite Programming Tags , , , ,

    We consider the problem of computing the minimum value $p_{\min}$ taken by a polynomial $p(x)$ of degree $d$ over the standard simplex $\Delta$. This is an NP-hard problem already for degree $d=2$. For any integer $k\ge 1$, by minimizing $p(x)$ over the set of rational points in $\Delta$ with denominator $k$, one obtains a hierarchy … Read more

    Algorithms for the quasiconvex feasibility problem

  • Yair Censor
  • Alexander Segal
    • Categories Convex and Nonsmooth Optimization Tags , , , , ,

    We study the behavior of subgradient projection algorithms for the quasiconvex feasibility problem of finding a point x^* in R^n that satisfies the inequalities f_i(x^*) less or equal 0, for all i=1,2,…,m, where all functions are continuous and quasiconvex. We consider the consistent case when the solution set is nonempty. Since the Fenchel-Moreau subdifferential might … Read more

    A branch and cut algorithm for solving the linear and quadratic integer programming problems

  • Fei Pusheng
  • Yan Zizong
  • Wan Zhongping
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Integer Programming Tags , , , ,

    This paper first presents an improve cutting plane method for solving the linear programming problems, based on the primal simplex method with the current equivalent facet technique, in which the increment of objection function is allowed as a pivot variable to decide the search step size. We obtain a strong valid inequality from the objective … Read more

    A Case Study of Joint Online Truck Scheduling and Inventory Management for Multiple Warehouses

  • Christoph Helmberg
  • Stefan Röhl
    • Categories (Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Convex Optimization Tags , , , , , , ,

    For a real world problem — transporting pallets between warehouses in order to guarantee sufficient supply for known and additional stochastic demand — we propose a solution approach via convex relaxation of an integer programming formulation, suitable for online optimization. The essential new element linking routing and inventory management is a convex piecewise linear cost … Read more