Fatma Kılınç-Karzan

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.
Information-based branching schemes for binary linear mixed-integer 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 mixed-integer 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 time-critical 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 Large-Scale 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 first-order algorithms for solving bilinear saddle points problems. Our developments are motivated by the need for sublinear time algorithms to solve large-scale {\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 sparsity-oriented Signal Processing. We demonstrate, both theoretically and by numerical examples, that when seeking for medium-accuracy solutions of large-scale $\ell_1$ minimization problems, our randomized algorithms outperform significantly (and progressively as the sizes of the problem grow) the state-of-the 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 entry-wise 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\{\|W-Y^T_m A_m\|_\infty\} \leq O(1)L(Y;A)\sqrt{\ln(n) \over m}$. Here $L(Y;A)$ is an easy-to-specify 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.
Information-based branching schemes for binary linear mixed-integer 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 branch-and-bound 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 mixed-integer 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 re-optimization. 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 Branch-and-Bound algorithm and a Beam Search procedure, and report results from a computational experiment. We find that optimal solutions can be quickly obtained for medium-sized instances with 25 jobs and 25 tools. For large-sized problem instances, Beam Search provides high quality solutions very quickly. Finally, we address the problem of minimizing the total flow time.

Scheduling time-critical 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.
Time-critical flowshops are a special class of problems characterized by a tight constraint that restricts the work-in-progress (WIP) at any station to be zero. These problems are commonly encountered in metals and chemicals related manufacturing and no-WIP restriction signifcantly increases the difficulty of generating feasible schedules. We present a novel approach to solve this class of problems by strengthening the logic-based 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 on-time 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%.