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...
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...
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 Rayleigh–Ritz Method for Numerical Solutions of Linear Fredholm Integral Equations of the Second Kind
Kaya, Ruşen; Taşeli, Hasan (2022-01-01)
A Rayleigh–Ritz Method is suggested for solving linear Fredholm integral equations of the second kind numerically in a desired accuracy. To test the performance of the present approach, the classical one-dimensional Schrödinger equation -y″(x)+v(x)y(x)=λy(x),x∈(-∞,∞) has been converted into an integral equation. For a regular problem, the unbounded interval is truncated to x∈ [ - ℓ, ℓ] , where ℓ is regarded as a boundary parameter. Then, the resulting integral equation has been solved and the results are co...
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.