BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Abraham P. Punnen

Abraham P. Punnen appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.OCDiscrete Mathematicsmath.COArtificial IntelligenceData Structures and AlgorithmsComputational ComplexityComputer Vision

Catalog footprint

What is connected

15works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

15 published item(s)

preprint2022arXiv

An adaptive bi-objective optimization algorithm for the satellite image data downlink scheduling problem considering request split

The satellite image data downlink scheduling problem (SIDSP) is well studied in literature for traditional satellites. With recent developments in satellite technology, SIDSP for modern satellites became more complicated, adding new dimensions of complexities and additional opportunities for the effective use of the satellite. In this paper, we introduce the dynamic two-phase satellite image data downlink scheduling problem (D-SIDSP) which combines two interlinked operations of image data segmentation and image data downlink, in a dynamic way, and thereby offering additional modelling flexibility and renewed capabilities. D-SIDSP is formulated as a bi-objective problem of optimizing the image data transmission rate and the service-balance degree. Harnessing the power of an adaptive large neighborhood search algorithm (ALNS) with a nondominated sorting genetic algorithm II (NSGA-II), an adaptive bi-objective memetic algorithm, ALNS+NSGA-II, is developed to solve D-SIDSP. Results of extensive computational experiments carried out using benchmark instances are also presented. Our experimental results disclose that the algorithm ALNS+NSGA-II is a viable alternative to solve D-SIDSP more efficiently and demonstrates superior outcomes based on various performance metrics. The paper also offers new benchmark instances for D-SIDSP that can be used in future research works on the topic.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Multi-strip observation scheduling problem for ac-tive-imaging agile earth observation satellites

Active-imaging agile earth observation satellite (AI-AEOS) is a new generation agile earth observation satellite (AEOS). With renewed capabilities in observation and active im-aging, AI-AEOS improves upon the observation capabilities of AEOS and provide additional ways to observe ground targets. This however makes the observation scheduling problem for these agile earth observation satellite more complex, especially when considering multi-strip ground targets. In this paper, we investigate the multi-strip observation scheduling problem for an active-image agile earth observation satellite (MOSP). A bi-objective optimization model is presented for MOSP along with an adaptive bi-objective memetic algorithm which integrates the combined power of an adaptive large neighborhood search algorithm (ALNS) and a nondominated sorting genetic algorithm II (NSGA-II). Results of extensive computa-tional experiments are presented which disclose that ALNS and NSGA-II when worked in unison produced superior outcomes. Our model is more versatile than existing models and provide enhanced capabilities in applied problem solving.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Markov Chain methods for the bipartite Boolean quadratic programming problem

We study the Bipartite Boolean Quadratic Programming Problem (BBQP) which is an extension of the well known Boolean Quadratic Programming Problem (BQP). Applications of the BBQP include mining discrete patterns from binary data, approximating matrices by rank-one binary matrices, computing the cut-norm of a matrix, and solving optimisation problems such as maximum weight biclique, bipartite maximum weight cut, maximum weight induced sub-graph of a bipartite graph, etc. For the BBQP, we first present several algorithmic components, specifically, hill climbers and mutations, and then show how to combine them in a high-performance metaheuristic. Instead of hand-tuning a standard metaheuristic to test the efficiency of the hybrid of the components, we chose to use an automated generation of a multi-component metaheuristic to save human time, and also improve objectivity in the analysis and comparisons of components. For this we designed a new metaheuristic schema which we call Conditional Markov Chain Search (CMCS). We show that CMCS is flexible enough to model several standard metaheuristics; this flexibility is controlled by multiple numeric parameters, and so is convenient for automated generation. We study the configurations revealed by our approach and show that the best of them outperforms the previous state-of-the-art BBQP algorithm by several orders of magnitude. In our experiments we use benchmark instances introduced in the preliminary version of this paper and described here, which have already become the de facto standard in the BBQP literature.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On a linearization technique for solving quadratic set covering problem and variations

In this paper we identify some inaccuracies in the paper by R.R. Saxena and S.R. Arora, A Linearization technique for solving the Quadratic Set Covering Problem, Optimization, 39 (1997) 33-42. In particular, we observe that their algorithm need not guarantee optimality, contrary to what is claimed. Experimental analysis with the algorithm has been carried out to evaluate its merit as a heuristic and compared with CPLEX. The results disclose that for some class of problems the algorithm is reasonably effective while for some other class, it's performance is very poor. we also discussion similar inaccuracies in another related paper.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Bilinear Assignment Problem: Complexity and polynomially solvable special cases

In this paper we study the {\it bilinear assignment problem} (BAP) with size parameters $m$ and $n$, $m\leq n$. BAP is a generalization of the well known quadratic assignment problem and the three dimensional assignment problem and hence NP-hard. We show that BAP cannot be approximated within a constant factor unless P=NP even if the associated quadratic cost matrix $Q$ is diagonal. Further, we show that BAP remains NP-hard if $m = O(\sqrt[r]{n})$, for some fixed $r$, but is solvable in polynomial time if $m = O(\sqrt{\log n})$. When the rank of $Q$ is fixed, BAP is observed to admit FPTAS and when this rank is one, it is solvable in polynomial time under some additional restrictions. We then provide a necessary and sufficient condition for BAP to be equivalent to two linear assignment problems. A closed form expression to compute the average of the objective function values of all solutions is presented, whereas the median of the solution values cannot be identified in polynomial time, unless P=NP. We then provide polynomial time heuristic algorithms that find a solution with objective function value no worse than that of $(m-1)!(n-1)!$ solutions. However, computing a solution whose objective function value is no worse than that of $m!n!-\lceil\frac{m}β\rceil !\lceil\frac{n}β\rceil !$ solutions is NP-hard for any fixed rational number $β>1$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Quadratic Minimum Spanning Tree Problem and its Variations

The quadratic minimum spanning tree problem and its variations such as the quadratic bottleneck spanning tree problem, the minimum spanning tree problem with conflict pair constraints, and the bottleneck spanning tree problem with conflict pair constraints are useful in modeling various real life applications. All these problems are known to be NP-hard. In this paper, we investigate these problems to obtain additional insights into the structure of the problems and to identify possible demarcation between easy and hard special cases. New polynomially solvable cases have been identified, as well as NP-hard instances on very simple graphs. As a byproduct, we have a recursive formula for counting the number of spanning trees on a $(k,n)$-accordion and a characterization of matroids in the context of a quadratic objective function.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

A characterization of linearizable instances of the quadratic minimum spanning tree problem

We investigate special cases of the quadratic minimum spanning tree problem (QMSTP) on a graph $G=(V,E)$ that can be solved as a linear minimum spanning tree problem. Characterization of such problems on graphs with special properties are given. This include complete graphs, complete bipartite graphs, cactuses among others. Our characterization can be verified in $O(|E|^2)$ time. In the case of complete graphs and when the cost matrix is given in factored form, we show that our characterization can be verified in $O(|E|)$ time. Related open problems are also indicated.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Average value of solutions of the bipartite quadratic assignment problem and linkages to domination analysis

In this paper we study the complexity and domination analysis in the context of the \emph{bipartite quadratic assignment problem}. Two variants of the problem, denoted by BQAP1 and BQAP2, are investigated. A formula for calculating the average objective function value $\mathcal{A}$ of all solutions is presented whereas computing the median objective function value is shown to be NP-hard. We show that any heuristic algorithm that produces a solution with objective function value at most $\mathcal{A}$ has the domination ratio at least $\frac{1}{mn}$. Analogous results for the standard \emph{quadratic assignment problem} is an open question. We show that computing a solution whose objective function value is no worse than that of $n^mm^n-{\lceil\frac{n}α\rceil}^{\lceil\frac{m}α\rceil}{\lceil\frac{m}α\rceil}^{\lceil\frac{n}α\rceil}$ solutions of BQAP1 or $m^mn^n-{\lceil\frac{m}α\rceil}^{\lceil\frac{m}α\rceil}{\lceil\frac{n}α\rceil}^{\lceil\frac{n}α\rceil}$ solutions of BQAP2, is NP-hard for any fixed natural numbers $a$ and $b$ such that $α=\frac{a}{b}>1$. However, a solution with the domination number $Ω(m^{n-1}n^{m-1}+m^{n+1}n+mn^{m+1})$ for BQAP1 and $Ω(m^{m-1}n^{n-1}+m^2n^{n}+m^mn^2)$ for BQAP2, can be found in $O(m^3n^3)$ time.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Satellite downlink scheduling problem: A case study

The synthetic aperture radar (SAR) technology enables satellites to efficiently acquire high quality images of the Earth surface. This generates significant communication traffic from the satellite to the ground stations, and, thus, image downlinking often becomes the bottleneck in the efficiency of the whole system. In this paper we address the downlink scheduling problem for Canada's Earth observing SAR satellite, RADARSAT-2. Being an applied problem, downlink scheduling is characterised with a number of constraints that make it difficult not only to optimise the schedule but even to produce a feasible solution. We propose a fast schedule generation procedure that abstracts the problem specific constraints and provides a simple interface to optimisation algorithms. By comparing empirically several standard meta-heuristics applied to the problem, we select the most suitable one and show that it is clearly superior to the approach currently in use.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The bipartite unconstrained 0-1 quadratic programming problem: polynomially solvable cases

We consider the bipartite unconstrained 0-1 quadratic programming problem (BQP01) which is a generalization of the well studied unconstrained 0-1 quadratic programming problem (QP01). BQP01 has numerous applications and the problem is known to be MAX SNP hard. We show that if the rank of an associated $m\times n$ cost matrix $Q=(q_{ij})$ is fixed, then BQP01 can be solved in polynomial time. When $Q$ is of rank one, we provide an $O(n\log n)$ algorithm and this complexity reduces to $O(n)$ with additional assumptions. Further, if $q_{ij}=a_i+b_j$ for some $a_i$ and $b_j$, then BQP01 is shown to be solvable in $O(mn\log n)$ time. By restricting $m=O(\log n),$ we obtain yet another polynomially solvable case of BQP01 but the problem remains MAX SNP hard if $m=O(\sqrt[k]{n})$ for a fixed $k$. Finally, if the minimum number of rows and columns to be deleted from $Q$ to make the remaining matrix non-negative is $O(\log n)$ then we show that BQP01 polynomially solvable but it is NP-hard if this number is $O(\sqrt[k]{n})$ for any fixed $k$. Keywords: quadratic programming, 0-1 variables, polynomial algorithms, complexity, pseudo-Boolean programming.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Average value of solutions for the bipartite boolean quadratic programs and rounding algorithms

We consider domination analysis of approximation algorithms for the bipartite boolean quadratic programming problem (BBQP) with m+n variables. A closed form formula is developed to compute the average objective function value A of all solutions in O(mn) time. However, computing the median objective function value of the solutions is shown to be NP-hard. Also, we show that any solution with objective function value no worse than A dominates at least 2^{m+n-2} solutions and this bound is the best possible. Further, we show that such a solution can be identified in O(mn) time and hence the dominance ratio of this algorithm is at least 1/4. We then show that for any fixed rational number a > 1, no polynomial time approximation algorithm exists for BBQP with dominance ratio larger than 1-2^{(m+n)(1-a)/a}, unless P=NP. We then analyze some powerful local search algorithms and show that they can get trapped at a local maximum with objective function value less than A. One of our approximation algorithms has an interesting rounding property which provides a data dependent lower bound on the optimal objective function value. A new integer programming formulation of BBQP is also given and computational results with our rounding algorithms are reported.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Heuristic algorithms for the bipartite unconstrained 0-1 quadratic programming problem

We study the Bipartite Unconstrained 0-1 Quadratic Programming Problem (BQP) which is a relaxation of the Unconstrained 0-1 Quadratic Programming Problem (QP). Applications of the BQP include mining discrete patterns from binary data, approximating matrices by rank-one binary matrices, computing cut-norm of a matrix, and solving optimization problems such as maximum weight biclique, bipartite maximum weight cut, maximum weight induced subgraph of a bipartite graph, etc. We propose several classes of heuristic approaches to solve the BQP and discuss a number of construction algorithms, local search algorithms and their combinations. Results of extensive computational experiments are reported to establish the practical performance of our algorithms. For this purpose, we propose several sets of test instances based on various applications of the BQP. Our algorithms are compared with state-of-the-art heuristics for QP which can also be used to solve BQP with reformulation. We also study theoretical properties of the neighborhoods and algorithms. In particular, we establish complexity of all neighborhood search algorithms and establish tight worst-case performance ratio for the greedy algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Integrating tabu search and VLSN search to develop enhanced algorithms: A case study using bipartite boolean quadratic programs

The bipartite boolean quadratic programming problem (BBQP) is a generalization of the well studied boolean quadratic programming problem. The model has a variety of real life applications; however, empirical studies of the model are not available in the literature, except in a few isolated instances. In this paper, we develop efficient heuristic algorithms based on tabu search, very large scale neighborhood (VLSN) search, and a hybrid algorithm that integrates the two. The computational study establishes that effective integration of simple tabu search with VLSN search results in superior outcomes, and suggests the value of such an integration in other settings. Complexity analysis and implementation details are provided along with conclusions drawn from experimental analysis. In addition, we obtain solutions better than the best previously known for almost all medium and large size benchmark instances.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

The quadratic balanced optimization problem

We introduce the quadratic balanced optimization problem (QBOP) which can be used to model equitable distribution of resources with pairwise interaction. QBOP is strongly NP-hard even if the family of feasible solutions has a very simple structure. Several general purpose exact and heuristic algorithms are presented. Results of extensive computational experiments are reported using randomly generated quadratic knapsack problems as the test bed. These results illustrate the efficacy of our exact and heuristic algorithms. We also show that when the cost matrix is specially structured, QBOP can be solved as a sequence of linear balanced optimization problems. As a consequence, we have several polynomially solvable cases of QBOP.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A reduced integer programming model for the ferry scheduling problem

We present an integer programming model for the ferry scheduling problem, improving existing models in various ways. In particular, our model has reduced size in terms of the number of variables and constraints compared to existing models by a factor of approximately O(n), where n being the number of ports. The model also handles efficiently load/unload time constraints, crew scheduling and passenger transfers. Experiments using real world data produced high quality solutions in 12 hours using CPLEX 12.4 with a performance guarantee of within 15% of optimality, on average. This establishes that using a general purpose integer programming solver is a viable alternative in solving the ferry scheduling problem of moderate size.

0 citations0 reviewsNo code linkedOpen access