A strong conic quadratic reformulation for machine-job assignment with controllable processing times

  • M. Selim Akturk
  • Alper Atamturk
  • Sinan Gurel
    • Categories (Mixed) Integer Nonlinear Programming, Second-Order Cone Programming

    We describe a polynomial-size conic quadratic reformulation for a machine-job assignment problem with separable convex cost. Because the conic strengthening is based on only the objective of the problem, it can also be applied to other problems with similar cost functions. Computational results demonstrate the effectiveness of the conic reformulation. CitationAppeared in Operations Research Letters. … Read more

    The Flow Set with Partial Order

  • Alper Atamturk
  • Muhong Zhang
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches

    The flow set with partial order is a mixed-integer set described by a budget on total flow and a partial order on the arcs that may carry positive flow. This set is a common substructure of resource allocation and scheduling problems with precedence constraints and robust network flow problems under demand/capacity uncertainty. We give a … Read more

    Partition Inequalities for Capacitated Survivable Network Design Based on Directed P-Cycles

  • Alper Atamturk
  • Deepak Rajan
    • Categories Applications - OR and Management Sciences, Telecommunications

    We study the design of capacitated survivable networks using directed p-cycles. A p-cycle is a cycle with at least three arcs, used for rerouting disrupted flow during edge failures. Survivability of the network is accomplished by reserving sufficient slack on directed p-cycles so that if an edge fails, its flow can be rerouted along the … Read more

    An O(n^2) Algorithm for Lot Sizing with Inventory Bounds and Fixed Costs

  • Alper Atamturk
  • Simge Küçükyavuz
    • Categories Applications - OR and Management Sciences, Production and Logistics

    Lot-sizing problems with inventory bounds and fixed charges have not received much attention in the literature, even though there are many emerging applications in which highly specialized storage is the main activity of interest. The traditional infinite capacity and variable cost assumptions on inventory that have been prevalent in the literature are inappropriate in situations … Read more

    Max-min separability: incremental approach and application to supervised data classification

  • Adil Bagirov
  • Bulent Karasozen
  • Dean Webb
    • Categories Global Optimization Applications, Nonsmooth Optimization Tags , , ,

    A new algorithm for the computation of a piecewise linear function separating two finite point sets in $n$-dimensional space is developed and the algorithm is applied to solve supervised data classification problems. The algorithm computes hyperplanes incrementally and it finds as many hyperplanes as necessary to separate two sets with respect to some tolerance. An … Read more

    A new lower bound for one-machine earliness-tardiness scheduling

  • Francis Sourd
    • Categories Scheduling Tags , , , ,

    In one-machine scheduling, MIP time-indexed formulations are often used to provide very good lower bounds through Lagrangian relaxations. In order to get an improved lower bound, we add valid cuts to a time-indexed formulation and show we still have a Lagrangian relaxation that can be solved as a shortest path in a graph. Two branch-and-bound … Read more

    Semidefinite Representation of Convex Sets

  • J. William Helton
  • Jiawang Nie
    • Categories Convex Optimization, Global Optimization Theory, Semi-definite Programming Tags , , , , , , , , , , , , ,

    Let $S =\{x\in \re^n:\, g_1(x)\geq 0, \cdots, g_m(x)\geq 0\}$ be a semialgebraic set defined by multivariate polynomials $g_i(x)$. Assume $S$ is convex, compact and has nonempty interior. Let $S_i =\{x\in \re^n:\, g_i(x)\geq 0\}$, and $\bdS$ (resp. $\bdS_i$) be the boundary of $S$ (resp. $S_i$). This paper, as does the subject of semidefinite programming (SDP), concerns … Read more

    Minimum weight t-composition of an integer

  • Domingos M. Cardoso
  • J. Orestes Cerdeira
    • Categories Combinatorial Optimization Tags , , ,

    If $p \geq t$ are positive integers, a t-composition of p is an ordered t-tuple of positive integers summing p. If $T=(s_1, s_2, \dots, s_t)$ is a t-composition of p and W is a $p-(t-1) \times t$ matrix, call $W(T)= \sum_{k=1}^t w_{s_k k}$ the weight of the t-composition T. We show that finding a minimum … Read more

    A globally convergent trust-region SQP method without a penalty function for nonlinearly constrained optimization

  • Hiroshi Yabe
  • Hiroshi Yamashita
    • Categories Constrained Nonlinear Optimization Tags , ,

    In this paper, we propose a new trust-region SQP method, which uses no penalty function, for solving nonlinearly constrained optimization problem. Our method consists of alternate two phases. Specifically, we alternately proceed the feasibility restoration phase and the objective function minimization phase. The global convergence property of the proposed method is shown. CitationCooperative Research Report … Read more

    A primal-dual interior point method for nonlinear semidefinite programming

  • Kouhei Harada
  • Hiroshi Yabe
  • Hiroshi Yamashita
    • Categories Constrained Nonlinear Optimization Tags , , , ,

    In this paper, we consider a primal-dual interior point method for solving nonlinear semidefinite programming problems. By combining the primal barrier penalty function and the primal-dual barrier function, a new primal-dual merit function is proposed within the framework of the line search strategy. We show the global convergence property of our method. Finally some numerical … Read more