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

Download
2009-05-01
Akturk, M. Selim
Atamturk, Alper
Gürel, Sinan
we describe a polynomial-size conic quadratic reformulation for a machine-job assignment problem with separable convex cost. Because the conic strengthening is based only on 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.
OPERATIONS RESEARCH LETTERS

Suggestions

A stagnation-aware cooperative parallel breakout local search algorithm for the quadratic assignment problem
Aksan, Yagmur; Dokeroglu, Tansel; Coşar, Ahmet (2017-01-01)
The Quadratic Assignment Problem (QAP) is one of the most challenging NP-Hard combinatorial optimization problems. Circuit-layout design, transportation/traffic engineering, and assigning gates to airplanes are some of the interesting applications of the QAP. In this study, we introduce an enhanced version of a recent local search heuristic, Breakout Local Search Algorithm (BLS), by using the Levenshtein Distance metric for checking the similarity of the new starting points to previously explored QAP permut...
Characterisation and enumeration of a class of semi bent quadratic Boolean functions
KOÇAK, Neşe; Koçak, Onur Ozan; Özbudak, Ferruh; SAYGI, ZÜLFÜKAR (2015-01-01)
In this paper, we consider semi-bentness of quadratic Boolean functions defined for even n and give the characterisation of these functions. Up to our knowledge, semi-bentness of this class has not been investigated before and we proved that semi-bent functions of this form exist only for 6|n. Furthermore, we present a method for enumeration of semi-bent and bent functions in certain classes. Using this method we find the exact number of semi-bent functions of this form. Moreover, we complete some previous ...
A robust Island Parallel Genetic Algorithm for the Quadratic Assignment Problem
Tosun, Umut; Dokeroglu, Tansel; Coşar, Ahmet (2013-07-01)
The Quadratic Assignment Problem (QAP) is a difficult and important problem studied in the domain of combinatorial optimisation. It is possible to solve QAP instances with 10--20 facilities using exhaustive parallel algorithms within a few days on a cluster machine. However, large QAP instances with more than 100 facilities are not solvable using exhaustive techniques. We have explored a variety of Genetic Algorithm crossover operators for this problem and verified its performance experimentally using well-...
A Stagnation aware cooperative breakout local search algorithm for the quadratic assignment problem on a multi-core architecture
Aksan, Yağmur; Coşar, Ahmet; Dökeroğlu, Tansel; Department of Computer Engineering (2016)
The quadratic assignment problem (QAP) is one of the most challenging NP-Hard combinatorial optimization problems with its several real life applications. Layout design, scheduling, and assigning gates to planes at an airport are some of the interesting applications of the QAP. In this thesis, we improve the talents of a recent local search heuristic Breakout Local Search Algorithm (BLS) by using adapted Levenshtein Distance metric for similarity checking of the previously explored permutations of the QAP p...
The number of irreducible polynomials over finite fields with vanishing trace and reciprocal trace
Çakıroğlu, Yağmur; Yayla, Oğuz; Yılmaz, Emrah Sercan (2022-08-01)
We present the formula for the number of monic irreducible polynomials of degree n over the finite field F-q where the coefficients of x(n)(-1) and x vanish for n >= 3. In particular, we give a relation between rational points of algebraic curves over finite fields and the number of elements a is an element of F-qn for which Trace(a) = 0 and Trace(a(-1)) = 0.
Citation Formats
M. S. Akturk, A. Atamturk, and S. Gürel, “A strong conic quadratic reformulation for machine-job assignment with controllable processing times,” OPERATIONS RESEARCH LETTERS, pp. 187–191, 2009, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/38772.