Semidefinite Optimization Approaches for Satisfiability and Maximum-Satisfiability Problems

  • Miguel F. Anjos
    • Categories Combinatorial Optimization, Linear, Cone and Semidefinite Programming Tags , , , , ,

    Semidefinite optimization, commonly referred to as semidefinite programming, has been a remarkably active area of research in optimization during the last decade. For combinatorial problems in particular, semidefinite programming has had a truly significant impact. This paper surveys some of the results obtained in the application of semidefinite programming to satisfiability and maximum-satisfiability problems. The … Read more

    An efficient algorithm for the earliness-tardiness scheduling problem

  • Safia Kedad-Sidhoum
  • Francis Sourd
    • Categories Scheduling Tags

    This paper addresses the one-machine scheduling problem with earliness-tardiness penalties. We propose a new branch-and-bound algorithm that can solve instances with up to 50 jobs and that can solve problems with even more general non-convex cost functions. The algorithm is based on the combination of a Lagrangean relaxation of resource constraints and new dominance rules. … Read more

    Anstreicher-Terlaky type monotonic simplex algorithms for linear feasibility problems

  • Zsolt Csizmadia
  • Tibor Illés
  • Bilen Filiz
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming Tags , , ,

    We define a variant of Anstreicher and Terlaky’s (1994) monotonic build-up (MBU) simplex algorithm for linear feasibility problems. Under a nondegeneracy assumption weaker than the normal one, the complexity of the algorithm can be given by $m\Delta$, where $\Delta$ is a constant determined by the input data of the problem and $m$ is the number … Read more

    Simulated Entropy and Global Optimization

  • Asaad M. Sultan
  • Andrew B. Templeman
    • Categories Combinatorial Optimization, Global Optimization Tags , ,

    Nonlinear optimization deals with the problem of optimizing a single objective function, such as physical weight or cost, in the presence of equality and inequality constraints. Usually engineering design applications are highly non-linear and engineers are always interested in not finding a feasible design that is locally optimal in the design space, but globally optimal … Read more

    Embedded in the Shadow of the Separator

  • Frank Göring
  • Christoph Helmberg
  • Markus Wappler
    • Categories Graphs and Matroids, Semi-definite Programming Tags , , , , ,

    We study the problem of maximizing the second smallest eigenvalue of the Laplace matrix of a graph over all nonnegative edge weightings with bounded total weight. The optimal value is the \emph{absolute algebraic connectivity} introduced by Fiedler, who proved tight connections of this value to the connectivity of the graph. Using semidefinite programming techniques and … Read more

    An Exact Primal-Dual Penalty Method Approach to Warmstarting Interior-Point Methods for Linear Programming

  • Hande Benson
  • David F. Shanno
    • Categories Linear Programming Tags , , ,

    One perceived deficiency of interior-point methods in comparison to active set methods is their inability to efficiently re-optimize by solving closely related problems after a warmstart. In this paper, we investigate the use of a primal-dual penalty approach to overcome this problem. We prove exactness and convergence and show encouraging numerical results on a set … Read more

    Postponing the Choice of the Barrier Parameter in Mehrotra-Type Predictor-Corrector Algorithms

  • Maziar Salahi
  • Tamás Terlaky
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    In \cite{SPT} the authors considered a variant of Mehrotra’s predictor-corrector algorithm that has been widely used in several IPMs based optimization packages. By an example they showed that this variant might make very small steps in order to keep the iterate in a certain neighborhood of the central path, that itself implies the inefficiency of … Read more

    Iterative Solution of Augmented Systems Arising in Interior Methods

  • Anders Forsgren
  • Philip E. Gill
  • Joshua D. Griffin
    • Categories Constrained Nonlinear Optimization Tags , , , , , , ,

    Iterative methods are proposed for certain augmented systems of linear equations that arise in interior methods for general nonlinear optimization. Interior methods define a sequence of KKT equations that represent the symmetrized (but indefinite) equations associated with Newton’s method for a point satisfying the perturbed optimality conditions. These equations involve both the primal and dual … Read more

    Topology optimization of a mechanical component subject to dynamical constraints

  • Sonia Calvel
  • Marcel Mongeau
    • Categories Applications - OR and Management Sciences, Applications - Science and Engineering, Optimization Software and Modeling Systems Tags , , , , , , , , ,

    This paper is concerned with the optimization of continuum structures under dynamic loading using methods from topology design. The constraint functions are non-linear and implicit, their evaluation requires the resolution of a computation-intensive finite-element analysis performed by a black-box commercial structural mechanics software such as MSC/Nastran. We first present a brief overview of topology optimization … Read more

    DIRECT algorithm : A new definition of potentially optimal hyperrectangles

  • Lakhdar Chiter
    • Categories Global Optimization

    We propose a new version of potentially optimal intervals for the DIRECT algorithm. A two-points based sampling method is presented. The method starts from a distingished point (the peak point) by forming an initial triangle. The idea is to sample the midpoint of a specific interval: the basis of the resulting triangle. This specific interval … Read more