A Simplicial Branch-and-Bound Algorithm for Solving Quadratically Constrained Quadratic Programs

  • Jeff Linderoth
    • Categories Global Optimization Theory Tags , , ,

    We propose a branch-and-bound algorithm for solving nonconvex quadratically-constrained quadratic programs. The algorithm is novel in that branching is done by partitioning the feasible region into the Cartesian product of two-dimensional triangles and rectangles. Explicit formulae for the convex and concave envelopes of bilinear functions over triangles and rectangles are derived and shown to be … Read more

    Vehicle routing and staffing for sedan service

  • Oktay Gunluk
  • Lazslo Ladanyi
  • Baruch Schieber
  • Tracy Kimbrel
  • Gregory B. Sorkin
    • Categories Integer Programming, Transportation Tags , , ,

    We present the optimization component of a decision support system developed for a sedan service provider. The system assists supervisors and dispatchers in scheduling driver shifts and routing the fleet throughout the day to satisfy customer demands within tight time windows. We periodically take a snapshot of the dynamic data and formulate an integer program, … Read more

    Gradient-Controlled, Typical-Distance Clustering for Global Optimization

  • Isaac Lagaris
  • I.G. Tsoulos
    • Categories Global Optimization, Stochastic Approaches Tags , ,

    We present a stochastic global optimization method that employs a clustering technique which is based on a typical distance and a gradient test. The method aims to recover all the local minima inside a rectangular domain. A new stopping rule is used. Comparative results on a set of test functions are reported. CitationPreprint, no 4-5/2004 … Read more

    Portfolio Investment with the Exact Tax Basis via Nonlinear Programming

  • Victor DeMiguel
  • Raman Uppal
    • Categories Finance and Economics, Stochastic Programming Tags , ,

    Computing the optimal portfolio policy of an investor facing capital gains tax is a challenging problem: because the tax to be paid depends on the price at which the security was purchased (the tax basis), the optimal policy is path dependent and the size of the problem grows exponentially with the number of time periods. … Read more

    A semidefinite programming based polyhedral cut and price algorithm for the maxcut problem

  • Kartik Krishnan
  • John E. Mitchell
    • Categories Branch and Cut Algorithms, Semi-definite Programming Tags , , ,

    We investigate solution of the maximum cut problem using a polyhedral cut and price approach. The dual of the well-known SDP relaxation of maxcut is formulated as a semi-infinite linear programming problem, which is solved within an interior point cutting plane algorithm in a dual setting; this constitutes the pricing (column generation) phase of the … Read more

    A sequential quadratic programming algorithm with a piecewise linear merit function

  • Francisco Gomes
    • Categories Constrained Nonlinear Optimization Tags , ,

    A sequential quadratic programming algorithm for solving nonlinear programming problems is presented. The new feature of the algorithm is related to the definition of the merit function. Instead of using one penalty parameter per iteration and increasing it as the algorithm progresses, we suggest that a new point is to be accepted if it stays … Read more

    Benchmarking Optimization Software with COPS 3.0

  • Elizabeth D. Dolan
  • Jorge MorĂ©
  • Todd S. Munson
    • Categories Constrained Nonlinear Optimization, Optimization Software Benchmark

    We describe version 3.0 of the COPS set of nonlinearly constrained optimization problems. We have added new problems, as well as streamlined and improved most of the problems. We also provide a comparison of the FILTER, KNITRO, LOQO, MINOS, and SNOPT solvers on these problems. CitationTechnical Report ANL/MCS-TM-273, Argonne National Laboratory, 02/04.ArticleDownload View PDF

    Optimality Measures for Performance Profiles

  • Elizabeth D. Dolan
  • Jorge MorĂ©
  • Todd S. Munson
    • Categories Nonlinear Optimization Tags ,

    We examine the importance of optimality measures when benchmarking a set of solvers, and show that scaling requirements lead to a convergence test for nonlinearly constrained optimization solvers that uses a mixture of absolute and relative error measures. We demonstrate that this convergence test is well behaved at any point where the constraints satisfy the … Read more

    Implementation of Infinite Dimensional Interior Point Method for Solving Multi-criteria Linear-Quadratic Control Problem

  • Leonid Faybusovich
  • Takashi Tsuchiya
  • Thanasak Mouktonglang
    • Categories Control Applications, Infinite Dimensional Optimization, Linear, Cone and Semidefinite Programming Tags , ,

    We describe an implementation of an infinite-dimensional primal-dual algorithm based on the Nesterov-Todd direction. Several applications to both continuous and discrete-time multi-criteria linear-quadratic control problems and linear-quadratic control problem with quadratic constraints are described. Numerical results show a very fast convergence (typically, within 3-4 iterations) to optimal solutions CitationPreprint, May, 2004, University of Notre DameArticleDownload … Read more

    Sensitivity analysis for linear optimization problem with fuzzy data in the objective function

  • Stephan Dempe
  • Tatiana Starostina
    • Categories Linear Programming, Robust Optimization Tags , ,

    Linear programming problems with fuzzy coefficients in the objective function are considered. Emphasis is on the dependence of the optimal solution from linear perturbations of the membership functions of the objective function coefficients as well as on the computation of a robust solution of the fuzzy linear problem if the membership functions are not surely … Read more