@article{Kianfar2018,

title = {Optimum Search Schemes for Approximate String Matching Using Bidirectional FM-Index},

author = {Kiavash Kianfar and Christopher Pockrandt and Bahman Torkamandi and Haochen Luo and Knut Reinert},

url = {https://arxiv.org/abs/1711.02035v2},

year  = {2018},

date = {2018-01-01},

journal = {In review},

abstract = {Finding approximate occurrences of a pattern in a text using a full-text index is a central problem in bioinformatics and has been extensively researched. Bidirectional indices have opened new possibilities in this regard allowing the search to start from anywhere within the pattern and extend in both directions. In particular, use of search schemes (partitioning the pattern and searching the pieces in certain orders with given bounds on errors) can yield significant speed-ups. However, finding optimal search schemes is a difficult combinatorial optimization problem. 

Here for the first time, we propose a mixed integer program (MIP) capable to solve this optimization problem for Hamming distance with given number of pieces. Our experiments show that the optimal search schemes found by our MIP significantly improve the performance of search in bidirectional FM-index upon previous ad-hoc solutions. For example, approximate matching of 101-bp Illumina reads (with two errors) becomes 35 times faster than standard backtracking. Moreover, despite being performed purely in the index, the running time of search using our optimal schemes (for up to two errors) is comparable to the best state-of-the-art aligners, which benefit from combining search in index with in-text verification using dynamic programming. As a result, we anticipate a full-fledged aligner that employs an intelligent combination of search in the bidirectional FM-index using our optimal search schemes and in-text verification using dynamic programming outperforms today's best aligners. The development of such an aligner, called FAMOUS (Fast Approximate string Matching using OptimUm search Schemes), is ongoing as our future work.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

@article{Bansal2017,

title = {Facets for continuous multi-mixing set with general coefficients and bounded integer variables},

author = {Manish Bansal and Kiavash Kianfar},

url = {https://doi.org/10.1016/j.disopt.2017.05.002},

year  = {2017},

date = {2017-05-31},

journal = {Discrete Optimization},

volume = {26},

pages = {1-25},

abstract = {Bansal and Kianfar (2015) introduced continuous multi-mixing set where the coefficients satisfy the so-called n-step MIR conditions and developed facet-defining inequalities for this set. In this paper, we first generalize their inequalities for the continuous multi-mixing set with general coefficients (where no conditions are imposed on the coefficients) and show that they are facet-defining in many cases. Next, we further generalize the continuous multi-mixing set with general coefficients by incorporating upper bounds on the integer variables. We introduce a family of valid inequalities for this set through a unified generalization of the n-step cycle inequalities and the mingled -step MIR inequalities. We indicate how to separate over these inequalities in polynomial time and present the conditions under which a subset of these inequalities are facet-defining.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

@article{Bansal2017b,

title = {Planar Maximum Coverage Location Problem with Partial Coverage and Rectangular Demand and Service Zones},

author = {Manish Bansal and Kiavash Kianfar},

url = {https://doi.org/10.1287/ijoc.2016.0722},

year  = {2017},

date = {2017-01-03},

journal = {INFORMS Journal on Computing},

volume = {29},

pages = {152-169},

abstract = {We study the planar maximum coverage location problem (MCLP) with rectilinear distance and rectangular demand zones in the case where “partial coverage” is allowed in its true sense, i.e., when covering part of a demand zone is allowed and the coverage accrued as a result of this is proportional to the demand of the covered part only. We pose the problem in a slightly more general form by allowing service zones to be rectangular instead of squares, thereby addressing applications in camera view-frame selection as well. More specifically, our problem, referred to as PMCLP-PCR (planar MCLP with partial coverage and rectangular demand and service zones), is to position a given number of rectangular service zones (SZs) on the two-dimensional plane to (partially) cover a set of existing (possibly overlapping) rectangular demand zones (DZs) such that the total covered demand is maximized. Previous studies on (planar) MCLP have assumed binary coverage, even when nonpoint objects such as lines or polygons have been used to represent demand. Under the binary coverage assumption, the problem can be readily formulated and solved as a binary linear program; whereas, partial coverage, although much more realistic, cannot be efficiently handled by binary linear programming, making PMCLP-PCR much more challenging to solve. In this paper, we first prove that PMCLP-PCR is NP-hard if the number of SZs is part of the input. We then present an improved algorithm for the single-SZ PMCLP-PCR, which is at least two times faster than the existing exact plateau vertex traversal algorithm. Next, we study multi-SZ PMCLP-PCR for the first time and prove theoretical properties that significantly reduce the search space for solving this problem, and we present a customized branch-and-bound exact algorithm to solve it. Our computational experiments show that this algorithm can solve relatively large instances of multi-SZ PMCLP-PCR in a short time. We also propose a fast polynomial time heuristic algorithm. Having optimal solutions from our exact algorithm, we benchmark the quality of solutions obtained from our heuristic algorithm. Our results show that for all the random instances solved to optimality by our exact algorithm, our heuristic algorithm finds a solution in a fraction of a second, where its objective value is at least 91% of the optimal objective in 90% of the instances (and at least 69% of the optimal objective in all the instances).},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

@article{Sanjeevi2016,

title = {Using cuts for mixed integer knapsack sets to generate cuts for mixed integer polyhedral conic sets},

author = {Sujeevraja Sanjeevi and Sina Masihabadi and Kiavash Kianfar},

url = {https://doi.org/10.1007/s10107-015-0959-1},

issn = {0025-5610},

year  = {2016},

date = {2016-09-01},

journal = {Mathematical Programming},

volume = {159},

pages = {571-583},

abstract = {Based on a bijective mapping between two mixed integer sets, we introduce a new perspective on developing cuts for the mixed integer polyhedral conic (MIPC) set by establishing a one-to-one correspondence between the cuts for this set and those for a related mixed integer knapsack (MIK) set. The face/facet-defining properties of the corresponding cuts are identical for their respective sets. We further show that the cut generation approach for the MIPC set resulting from this new perspective always produces cuts that dominate those generated based on any of the two individual MIK constraints corresponding to the MIPC constraint. Our computational results show this dominance can be quite significant. As a special case of this new perspective, the conic MIR inequality of Atamtürk  and Narayanan for the MIPC set and its properties can be directly derived from the MIR inequality for the MIK set and its properties. We also generalize these cuts to the n-step conic MIR inequalities, which are directly derived form the n-step MIR inequalities for the MIK set.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

@article{Bansal2015,

title = {n-Step cycle inequalities: facets for continuous multi-mixing set and strong cuts for multi-module capacitated lot-sizing problem},

author = {Manish Bansal and Kiavash Kianfar},

doi = {https://doi.org/10.1007/s10107-015-0906-1},

issn = {0025-5610},

year  = {2015},

date = {2015-04-28},

journal = {Mathematical Programming},

volume = {154},

pages = {113-144},

abstract = {In this paper, we introduce a generalization of the continuous mixing set, which we refer to as the continuous multi-mixing set. This set is closely related to the feasible set of the multi-module capacitated lot-sizing (MML) problem with(out) backlogging. We present a family of valid inequalities for the continuous multi-mixing set and identify conditions under which they are facet-defining. The cycle inequalities,   n-step MIR inequalities, and mixed   n-step MIR inequalities are special cases of these inequalities. We also present an exact separation algorithm for our inequalities. We then use these inequalities to generate valid inequalities for MML with(out) backlogging. Our computational results show that our cuts are very effective in solving the MML instances, resulting in substantial reduction in the integrality gap, number of nodes, and total solution time.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

@article{Bansal2013,

title = {Hybridization of Bound-and-Decompose and Mixed Integer Feasibility Checking to Measure Redundancy in Structured Linear Systems},

author = {Manish Bansal and Kiavash Kianfar and Yu Ding and Erick Moreno-Centeno},

url = {https://doi.org/10.1109/TASE.2013.2259479},

issn = {1558-3783},

year  = {2013},

date = {2013-05-23},

journal = {IEEE Transactions on Automation Science and Engineering },

volume = {10},

pages = {1151-1157},

abstract = {Computing the degree of redundancy for structured linear systems is proven to be NP-hard. A linear system whose model matrix is of size n×p is considered structured if some p row vectors in the model matrix are linearly dependent. Bound-and-decompose and 0-1 mixed integer programming (MIP) are two approaches to compute the degree of redundancy, which were previously proposed and compared in the literature. In this paper, first we present an enhanced version of the bound-and-decompose algorithm, which is substantially (up to 30 times) faster than the original version. We then present a novel hybrid algorithm to measure redundancy in structured linear systems. This algorithm uses a 0-1 mixed integer feasibility checking algorithm embedded within a bound-and-decompose framework. Our computational study indicates that this new hybrid approach significantly outperforms the existing algorithms as well as our enhanced version of bound-and-decompose in several instances. We also perform a computational study that shows matrix density has a significant effect on the runtime of the algorithms.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

@article{Sanjeevi2012,

title = {Mixed n-step MIR inequalities: Facets for the n-mixing set},

author = {Sujeevraja Sanjeevi and Kiavash Kianfar},

url = {https://doi.org/10.1016/j.disopt.2012.07.003},

year  = {2012},

date = {2012-11-01},

journal = {Discrete Optimization},

volume = {9},

pages = {216-235},

abstract = {Günlük and Pochet [O. Günlük, Y. Pochet, Mixing mixed integer inequalities. Mathematical Programming 90 (2001) 429–457] proposed a procedure to mix mixed integer rounding (MIR) inequalities. The mixed MIR inequalities define the convex hull of the mixing set  and can also be used to generate valid inequalities for general as well as several special mixed integer programs (MIPs). In another direction, Kianfar and Fathi [K. Kianfar, Y. Fathi, Generalized mixed integer rounding inequalities: facets for infinite group polyhedra. Mathematical Programming 120 (2009) 313–346] introduced the n-step MIR inequalities for the mixed integer knapsack set through a generalization of MIR. In this paper, we generalize the mixing procedure to the n-step MIR inequalities and introduce the mixed n-step MIR inequalities. We prove that these inequalities define facets for a generalization of the mixing set with  integer variables in each row (which we refer to as the n-mixing set) . The mixed MIR inequalities are simply the special case of . We also show that mixed n-step MIR can generate valid inequalities based on multiple constraints for general MIPs. Moreover, we introduce generalizations of the capacitated lot-sizing and facility location problems, which we refer to as the multi-module problems, and show that mixed n-step MIR can be used to generate valid inequalities for these generalizations. Our computational results on small MIPLIB instances as well as a set of multi-module lot-sizing instances justify the effectiveness of the mixed n-step MIR inequalities.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

@article{Kianfar2012,

title = {On n-step MIR and partition inequalities for integer knapsack and single-node capacitated flow sets},

author = {Kiavash Kianfar},

url = {https://doi.org/10.1016/j.dam.2012.02.025},

year  = {2012},

date = {2012-07-01},

journal = {Discrete Applied Mathematics},

volume = {160},

pages = {1567-1582},

abstract = {Pochet and Wolsey [Y. Pochet, L.A. Wolsey, Integer knapsack and flow covers with divisible coefficients: polyhedra, optimization and separation, Discrete Applied Mathematics 59 (1995) 57–74] introduced partition inequalities for three substructures arising in various mixed integer programs, namely the integer knapsack set with nonnegative divisible/arbitrary coefficients and two forms of single-node capacitated flow set with divisible coefficients. They developed the partition inequalities by proving properties of the optimal solution in optimizing a linear function over these sets. More recently, the author and Fathi [K. Kianfar, Y. Fathi, Generalized mixed integer rounding inequalities: facets for infinite group polyhedra, Mathematical Programming 120 (2009) 313–346] have introduced the n-step mixed integer rounding (MIR) inequalities for the mixed-integer knapsack set with arbitrary coefficients through a generalization of MIR. In this paper, we show that the n-step MIR generates facet-defining inequalities not only for the three sets considered by Pochet and Wolsey but also for their generalization to the case where coefficients are not necessarily divisible. In the case of divisible coefficients, n-step MIR directly generates the partition inequalities for all three sets (and in some cases stronger inequalities for one of the sets). We show that n-step MIR gives facets for the integer knapsack set with arbitrary coefficients that either dominate or are not obtainable by the partition inequalities. Also, using the n-step MIR, we introduce families of facets for the two capacitated flow sets with arbitrary coefficients for the first time. Our results provide a new perspective based on n-step MIR into the polyhedral properties of these three substructures, extend them to the case of arbitrary coefficients, and underscore the power of n-step MIR to easily generate strong valid inequalities.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

@article{Alvarado2012,

title = {Reducing pediatric medication errors: A survey and taxonomy},

author = {Michelle M. Alvarado and Lewis Ntaimo and Amarnath Banerjee and Kiavash Kianfar},

url = {https://doi.org/10.1080/19488300.2012.680799},

year  = {2012},

date = {2012-04-05},

journal = {IIE Transactions on Healthcare Systems Engineering},

volume = {2},

pages = {142-155},

abstract = {According to a 1999 report by the Institute of Medicine an estimated 44,000 to 98,000 people die annually due to medication errors (MEs) in health care. Medication errors can occur at any point in the continuum of care and the literature suggests that MEs are common in our hospitals today, especially in the complex setting of pediatric medicine. This paper is a survey of reported research over the last decade on MEs in pediatrics and their prevention and reduction strategies. It is difficult to know the prevalence of pediatric MEs due to the lack of consistency in error definitions in past studies. Unlike previous surveys on this topic, this paper reviews several studies and provides a taxonomy chart listing the most common pediatric MEs, as well as contributing factors, severity, and possible prevention strategies. The objective is to provide interested researchers in this field with a resource that aggregates and compares related studies on MEs in pediatrics, and provides a comprehensive taxonomy of errors. Challenges and prevention strategies towards reducing pediatric MEs are also discussed.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

@article{Atamtürk2012,

title = {n-step mingling inequalities: new facets for the mixed-integer knapsack set},

author = {Alper Atamtürk and Kiavash Kianfar},

url = {https://doi.org/10.1007/s10107-010-0382-6},

issn = {0025-5610},

year  = {2012},

date = {2012-04-01},

journal = {Mathematical Programming},

volume = {132},

pages = {79-98},

abstract = {The n-step mixed integer rounding (MIR) inequalities of Kianfar and Fathi (Math Program 120(2):313–346, 2009) are valid inequalities for the mixed-integer knapsack set that are derived by using periodic n-step MIR functions and define facets for group problems. The mingling and 2-step mingling inequalities of Atamtürk and Günlük (Math Program 123(2):315–338, 2010) are also derived based on MIR and they incorporate upper bounds on the integer variables. It has been shown that these inequalities are facet-defining for the mixed integer knapsack set under certain conditions and generalize several well-known valid inequalities. In this paper, we introduce new classes of valid inequalities for the mixed-integer knapsack set with bounded integer variables, which we call n-step mingling inequalities (for positive integer n). These inequalities incorporate upper bounds on integer variables into n-step MIR and, therefore, unify the concepts of n-step MIR and mingling in a single class of inequalities. Furthermore, we show that for each n, the n-step mingling inequality defines a facet for the mixed integer knapsack set under certain conditions. For n = 2, we extend the results of Atamtürk and Günlük on facet-defining properties of 2-step mingling inequalities. For n ≥ 3, we present new facets for the mixed integer knapsack set. As a special case we also derive conditions under which the n-step MIR inequalities define facets for the mixed integer knapsack set. In addition, we show that n-step mingling can be used to generate new valid inequalities and facets based on covers and packs defined for mixed integer knapsack sets.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

@article{Farzaneh2012,

title = {Optimal Deployment of Emission Reduction Technologies for Large Fleets},

author = {Mohamadreza Farzaneh and Gokhan Memisoglu and Kiavash Kianfar },

url = {https://doi.org/10.3141/2287-03},

issn = {0361-1981},

year  = {2012},

date = {2012-01-01},

journal = {Transportation Research Record},

volume = {2287},

pages = {18-26},

abstract = {In states that have serious air quality problems, such as Texas and California, public fleet managers are under pressure to reduce emissions of their fleets. This paper presents an improved optimization framework for determining the most cost-effective assignment of emission reduction technologies to the vehicles in a large fleet and applies it in a much larger setting than previously done in the literature (in relation to fleet size, geographical area, and numbers of pollutants and technologies). Although the improved framework is applicable to any large setting, this study uses the fleet of the Texas Department of Transportation (DOT) as one example. An explanation of the three components of the framework (i.e., fleet data preprocessing, emissions rate estimation, and the binary integer programming optimization model) is followed by the presentation of two scenarios in which the framework is applied to the whole Texas DOT fleet. The resulting optimal deployment of nine technologies and five pollutants is reported. The improved framework uses weighting schemes for counties and pollutants that allow the optimization model itself to choose the best budget distribution strategy from an arbitrary number of possibilities acceptable to the decision maker. In contrast, previous frameworks could consider only an extremely small number of budget distribution strategies for counties.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

@article{Fathi2011,

title = {An efficient model for the crosscut optimisation problem in a wood processing mill},

author = {Yahya Fathi and Kiavash Kianfar},

url = {https://doi.org/10.1080/00207543.2010.538446},

year  = {2011},

date = {2011-06-03},

journal = {International Journal of Production Research},

volume = {50},

pages = {485-497},

abstract = {We propose a dynamic programming model for the crosscut optimisation problem. This problem arises in the context of cutting lumber (rip-first) in order to obtain cubic blocks (cut-pieces) with required dimensions and surface characteristics. We propose a novel approach for matching the pattern of defects on all four surfaces of an incoming strip of wood with the surface requirements of the cut-pieces as specified in a given cut-bill, and determine an effective cutting pattern for each incoming strip accordingly. Our proposed dynamic programming model results in fast execution times as shown by the results of a computational experiment. The model is deployed in a software package that has been implemented successfully in several major rough mills.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

@article{Kianfar2011,

title = {Branch-and-Bound Algorithms},

author = {Kiavash Kianfar},

url = {https://doi.org/10.1002/9780470400531.eorms0116},

year  = {2011},

date = {2011-01-14},

journal = {Wiley Encyclopedia of Operations Research and Management Science},

abstract = {“Branch‐and‐bound” is the most common approach to solving integer programming and many combinatorial optimization problems. This article provides an overview of the main concepts in branch‐and‐bound and explains how it works. It also discusses the major design questions that arise in implementing branch‐and‐bound, and briefly reviews the most common answers to these questions by referring to the recent literature providing the reader with ample opportunity for further reading.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

@article{Kianfar2010b,

title = {Generating facets for finite master cyclic group polyhedra using n-step mixed integer rounding functions},

author = {Kiavash Kianfar and Yahya Fathi},

url = {https://doi.org/10.1016/j.ejor.2010.04.021},

year  = {2010},

date = {2010-11-16},

journal = {European Journal of Operational Research},

volume = {207},

pages = {105-109},

abstract = {The n-step mixed integer rounding (MIR) functions generate n-step MIR inequalities for MIP problems and are facets for the infinite group problems. We show that the n-step MIR functions also directly generate facets for the finite master cyclic group polyhedra especially in many cases where the breakpoints of the n-step MIR function are not necessarily at the elements of the group (hence the linear interpolation of the facet coefficients obtained has more than two slopes).},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

@article{Kianfar2010,

title = {An Integer Programming Approach for Analyzing the Measurement Redundancy in Structured Linear Systems},

author = {Kiavash Kianfar and Arash Pourhabib and Yu Ding},

url = {https://doi.org/10.1109/TASE.2010.2089449},

issn = {1545-5955},

year  = {2010},

date = {2010-11-09},

journal = { IEEE Transactions on Automation Science and Engineering },

volume = {8},

pages = {447-450},

abstract = {A linear system whose model matrix is of size n×p is considered structured if some p row vectors in the model matrix are linearly dependent. Computing the degree of redundancy for structured linear systems is proven NP-hard. Previous computation strategy is divide-and-conquer, materialized in a bound-and-decompose algorithm, which, when the required conditions are satisfied, can compute the degree of redundancy on a set of much smaller submatrices instead of directly on the original model matrix. The limitation of this algorithm is that the current decomposition conditions are still restrictive and not always satisfied for many applications. We present a mixed integer programming (MIP) formulation of the redundancy degree problem and solve it using an existing MIP solver. Our numerical studies indicate that our approach outperforms the existing methods for many applications, especially when the decomposition conditions are not satisfied. The main contribution of the paper is that we tackle this challenging problem from a different angle and test a promising new approach. The resulting approach points to a path that can potentially solve the problem in its entirety.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

@article{Sanjeevi2010,

title = {A polyhedral study of triplet formulation for single row facility layout problem},

author = {Sujeevraja Sanjeevi and Kiavash Kianfar},

url = {https://doi.org/10.1016/j.dam.2010.07.005},

year  = {2010},

date = {2010-08-28},

journal = {Discrete Applied Mathematics},

volume = {158},

pages = {1861-1867},

abstract = {The single row facility layout problem (SRFLP) is the problem of arranging n departments with given lengths on a straight line so as to minimize the total weighted distance between all department pairs. We present a polyhedral study of the triplet formulation of the SRFLP introduced by Amaral [A.R.S. Amaral, A new lower bound for the single row facility layout problem, Discrete Applied Mathematics 157 (1) (2009) 183–190]. For any number of departments , we prove that the dimension of the triplet polytope is n(n-1)(n-2)/3 (this is also true for the projections of this polytope presented by Amaral). We then prove that several valid inequalities presented by Amaral for this polytope are facet-defining. These results provide theoretical support for the fact that the linear program solved over these valid inequalities gives the optimal solution for all instances studied by Amaral.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}

@article{Kianfar2009,

title = {Generalized mixed integer rounding inequalities: facets for infinite group polyhedra},

author = {Kiavash Kianfar and Yahya Fathi},

url = {https://doi.org/10.1007/s10107-008-0216-y},

issn = {0025-5610},

year  = {2009},

date = {2009-09-01},

journal = {Mathematical Programming},

volume = {120},

pages = {313-346},

abstract = {We present a generalization of the mixed integer rounding (MIR) approach for generating valid inequalities for (mixed) integer programming (MIP) problems. For any positive integer n, we develop n facets for a certain (n + 1)-dimensional single-constraint polyhedron in a sequential manner. We then show that for any n, the last of these facets (which we call the n-step MIR facet) can be used to generate a family of valid inequalities for the feasible set of a general (mixed) IP constraint, which we refer to as the n-step MIR inequalities. The Gomory Mixed Integer Cut and the 2-step MIR inequality of Dash and günlük  (Math Program 105(1):29–53, 2006) are the first two families corresponding to n = 1,2, respectively. The n-step MIR inequalities are easily produced using periodic functions which we refer to as the n-step MIR functions. None of these functions dominates the other on its whole period. Finally, we prove that the n-step MIR inequalities generate two-slope facets for the infinite group polyhedra, and hence are potentially strong.},

keywords = {},

pubstate = {published},

tppubtype = {article}

}