Journal Articles
 On low rank matrix approximations with applications to synthesis problem in Compressed Sensing, Judistky, A., KılınçKarzan, F., Nemirovski, A. (2010) , to appear in SIAM Journal on Matrix Analysis and Applications.
 Verifiable conditions of $\ell_1$recovery for sparse signals with sign restrictions, Judistky, A., KılınçKarzan, F., Nemirovski, A. (2010) , to appear in Mathematical Programming.
 Informationbased branching schemes for binary linear mixedinteger programs, KılınçKarzan, F., Nemhauser, G.L., Savelsbergh, M.W.P. (2009) , Mathematical Programming Computations, 1(4), 249  293.
 Approximating the stability region for binary mixedinteger programs, KılınçKarzan, F., Toriello, A., Ahmed, S., Nemhauser, G.L., Savelsbergh, M.W.P. (2009) , Operations Research Letters, 37(4), 250  254.
 The tool transporter movements problem in flexible manufacturing systems, KılınçKarzan, F., Azizoglu, M. (2008) , International Journal of Production Research, 46(11), 3059  3084.
Working Papers
 $\ell_1$ minimization via randomized first order algorithms, Judistky, A., KılınçKarzan, F., Nemirovski, A. (2011) , submitted.
 Scheduling timecritical flowshops: An example from the steel industry, KılınçKarzan, F., Kalagnanam, J.R., Davenport, A.J., Siegel, S., Reddy, C. (2008) , IBM technical report.
Thesis
 Tractable Relaxations and Efficient Algorithmic Techniques for LargeScale Optimization, Ph.D. Thesis. Georgia Institute of Technology, Atlanta, GA, USA (August 2011).
 The Tool Transporter Movements Problem in Flexible Manufacturing Systems, M.Sc. Thesis. Middle East Technical University, Ankara, TURKEY (April 2005).
Publication Details

$\ell_1$ minimization via randomized first order algorithms,
Judistky, A., KılınçKarzan, F., Nemirovski, A. (2011) ,
submitted.
In the paper, we propose randomized firstorder algorithms for solving bilinear saddle points problems. Our developments are motivated by the need for sublinear time algorithms to solve largescale {\sl parametric} bilinear saddle point problems where cheap online assessment of solution quality is crucial. We present the theoretical efficiency estimates of our algorithms and discuss a number of applications, primarily to the problem of $\ell_1$ minimization arising in sparsityoriented Signal Processing. We demonstrate, both theoretically and by numerical examples, that when seeking for mediumaccuracy solutions of largescale $\ell_1$ minimization problems, our randomized algorithms outperform significantly (and progressively as the sizes of the problem grow) the stateofthe art deterministic methods.

On low rank matrix approximations with applications to synthesis problem in Compressed Sensing,
Judistky, A., KılınçKarzan, F., Nemirovski, A. (2011) ,
to appear in SIAM Journal on Matrix Analysis and Applications.
We consider the {\sl synthesis problem} of Compressed Sensing given $s$ and an $M\times n$ matrix $A$, extract from it an $m\times n$ submatrix $A_m$, with $m$ as small as possible, which is $s$good, that is, every signal $x$ with at most $s$ nonzero entries can be recovered from observation $A_m x$ by $\ell_1$ minimization: $x = \argmin_u \{\u\_1 : A_m u =A_m x \}$. We show that under reasonable assumptions the synthesis problem can be reformulated as the problem of entrywise approximation, within a given accuracy, of $n \times n$ matrix $W=Y^TA$, with $Y \in R^{M \times n}$ given, by a matrix of the form $Y^T_m A_m$, with $A_m$ comprised of $m$ rows of $A$. We propose randomized algorithms for efficiently solving the latter problem with accuracy guaranties $E\{\WY^T_m A_m\_\infty\} \leq O(1)L(Y;A)\sqrt{\ln(n) \over m}$. Here $L(Y;A)$ is an easytospecify quantity which in good cases is a moderate absolute constant (e.g., $L(A;A)=1$ when $A$ is a Hadamard matrix, and similarly the matrix of Fourier transform on any finite Abelian group). We also supply derandomized versions of the approximation algorithms which do not require random sampling of matrices and attain the same accuracy bounds. We further demonstrate that in terms of approximation accuracy our algorithms are optimal up to logarithmic in $n$ factors. Finally, we provide preliminary numerical results on the performance of our algorithms for the synthesis problem.

Verifiable conditions of $\ell_1$recovery of sparse signals with sign restrictions,
Judistky, A., KılınçKarzan, F., Nemirovski, A. (2010) ,
Mathematical Programming, 127(1), 89  122.
We propose necessary and sufficient conditions for a sensing matrix to be ``$s$semigood''  to allow for exact $\ell_1$recovery of sparse signals with at most $s$ nonzero entries under sign restrictions on part of the entries. We expres error bounds for imperfect $\ell_1$recovery in terms of the characteristics underlying these conditions. These characteristics, although difficult to evaluate, lead to verifiable sufficient conditions for exact sparse $\ell_1$recovery and thus efficiently computable lower bounds on those $s$ for which a given sensing matrix is $s$semigood. We examine the properties of proposed verifiable sufficient conditions, describe their limits of performance and provide numerical examples comparing them with other verifiable conditions from the literature.

Informationbased branching schemes for binary linear mixedinteger programs,
KılınçKarzan, F., Nemhauser, G.L., Savelsbergh, M.W.P. (2009) ,
Mathematical Programming Computations, 1(4), 249  293.
Branching variable selection can greatly affect the effectiveness and efficiency of a branch and bound algorithm. Traditional approaches to branching variable selection rely on estimating the effect of the candidate variables on the objective function. We propose an approach which is empowered by exploiting the information contained in a family of fathomed subproblems, collected beforehand from an incomplete branchandbound tree. In particular, we use this information to define new branching rules that reduce the risk of incurring inappropriate branchings. We provide computational results that demonstrate the effectiveness of the new branching rules on various benchmark instances.

Approximating the stability region for binary mixedinteger programs,
KılınçKarzan, F., Toriello, A., Ahmed, S., Nemhauser, G.L., Savelsbergh, M.W.P. (2009) ,
Operations Research Letters, 37(4), 250  254.
The stability region of a solution is the polyhedral set of objective coefficients for which the solution is optimal. It provides valuable information for sensitivity analysis and reoptimization. An exact description of it may require an exponential number of inequalities. We develop polyhedral inner and outer approximations of linear size.

The tool transporter movements problem in flexible manufacturing systems,
KılınçKarzan, F., Azizoglu, M. (2008) ,
International Journal of Production Research, 46(11), 3059  3084.
We consider a job sequencing and tool transporter movements problem on a single flexible machine with limited tool magazine capacity. A tool transporter having limited capacity is used in transporting the tools between the machine and tool crib area. Our aim is to minimize the number of the tool transporter movements. We present several lower and upper bounds, propose a BranchandBound algorithm and a Beam Search procedure, and report results from a computational experiment. We find that optimal solutions can be quickly obtained for mediumsized instances with 25 jobs and 25 tools. For largesized problem instances, Beam Search provides high quality solutions very quickly. Finally, we address the problem of minimizing the total flow time.

Scheduling timecritical flowshops: An example from the steel industry,
KılınçKarzan, F., Kalagnanam, J.R., Davenport, A.J., Siegel, S., Reddy, C. (2008) ,
IBM technical report.
Timecritical flowshops are a special class of problems characterized by a tight constraint that restricts the workinprogress (WIP) at any station to be zero. These problems are commonly encountered in metals and chemicals related manufacturing and noWIP restriction signifcantly increases the difficulty of generating feasible schedules. We present a novel approach to solve this class of problems by strengthening the logicbased Benders decomposition with a special class of aggregate resource use inequalities that allow us to generate feasible solutions that cannot be achieved by the traditional approaches. We generate the aggregate resource use constraints using a detailed constraint programming based schedule for each job. We apply this method to a flowshop scheduling problem arising in the steel manufacturing industry with the objective of maximizing ontime delivery while keeping productivity at desired high levels. The solution has been successfully deployed in the daily operations of a large integrated steelmaker with improvements in ontime delivery from 75% to over 90%.