Extending an Algebraic Modeling Language to Support Constraint Programming

  • Robert Fourer
  • David M. Gay
    • Categories Combinatorial Optimization, Modeling Languages and Systems Tags ,

    We describe extensions to algebraic modeling languages and their solver interfaces that will be needed to take advantage of constraint programming solvers, particularly in the area of combinatorial optimization. CitationTechnical Report, Department of Industrial Engineering and Management Sciences, Northwestern University (2001); based on a shorter version that appeared in the Proceedings of the Third International … Read more

    Solving a Class of Semidefinite Programs via Nonlinear Programming

  • Samuel Burer
  • Renato D.C. Monteiro
  • Yin Zhang
    • Categories Constrained Nonlinear Optimization, Semi-definite Programming

    In this paper, we introduce a transformation that converts a class of linear and nonlinear semidefinite programming (SDP) problems into nonlinear optimization problems. For those problems of interest, the transformation replaces matrix-valued constraints by vector-valued ones, hence reducing the number of constraints by an order of magnitude. The class of transformable problems includes instances of … Read more

    New Classes of Globally Convexized Filled Functions for Global Optimization

  • Stefano Lucidi
  • Veronica Piccialli
    • Categories Global Optimization Theory, Nonlinear Optimization Tags , ,

    We propose new classes of globally convexized filled functions. Unlike the globally convexized filled functions previously proposed in literature, the ones proposed in this paper are continuously differentiable and, under suitable assumptions, their unconstrained minimization allows to escape from any local minima of the original objective function. Moreover we show that the properties of the … Read more

    A genetic algorithm for the weight setting problem in OSPF routing

  • M. Ericsson
  • Panos M. Pardalos
  • Mauricio G.C. Resende
    • Categories Meta Heuristics, Telecommunications Tags , ,

    With the growth of the Internet, Internet Service Providers (ISPs) try to meet the increasing traffic demand with new technology and improved utilization of existing resources. Routing of data packets can affect network utilization. Packets are sent along network paths from source to destination following a protocol. Open Shortest Path First (OSPF) is the most … Read more

    A Polyhedral Study of the Cardinality Cosntrained Knapsack Problem

  • Ismael de Farias
  • George L. Nemhauser
    • Categories Branch and Cut Algorithms, Combinatorial Optimization, Integer Programming Tags , , ,

    A cardinality constrained knapsack problem is a continuous knapsack problem in which no more than a specified number of nonnegative variables are allowed to be positive. This structure occurs, for example, in areas as finance, location, and scheduling. Traditionally, cardinality constraints are modeled by introducing auxiliary 0-1 variables and additional constraints that relate the continuous … Read more

    Robust Capacity Planning in Semiconductor Manufacturing

  • Francisco Barahona
  • Oktay Gunluk
  • Stuart Bermon
  • Sarah Hood
    • Categories Supply Chain Management Tags ,

    We present a stochastic programming approach to capacity planning under demand uncertainty in semiconductor manufacturing. Given multiple demand scenarios together with associated probabilities, our aim is to arrive at a set of tools that does well across all of these scenarios. We formulate the problem as a mixed-integer program in which expected value of the … Read more

    Complexity of Convex Optimization using Geometry-based Measures and a Reference Point

  • Robert M. Freund
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

    Our concern lies in solving the following convex optimization problem: minimize cx subject to Ax=b, x \in P, where P is a closed convex set, not necessarily a cone. We bound the complexity of computing an almost-optimal solution of this problem in terms of natural geometry-based measures of the feasible region and the level-set of … Read more

    An Efficient Exact Algorithm for the Vertex p-Center Problem

  • T. Ilhan
  • Mustafa C. Pinar
    • Categories 0-1 Programming Tags , ,

    Inspired by an algorithm due to Minieka, we develop a simple and yet very efficient exact algorithm for the problem of locating p facilities and assigning clients to them in order to minimize the maximum distance between a client and the facility it is assigned to. After a lower bounding phase, the algorithm iteratively sets … Read more

    Strong semismoothness of eigenvalues of symmetric matrices and its application to inverse eigenvalue problems

  • Jie Sun
  • Defeng Sun
    • Categories Control Applications, Nonsmooth Optimization Tags , , , , ,

    It is well known that the eigenvalues of a real symmetric matrix are not everywhere differentiable. A classical result of Ky Fan states that each eigenvalue of a symmetric matrix is the difference of two convex functions. This directly implies that the eigenvalues of a symmetric matrix are semismooth everywhere. Based on a very recent … Read more

    New Benchmark Instances for the Steiner Problem in Graphs

  • Marcus Poggi de Aragão
  • Celso C. Ribeiro
  • Isabel Rosseti
  • Eduardo Uchoa
  • Renato F. Werneck
    • Categories Combinatorial Optimization, Graphs and Matroids, Meta Heuristics Tags , ,

    We propose in this work 50 new test instances for the Steiner problem in graphs. These instances are characterized by large integrality gaps and symmetry aspects which make them harder to both exact methods and heuristics than the test problems currently in use for the evaluation and comparison of existing and newly developed algorithms. Our … Read more