Showing 1–32 of 32 results for author: Pardalos, P M

Double interdiction problem on trees on the sum of root-leaf distances by upgrading edges

Authors: Xiao Li, Xiucui Guan, Junhua Jia, Panos M. Pardalos

Abstract: The double interdiction problem on trees (DIT) for the sum of root-leaf distances (SRD) has significant implications in diverse areas such as transportation networks, military strategies, and counter-terrorism efforts. It aims to maximize the SRD by upgrading edge weights subject to two constraints. One gives an upper bound for the cost of upgrades under certain norm and the other specifies a lowe… ▽ More The double interdiction problem on trees (DIT) for the sum of root-leaf distances (SRD) has significant implications in diverse areas such as transportation networks, military strategies, and counter-terrorism efforts. It aims to maximize the SRD by upgrading edge weights subject to two constraints. One gives an upper bound for the cost of upgrades under certain norm and the other specifies a lower bound for the shortest root-leaf distance (StRD). We utilize both weighted $l_\infty$ norm and Hamming distance to measure the upgrade cost and denote the corresponding (DIT) problem by (DIT$_{H\infty}$) and its minimum cost problem by (MCDIT$_{H\infty}$). We establish the $\mathcal{NP}$-hardness of problem (DIT$_{H\infty}$) by building a reduction from the 0-1 knapsack problem. We solve the problem (DIT$_{H\infty}$) by two scenarios based on the number $N$ of upgrade edges. When $N=1$, a greedy algorithm with $O(n)$ complexity is proposed. For the general case, an exact dynamic programming algorithm within a pseudo-polynomial time is proposed, which is established on a structure of left subtrees by maximizing a convex combination of the StRD and SRD. Furthermore, we confirm the $\mathcal{NP}$-hardness of problem (MCDIT$_{H\infty}$) by reducing from the 0-1 knapsack problem. To tackle problem (MCDIT$_{H\infty}$), a binary search algorithm with pseudo-polynomial time complexity is outlined, which iteratively solves problem (DIT$_{H\infty}$). We culminate our study with numerical experiments, showcasing effectiveness of the algorithm. △ Less

Submitted 18 July, 2024; originally announced July 2024.

Comments: 25 pages, 5 figures

Delta-modular ILP Problems of Bounded Co-dimension, Discrepancy, and Convolution

Authors: D. Gribanov, D. Malyshev, P. M. Pardalos

Abstract: For $k, n \geq 0$, and $c \in Z^n$, we consider ILP problems \begin{gather*} \max\bigl\{ c^\top x \colon A x = b,\, x \in Z^n_{\geq 0} \bigr\}\text{ with $A \in Z^{k \times n}$, $rank(A) = k$, $b \in Z^{k}$ and} \max\bigl\{ c^\top x \colon A x \leq b,\, x \in Z^n \bigr\} \text{ with $A \in Z^{(n+k) \times n}$, $rank(A) = n$, $b \in Z^{n+k}$.} \end{gather*} The first problem is called an \emph{… ▽ More For $k, n \geq 0$, and $c \in Z^n$, we consider ILP problems \begin{gather*} \max\bigl\{ c^\top x \colon A x = b,\, x \in Z^n_{\geq 0} \bigr\}\text{ with $A \in Z^{k \times n}$, $rank(A) = k$, $b \in Z^{k}$ and} \max\bigl\{ c^\top x \colon A x \leq b,\, x \in Z^n \bigr\} \text{ with $A \in Z^{(n+k) \times n}$, $rank(A) = n$, $b \in Z^{n+k}$.} \end{gather*} The first problem is called an \emph{ILP problem in the standard form of the codimension $k$}, and the second problem is called an \emph{ILP problem in the canonical form with $n+k$ constraints.} We show that, for any sufficiently large $Δ$, both problems can be solved with $$ 2^{O(k)} \cdot (f_{k,d} \cdot Δ)^2 / 2^{Ω\bigl(\sqrt{\log(f_{k,d} \cdot Δ)}\bigr)} $$ operations, where $ f_{k,d} = \min \Bigl\{ k^{k/2}, \bigl(\log k \cdot \log (d + k)\bigr)^{k/2} \Bigr\} $, $d$ is the dimension of a corresponding polyhedron and $Δ$ is the maximum absolute value of $rank(A) \times rank(A)$ sub-determinants of $A$. As our second main result, we show that the feasibility variants of both problems can be solved with $$ 2^{O(k)} \cdot f_{k,d} \cdot Δ\cdot \log^3(f_{k,d} \cdot Δ) $$ operations. The constant $f_{k,d}$ can be replaced by other constant $g_{k,Δ} = \bigl(\log k \cdot \log (k Δ)\bigr)^{k/2}$ that depends only on $k$ and $Δ$. Additionally, we consider different partial cases with $k=0$ and $k=1$, which have interesting applications. As a result of independent interest, we propose an $n^2/2^{Ω\bigl(\sqrt{\log n}\bigr)}$-time algorithm for the tropical convolution problem on sequences, indexed by elements of a finite Abelian group of the order $n$. Additionally, we give a complete, self-contained error analysis of the generalized Discrete Fourier Transform for Abelian groups with respect to the Word-RAM computational model. △ Less

Submitted 23 July, 2024; v1 submitted 27 May, 2024; originally announced May 2024.

An Overview of Absolute Value Equations: From Theory to Solution Methods and Challenges

Authors: Milan Hladík, Hossein Moosaei, Fakhrodin Hashemi, Saeed Ketabchi, Panos M. Pardalos

Abstract: This paper provides a thorough exploration of the absolute value equations $Ax-|x|=b$, a seemingly straightforward concept that has gained heightened attention in recent years. It is an NP-hard and nondifferentiable problem and equivalent with the standard linear complementarity problem. Offering a comprehensive review of existing literature, the study delves into theorems concerning the existence… ▽ More This paper provides a thorough exploration of the absolute value equations $Ax-|x|=b$, a seemingly straightforward concept that has gained heightened attention in recent years. It is an NP-hard and nondifferentiable problem and equivalent with the standard linear complementarity problem. Offering a comprehensive review of existing literature, the study delves into theorems concerning the existence and nonexistence of solutions to the absolute value equations, along with numerical methods for effectively addressing this complex equation. Going beyond conventional approaches, the paper investigates strategies for obtaining solutions with minimal norms, techniques for correcting infeasible systems, and other pertinent topics. By pinpointing challenging issues and emphasizing open problems, this paper serves as a valuable guide for shaping the future research trajectory in this dynamic and multifaceted field. △ Less

Submitted 9 April, 2024; originally announced April 2024.

A branch-and-price approach for the nurse rostering problem with multiple units

Authors: Wanzhe Hu, Xiaozhou He, Li Luo, Panos M. Pardalos

Abstract: In this paper, we study the nurse rostering problem that considers multiple units and many soft time-related constraints. An efficient branch and price solution approach that relies on a fast algorithm to solve the pricing subproblem of the column generation process is presented. For the nurse rostering problem, its pricing subproblem can be formulated as a shortest path problem with resource cons… ▽ More In this paper, we study the nurse rostering problem that considers multiple units and many soft time-related constraints. An efficient branch and price solution approach that relies on a fast algorithm to solve the pricing subproblem of the column generation process is presented. For the nurse rostering problem, its pricing subproblem can be formulated as a shortest path problem with resource constraints, which has been the backbone of several solutions for several classical problems like vehicle routing problems. However, approaches that perform well on these problems cannot be used since most constraints in the nurse rostering problem are soft. Based on ideas borrowed from global constraints in constraint programming to model rostering problems, an efficient dynamic programming algorithm with novel label definitions and dominating rules specific to soft time-related constraints is proposed. In addition, several acceleration strategies are employed to improve the branch and price algorithm. Computational results on instances of different sizes indicate that the proposed algorithm is a promising solution for the nurse rostering problem with multiple units. △ Less

Submitted 9 November, 2023; originally announced November 2023.

Restricted inverse optimal value problem on linear programming under weighted $l_1$ norm

Authors: Junhua Jia, Xiucui Guan, Xinqiang Qian, Panos M. Pardalos

Abstract: We study the restricted inverse optimal value problem on linear programming under weighted $l_1$ norm (RIOVLP $_1$). Given a linear programming problem $LP_c: \min \{cx|Ax=b,x\geq 0\}$ with a feasible solution $x^0$ and a value $K$, we aim to adjust the vector $c$ to $\bar{c}$ such that $x^0$ becomes an optimal solution of the problem LP$_{\bar c}$ whose objective value $\bar{c}x^0$ equals $K$. Th… ▽ More We study the restricted inverse optimal value problem on linear programming under weighted $l_1$ norm (RIOVLP $_1$). Given a linear programming problem $LP_c: \min \{cx|Ax=b,x\geq 0\}$ with a feasible solution $x^0$ and a value $K$, we aim to adjust the vector $c$ to $\bar{c}$ such that $x^0$ becomes an optimal solution of the problem LP$_{\bar c}$ whose objective value $\bar{c}x^0$ equals $K$. The objective is to minimize the distance $\|\bar c - c\|_1=\sum_{j=1}^nd_j|\bar c_j-c_j|$ under weighted $l_1$ norm.Firstly, we formulate the problem (RIOVLP$_1$) as a linear programming problem by dual theories. Secondly, we construct a sub-problem $(D^z)$, which has the same form as $LP_c$, of the dual (RIOVLP$_1$) problem corresponding to a given value $z$. Thirdly, when the coefficient matrix $A$ is unimodular, we design a binary search algorithm to calculate the critical value $z^*$ corresponding to an optimal solution of the problem (RIOVLP$_1$). Finally, we solve the (RIOV) problems on Hitchcock and shortest path problem, respectively, in $O(T_{MCF}\log\max\{d_{max},x^0_{max},n\})$ time, where we solve a sub-problem $(D^z)$ by minimum cost flow in $T_{MCF}$ time in each iteration. The values $d_{max},x^0_{max}$ are the maximum values of $d$ and $x^0$, respectively. △ Less

Submitted 21 August, 2023; originally announced August 2023.

The sum of root-leaf distance interdiction problem with cardinality constraint by upgrading edges on trees

Authors: Xiao Li, Xiucui Guan, Qiao Zhang, Xinyi Yin, Panos M. Pardalos

Abstract: A network for the transportation of supplies can be described as a rooted tree with a weight of a degree of congestion for each edge. We take the sum of root-leaf distance (SRD) on a rooted tree as the whole degree of congestion of the tree. Hence, we consider the SRD interdiction problem on trees with cardinality constraint by upgrading edges (denoted by (SDIPTC) in brief). It aims to maximize th… ▽ More A network for the transportation of supplies can be described as a rooted tree with a weight of a degree of congestion for each edge. We take the sum of root-leaf distance (SRD) on a rooted tree as the whole degree of congestion of the tree. Hence, we consider the SRD interdiction problem on trees with cardinality constraint by upgrading edges (denoted by (SDIPTC) in brief). It aims to maximize the SRD by upgrading the weights of $N$ critical edges such that the total upgrade cost under some measurement is upper-bounded by a given value. The relevant minimum cost problem (MCSDIPTC) aims to minimize the total upgrade cost on the premise that the SRD is lower-bounded by a given value. We develop two different norms including weighted $l_\infty$ norm and weighted bottleneck Hamming distance to measure the upgrade cost. We propose two binary search algorithms within O($n\log n$) time for the problems (SDIPTC) under the two norms, respectively. For problems (MCSDIPTC),we propose two binary search algorithms within O($N n^2$) and O($n \log n$) under weighted $l_\infty$ norm and weighted bottleneck Hamming distance, respectively. These problems are solved through their subproblems (SDIPT) and (MCSDIPT), in which we ignore the cardinality constraint on the number of upgraded edges. Finally, we design numerical experiments to show the effectiveness of these algorithms. △ Less

Submitted 30 July, 2023; originally announced July 2023.

A Brief Review of Explainable Artificial Intelligence in Healthcare

Authors: Zahra Sadeghi, Roohallah Alizadehsani, Mehmet Akif Cifci, Samina Kausar, Rizwan Rehman, Priyakshi Mahanta, Pranjal Kumar Bora, Ammar Almasri, Rami S. Alkhawaldeh, Sadiq Hussain, Bilal Alatas, Afshin Shoeibi, Hossein Moosaei, Milan Hladik, Saeid Nahavandi, Panos M. Pardalos

Abstract: XAI refers to the techniques and methods for building AI applications which assist end users to interpret output and predictions of AI models. Black box AI applications in high-stakes decision-making situations, such as medical domain have increased the demand for transparency and explainability since wrong predictions may have severe consequences. Model explainability and interpretability are vit… ▽ More XAI refers to the techniques and methods for building AI applications which assist end users to interpret output and predictions of AI models. Black box AI applications in high-stakes decision-making situations, such as medical domain have increased the demand for transparency and explainability since wrong predictions may have severe consequences. Model explainability and interpretability are vital successful deployment of AI models in healthcare practices. AI applications' underlying reasoning needs to be transparent to clinicians in order to gain their trust. This paper presents a systematic review of XAI aspects and challenges in the healthcare domain. The primary goals of this study are to review various XAI methods, their challenges, and related machine learning models in healthcare. The methods are discussed under six categories: Features-oriented methods, global methods, concept models, surrogate models, local pixel-based methods, and human-centric methods. Most importantly, the paper explores XAI role in healthcare problems to clarify its necessity in safety-critical applications. The paper intends to establish a comprehensive understanding of XAI-related applications in the healthcare field by reviewing the related experimental results. To facilitate future research for filling research gaps, the importance of XAI models from different viewpoints and their limitations are investigated. △ Less

Submitted 4 April, 2023; originally announced April 2023.

A New Approximation Algorithm for Minimum-Weight $(1,m)$--Connected Dominating Set

Authors: Jiao Zhou, Yingli Ran, Panos M. Pardalos, Zhao Zhang, Shaojie Tang, Ding-Zhu Du

Abstract: Consider a graph with nonnegative node weight. A vertex subset is called a CDS (connected dominating set) if every other node has at least one neighbor in the subset and the subset induces a connected subgraph. Furthermore, if every other node has at least $m$ neighbors in the subset, then the node subset is called a $(1,m)$CDS. The minimum-weight $(1,m)$CDS problem aims at finding a $(1,m)$CDS wi… ▽ More Consider a graph with nonnegative node weight. A vertex subset is called a CDS (connected dominating set) if every other node has at least one neighbor in the subset and the subset induces a connected subgraph. Furthermore, if every other node has at least $m$ neighbors in the subset, then the node subset is called a $(1,m)$CDS. The minimum-weight $(1,m)$CDS problem aims at finding a $(1,m)$CDS with minimum total node weight. In this paper, we present a new polynomial-time approximation algorithm for this problem with approximation ratio $2H(δ_{\max}+m-1)$, where $δ_{\max}$ is the maximum degree of the given graph and $H(\cdot)$ is the Harmonic function, i.e., $H(k)=\sum_{i=1}^k \frac{1}{i}$. △ Less

Submitted 21 February, 2023; v1 submitted 22 January, 2023; originally announced January 2023.

MSC Class: 68W25 ACM Class: F.2.2

Survey of Methods for Solving Systems of Nonlinear Equations, Part II: Optimization Based Approaches

Authors: Ilias S. Kotsireas, Panos M. Pardalos, Alexander Semenov, William T. Trevena, Michael N. Vrahatis

Abstract: This paper presents a comprehensive survey of methods which can be utilized to search for solutions to systems of nonlinear equations (SNEs). Our objectives with this survey are to synthesize pertinent literature in this field by presenting a thorough description and analysis of the known methods capable of finding one or many solutions to SNEs, and to assist interested readers seeking to identify… ▽ More This paper presents a comprehensive survey of methods which can be utilized to search for solutions to systems of nonlinear equations (SNEs). Our objectives with this survey are to synthesize pertinent literature in this field by presenting a thorough description and analysis of the known methods capable of finding one or many solutions to SNEs, and to assist interested readers seeking to identify solution techniques which are well suited for solving the various classes of SNEs which one may encounter in real world applications. To accomplish these objectives, we present a multi-part survey. In part one, we focused on root-finding approaches which can be used to search for solutions to a SNE without transforming it into an optimization problem. In part two, we introduce the various transformations which have been utilized to transform a SNE into an optimization problem, and we discuss optimization algorithms which can then be used to search for solutions. We emphasize the important characteristics of each method, and we discuss promising directions for future research. In part three, we will present a robust quantitative comparative analysis of methods capable of searching for solutions to SNEs. △ Less

Submitted 17 August, 2022; originally announced August 2022.

Survey of Methods for Solving Systems of Nonlinear Equations, Part I: Root-finding Approaches

Authors: Ilias S. Kotsireas, Panos M. Pardalos, Alexander Semenov, William T. Trevena, Michael N. Vrahatis

Abstract: This paper presents a comprehensive survey of methods which can be utilized to search for solutions to systems of nonlinear equations (SNEs). Our objectives with this survey are to synthesize pertinent literature in this field by presenting a thorough description and analysis of the known methods capable of finding one or many solutions to SNEs, and to assist interested readers seeking to identify… ▽ More This paper presents a comprehensive survey of methods which can be utilized to search for solutions to systems of nonlinear equations (SNEs). Our objectives with this survey are to synthesize pertinent literature in this field by presenting a thorough description and analysis of the known methods capable of finding one or many solutions to SNEs, and to assist interested readers seeking to identify solution techniques which are well suited for solving the various classes of SNEs which one may encounter in real world applications. To accomplish these objectives, we present a multi-part survey. In part one, we focus on root-finding approaches which can be used to search for solutions to a SNE without transforming it into an optimization problem. In part two, we will introduce the various transformations which have been utilized to transform a SNE into an optimization problem, and we discuss optimization algorithms which can then be used to search for solutions. In part three, we will present a robust quantitative comparative analysis of methods capable of searching for solutions to SNEs. △ Less

Submitted 17 August, 2022; originally announced August 2022.

Homography augumented momentum constrastive learning for SAR image retrieval

Authors: Seonho Park, Maciej Rysz, Kathleen M. Dipple, Panos M. Pardalos

Abstract: Deep learning-based image retrieval has been emphasized in computer vision. Representation embedding extracted by deep neural networks (DNNs) not only aims at containing semantic information of the image, but also can manage large-scale image retrieval tasks. In this work, we propose a deep learning-based image retrieval approach using homography transformation augmented contrastive learning to pe… ▽ More Deep learning-based image retrieval has been emphasized in computer vision. Representation embedding extracted by deep neural networks (DNNs) not only aims at containing semantic information of the image, but also can manage large-scale image retrieval tasks. In this work, we propose a deep learning-based image retrieval approach using homography transformation augmented contrastive learning to perform large-scale synthetic aperture radar (SAR) image search tasks. Moreover, we propose a training method for the DNNs induced by contrastive learning that does not require any labeling procedure. This may enable tractability of large-scale datasets with relative ease. Finally, we verify the performance of the proposed method by conducting experiments on the polarimetric SAR image datasets. △ Less

Submitted 21 September, 2021; originally announced September 2021.

Network diffusion capacity unveiled by dynamical paths

Authors: T. A. Schieber, L. C. Carpi, P. M. Pardalos, C. Masoller, A. Díaz-Guilera, M. G. Ravetti

Abstract: Improving the understanding of diffusive processes in networks with complex topologies is one of the main challenges of today's complexity science. Each network possesses an intrinsic diffusive potential that depends on its structural connectivity. However, the diffusion of a process depends not only on this topological potential but also on the dynamical process itself. Quantifying this potential… ▽ More Improving the understanding of diffusive processes in networks with complex topologies is one of the main challenges of today's complexity science. Each network possesses an intrinsic diffusive potential that depends on its structural connectivity. However, the diffusion of a process depends not only on this topological potential but also on the dynamical process itself. Quantifying this potential will allow the design of more efficient systems in which it is necessary either to weaken or to enhance diffusion. Here we introduce a measure, the {\em diffusion capacity}, that quantifies, through the concept of dynamical paths, the potential of an element of the system, and also, of the system itself, to propagate information. Among other examples, we study a heat diffusion model and SIR model to demonstrate the value of the proposed measure. We found, in the last case, that diffusion capacity can be used as a predictor of the evolution of the spreading process. In general, we show that the diffusion capacity provides an efficient tool to evaluate the performance of systems, and also, to identify and quantify structural modifications that could improve diffusion mechanisms. △ Less

Submitted 21 April, 2021; originally announced April 2021.

Deep Data Density Estimation through Donsker-Varadhan Representation

Authors: Seonho Park, Panos M. Pardalos

Abstract: Estimating the data density is one of the challenging problems in deep learning. In this paper, we present a simple yet effective method for estimating the data density using a deep neural network and the Donsker-Varadhan variational lower bound on the KL divergence. We show that the optimal critic function associated with the Donsker-Varadhan representation on the KL divergence between the data a… ▽ More Estimating the data density is one of the challenging problems in deep learning. In this paper, we present a simple yet effective method for estimating the data density using a deep neural network and the Donsker-Varadhan variational lower bound on the KL divergence. We show that the optimal critic function associated with the Donsker-Varadhan representation on the KL divergence between the data and the uniform distribution can estimate the data density. We also present the deep neural network-based modeling and its stochastic learning. The experimental results and possible applications of the proposed method demonstrate that it is competitive with the previous methods and has a lot of possibilities in applied to various applications. △ Less

Submitted 13 April, 2021; originally announced April 2021.

MSC Class: 68T09; 60F10

NC-MOPSO: Network centrality guided multi-objective particle swarm optimization for transport optimization on networks

Authors: Jiexin Wu, Cunlai Pu, Shuxin Ding, Guo Cao, Panos M. Pardalos

Abstract: Transport processes are universal in real-world complex networks, such as communication and transportation networks. As the increase of the traffic in these complex networks, problems like traffic congestion and transport delay are becoming more and more serious, which call for a systematic optimization of these networks. In this paper, we formulate a multi-objective optimization problem (MOP) to… ▽ More Transport processes are universal in real-world complex networks, such as communication and transportation networks. As the increase of the traffic in these complex networks, problems like traffic congestion and transport delay are becoming more and more serious, which call for a systematic optimization of these networks. In this paper, we formulate a multi-objective optimization problem (MOP) to deal with the enhancement of network capacity and efficiency simultaneously, by appropriately adjusting the weights of edges in networks. To solve this problem, we provide a multi-objective evolutionary algorithm (MOEA) based on particle swarm optimization (PSO), namely network centrality guided multi-objective PSO (NC-MOPSO). Specifically, in the framework of PSO, we propose a hybrid population initialization mechanism and a local search strategy by employing the network centrality theory to enhance the quality of initial solutions and strengthen the exploration of the search space, respectively. Simulation experiments performed on network models and real networks show that our algorithm has better performance than four state-of-the-art alternatives on several most-used metrics. △ Less

Submitted 27 July, 2021; v1 submitted 8 September, 2020; originally announced September 2020.

Comments: This work has been submitted to the IEEE for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible

Interpreting Rate-Distortion of Variational Autoencoder and Using Model Uncertainty for Anomaly Detection

Authors: Seonho Park, George Adosoglou, Panos M. Pardalos

Abstract: Building a scalable machine learning system for unsupervised anomaly detection via representation learning is highly desirable. One of the prevalent methods is using a reconstruction error from variational autoencoder (VAE) via maximizing the evidence lower bound. We revisit VAE from the perspective of information theory to provide some theoretical foundations on using the reconstruction error, an… ▽ More Building a scalable machine learning system for unsupervised anomaly detection via representation learning is highly desirable. One of the prevalent methods is using a reconstruction error from variational autoencoder (VAE) via maximizing the evidence lower bound. We revisit VAE from the perspective of information theory to provide some theoretical foundations on using the reconstruction error, and finally arrive at a simpler and more effective model for anomaly detection. In addition, to enhance the effectiveness of detecting anomalies, we incorporate a practical model uncertainty measure into the metric. We show empirically the competitive performance of our approach on benchmark datasets. △ Less

Submitted 7 May, 2020; v1 submitted 4 May, 2020; originally announced May 2020.

Comments: Corrected typos

On $Δ$-Modular Integer Linear Problems In The Canonical Form And Equivalent Problems

Authors: D. V. Gribanov, I. A. Shumilov, D. S. Malyshev, P. M. Pardalos

Abstract: Many papers in the field of integer linear programming (ILP, for short) are devoted to problems of the type $\max\{c^\top x \colon A x = b,\, x \in \mathbb{Z}^n_{\geq 0}\}$, where all the entries of $A,b,c$ are integer, parameterized by the number of rows of $A$ and $\|A\|_{\max}$. This class of problems is known under the name of ILP problems in the standard form, adding the word "bounded" if… ▽ More Many papers in the field of integer linear programming (ILP, for short) are devoted to problems of the type $\max\{c^\top x \colon A x = b,\, x \in \mathbb{Z}^n_{\geq 0}\}$, where all the entries of $A,b,c$ are integer, parameterized by the number of rows of $A$ and $\|A\|_{\max}$. This class of problems is known under the name of ILP problems in the standard form, adding the word "bounded" if $x \leq u$, for some integer vector $u$. Recently, many new sparsity, proximity, and complexity results were obtained for bounded and unbounded ILP problems in the standard form. In this paper, we consider ILP problems in the canonical form $$\max\{c^\top x \colon b_l \leq A x \leq b_r,\, x \in \mathbb{Z}^n\},$$ where $b_l$ and $b_r$ are integer vectors. We assume that the integer matrix $A$ has the rank $n$, $(n + m)$ rows, $n$ columns, and parameterize the problem by $m$ and $Δ(A)$, where $Δ(A)$ is the maximum of $n \times n$ sub-determinants of $A$, taken in the absolute value. We show that any ILP problem in the standard form can be polynomially reduced to some ILP problem in the canonical form, preserving $m$ and $Δ(A)$, but the reverse reduction is not always possible. More precisely, we define the class of generalized ILP problems in the standard form, which includes an additional group constraint, and prove the equivalence to ILP problems in the canonical form. We generalize known sparsity, proximity, and complexity bounds for ILP problems in the canonical form. Additionally, sometimes, we strengthen previously known results for ILP problems in the canonical form, and, sometimes, we give shorter proofs. Finally, we consider the special cases of $m \in \{0,1\}$. By this way, we give specialised sparsity, proximity, and complexity bounds for the problems on simplices, Knapsack problems and Subset-Sum problems. △ Less

Submitted 9 February, 2022; v1 submitted 3 February, 2020; originally announced February 2020.

Comments: J Glob Optim (2022)

Combining Stochastic Adaptive Cubic Regularization with Negative Curvature for Nonconvex Optimization

Authors: Seonho Park, Seung Hyun Jung, Panos M. Pardalos

Abstract: We focus on minimizing nonconvex finite-sum functions that typically arise in machine learning problems. In an attempt to solve this problem, the adaptive cubic regularized Newton method has shown its strong global convergence guarantees and ability to escape from strict saddle points. This method uses a trust region-like scheme to determine if an iteration is successful or not, and updates only w… ▽ More We focus on minimizing nonconvex finite-sum functions that typically arise in machine learning problems. In an attempt to solve this problem, the adaptive cubic regularized Newton method has shown its strong global convergence guarantees and ability to escape from strict saddle points. This method uses a trust region-like scheme to determine if an iteration is successful or not, and updates only when it is successful. In this paper, we suggest an algorithm combining negative curvature with the adaptive cubic regularized Newton method to update even at unsuccessful iterations. We call this new method Stochastic Adaptive cubic regularization with Negative Curvature (SANC). Unlike the previous method, in order to attain stochastic gradient and Hessian estimators, the SANC algorithm uses independent sets of data points of consistent size over all iterations. It makes the SANC algorithm more practical to apply for solving large-scale machine learning problems. To the best of our knowledge, this is the first approach that combines the negative curvature method with the adaptive cubic regularized Newton method. Finally, we provide experimental results including neural networks problems supporting the efficiency of our method. △ Less

Submitted 26 June, 2019; originally announced June 2019.

A Statistical Density-Based Analysis of Graph Clustering Algorithm Performance

Authors: Pierre Miasnikof, Alexander Y. Shestopaloff, Anthony J. Bonner, Yuri Lawryshyn, Panos M. Pardalos

Abstract: Measuring graph clustering quality remains an open problem. To address it, we introduce quality measures based on comparisons of intra- and inter-cluster densities, an accompanying statistical test of the significance of their differences and a step-by-step routine for clustering quality assessment. Our null hypothesis does not rely on any generative model for the graph, unlike modularity which us… ▽ More Measuring graph clustering quality remains an open problem. To address it, we introduce quality measures based on comparisons of intra- and inter-cluster densities, an accompanying statistical test of the significance of their differences and a step-by-step routine for clustering quality assessment. Our null hypothesis does not rely on any generative model for the graph, unlike modularity which uses the configuration model as a null model. Our measures are shown to meet the axioms of a good clustering quality function, unlike the very commonly used modularity measure. They also have an intuitive graph-theoretic interpretation, a formal statistical interpretation and can be easily tested for significance. Our work is centered on the idea that well clustered graphs will display a significantly larger intra-cluster density than inter-cluster density. We develop tests to validate the existence of such a cluster structure. We empirically explore the behavior of our measures under a number of stress test scenarios and compare their behavior to the commonly used modularity and conductance measures. Empirical stress test results confirm that our measures compare very favorably to the established ones. In particular, they are shown to be more responsive to graph structure and less sensitive to sample size and breakdowns during numerical implementation and less sensitive to uncertainty in connectivity. These features are especially important in the context of larger data sets or when the data may contain errors in the connectivity patterns. △ Less

Submitted 18 March, 2020; v1 submitted 5 June, 2019; originally announced June 2019.

A Smooth Double Proximal Primal-Dual Algorithm for a Class of Distributed Nonsmooth Optimization Problem

Authors: Yue Wei, Hao Fang, Xianlin Zeng, Jie Chen, Panos M. Pardalos

Abstract: This technical note studies a class of distributed nonsmooth convex consensus optimization problem. The cost function is a summation of local cost functions which are convex but nonsmooth. Each of the local cost functions consists of a twice differentiable convex function and two lower semi-continuous convex functions. We call this problem as single-smooth plus double-nonsmooth (SSDN) problem. Und… ▽ More This technical note studies a class of distributed nonsmooth convex consensus optimization problem. The cost function is a summation of local cost functions which are convex but nonsmooth. Each of the local cost functions consists of a twice differentiable convex function and two lower semi-continuous convex functions. We call this problem as single-smooth plus double-nonsmooth (SSDN) problem. Under mild conditions, we propose a distributed double proximal primal-dual optimization algorithm. The double proximal operator is designed to deal with the difficulty caused by the unproximable property of the summation of those two nonsmooth functions. Besides, it can also guarantee that the proposed algorithm is locally Lipschitz continuous. An auxiliary variable in the double proximal operator is introduced to estimate the subgradient of the second nonsmooth function. Theoretically, we conduct the convergence analysis by employing Lyapunov stability theory. It shows that the proposed algorithm can make the states achieve consensus at the optimal point. In the end, nontrivial simulations are presented and the results demonstrate the effectiveness of the proposed algorithm. △ Less

Submitted 16 August, 2018; originally announced August 2018.

On the complexity of quasiconvex integer minimization problem

Authors: A. Yu. Chirkov, D. V. Gribanov, D. S. Malyshev, P. M. Pardalos, S. I. Veselov, N. Yu. Zolotykh

Abstract: In this paper, we consider the class of quasiconvex functions and its proper subclass of conic functions. The integer minimization problem of these functions is considered in the paper, assuming that an optimized function is defined by the comparison oracle. We will show that there is no a polynomial algorithm on $\log R$ to optimize quasiconvex functions in the ball of integer radius $R$ using on… ▽ More In this paper, we consider the class of quasiconvex functions and its proper subclass of conic functions. The integer minimization problem of these functions is considered in the paper, assuming that an optimized function is defined by the comparison oracle. We will show that there is no a polynomial algorithm on $\log R$ to optimize quasiconvex functions in the ball of integer radius $R$ using only the comparison oracle. On the other hand, if an optimized function is conic, then we show that there is a polynomial on $\log R$ algorithm. We also present an exponential on the dimension lower bound for the oracle complexity of the conic function integer optimization problem. Additionally, we give examples of known problems that can be polynomially reduced to the minimization problem of functions in our classes. △ Less

Submitted 7 October, 2019; v1 submitted 8 July, 2018; originally announced July 2018.

Comments: Some new proofs have been added. Some fixes are done

Journal ref: J Glob Optim 73, 761-788 (2019)

Assessing diversity in multiplex networks

Authors: L. C. Carpi, T. A. Schieber, P. M. Pardalos, G. Marfany, C. Masoller, A. Díaz-Guilera, M. G. Ravetti

Abstract: Diversity, understood as the variety of different elements or configurations that an extensive system has, is a crucial property that allows maintaining the system's functionality in a changing environment, where failures, random events or malicious attacks are often unavoidable. Despite the relevance of preserving diversity in the context of ecology, biology, transport, finances, etc., the elemen… ▽ More Diversity, understood as the variety of different elements or configurations that an extensive system has, is a crucial property that allows maintaining the system's functionality in a changing environment, where failures, random events or malicious attacks are often unavoidable. Despite the relevance of preserving diversity in the context of ecology, biology, transport, finances, etc., the elements or configurations that more contribute to the diversity are often unknown, and thus, they can not be protected against failures or environmental crises. This is due to the fact that there is no generic framework that allows identifying which elements or configurations have crucial roles in preserving the diversity of the system. Existing methods treat the level of heterogeneity of a system as a measure of its diversity, being unsuitable when systems are composed of a large number of elements with different attributes and types of interactions. Besides, with limited resources, one needs to find the best preservation policy, i.e., one needs to solve an optimization problem. Here we aim to bridge this gap by developing a metric between labeled graphs to compute the diversity of the system, which allows identifying the most relevant components, based on their contribution to a global diversity value. The proposed framework is suitable for large multiplex structures, which are constituted by a set of elements represented as nodes, which have different types of interactions, represented as layers. The proposed method allows us to find, in a genetic network (HIV-1), the elements with the highest diversity values, while in a European airline network, we systematically identify the companies that maximize (and those that less compromise) the variety of options for routes connecting different airports. △ Less

Submitted 8 December, 2018; v1 submitted 31 May, 2018; originally announced May 2018.

Comments: 14 pages, 7 figures

Extended Vertical Lists for Temporal Pattern Mining from Multivariate Time Series

Authors: Anton Kocheturov, Petar Momcilovic, Azra Bihorac, Panos M. Pardalos

Abstract: Temporal Pattern Mining (TPM) is the problem of mining predictive complex temporal patterns from multivariate time series in a supervised setting. We develop a new method called the Fast Temporal Pattern Mining with Extended Vertical Lists. This method utilizes an extension of the Apriori property which requires a more complex pattern to appear within records only at places where all of its subpat… ▽ More Temporal Pattern Mining (TPM) is the problem of mining predictive complex temporal patterns from multivariate time series in a supervised setting. We develop a new method called the Fast Temporal Pattern Mining with Extended Vertical Lists. This method utilizes an extension of the Apriori property which requires a more complex pattern to appear within records only at places where all of its subpatterns are detected as well. The approach is based on a novel data structure called the Extended Vertical List that tracks positions of the first state of the pattern inside records. Extensive computational results indicate that the new method performs significantly faster than the previous version of the algorithm for TMP. However, the speed-up comes at the expense of memory usage. △ Less

Submitted 26 April, 2018; originally announced April 2018.

Comments: 16 pages, 7 figures, 2 tables

Machine Learning Methods for Data Association in Multi-Object Tracking

Authors: Patrick Emami, Panos M. Pardalos, Lily Elefteriadou, Sanjay Ranka

Abstract: Data association is a key step within the multi-object tracking pipeline that is notoriously challenging due to its combinatorial nature. A popular and general way to formulate data association is as the NP-hard multidimensional assignment problem (MDAP). Over the last few years, data-driven approaches to assignment have become increasingly prevalent as these techniques have started to mature. We… ▽ More Data association is a key step within the multi-object tracking pipeline that is notoriously challenging due to its combinatorial nature. A popular and general way to formulate data association is as the NP-hard multidimensional assignment problem (MDAP). Over the last few years, data-driven approaches to assignment have become increasingly prevalent as these techniques have started to mature. We focus this survey solely on learning algorithms for the assignment step of multi-object tracking, and we attempt to unify various methods by highlighting their connections to linear assignment as well as to the MDAP. First, we review probabilistic and end-to-end optimization approaches to data association, followed by methods that learn association affinities from data. We then compare the performance of the methods presented in this survey, and conclude by discussing future research directions. △ Less

Submitted 25 August, 2020; v1 submitted 19 February, 2018; originally announced February 2018.

Comments: Accepted for publication in ACM Computing Surveys

Journal ref: Volume 53, Issue 4 (August 2020)

FPT-algorithms for some problems related to integer programming

Authors: D. V. Gribanov, D. S. Malyshev, P. M. Pardalos, S. I. Veselov

Abstract: In this paper, we present FPT-algorithms for special cases of the shortest lattice vector, integer linear programming, and simplex width computation problems, when matrices included in the problems' formulations are near square. The parameter is the maximum absolute value of rank minors of the corresponding matrices. Additionally, we present FPT-algorithms with respect to the same parameter for th… ▽ More In this paper, we present FPT-algorithms for special cases of the shortest lattice vector, integer linear programming, and simplex width computation problems, when matrices included in the problems' formulations are near square. The parameter is the maximum absolute value of rank minors of the corresponding matrices. Additionally, we present FPT-algorithms with respect to the same parameter for the problems, when the matrices have no singular rank sub-matrices. △ Less

Submitted 7 March, 2019; v1 submitted 18 December, 2017; originally announced December 2017.

Comments: arXiv admin note: text overlap with arXiv:1710.00321 From author: some minor corrections has been done

Journal ref: J Comb Optim 35, 1128-1146 (2018)

Information transmission on hybrid networks

Authors: Rongbin Chen, Wei Cui, Cunlai Pu, Jie Li, Bo Ji, Konstantinos Gakis, Panos M. Pardalos

Abstract: Many real-world communication networks often have hybrid nature with both fixed nodes and moving modes, such as the mobile phone networks mainly composed of fixed base stations and mobile phones. In this paper, we discuss the information transmission process on the hybrid networks with both fixed and mobile nodes. The fixed nodes (base stations) are connected as a spatial lattice on the plane form… ▽ More Many real-world communication networks often have hybrid nature with both fixed nodes and moving modes, such as the mobile phone networks mainly composed of fixed base stations and mobile phones. In this paper, we discuss the information transmission process on the hybrid networks with both fixed and mobile nodes. The fixed nodes (base stations) are connected as a spatial lattice on the plane forming the information-carrying backbone, while the mobile nodes (users), which are the sources and destinations of information packets, connect to their current nearest fixed nodes respectively to deliver and receive information packets. We observe the phase transition of traffic load in the hybrid network when the packet generation rate goes from below and then above a critical value, which measures the network capacity of packets delivery. We obtain the optimal speed of moving nodes leading to the maximum network capacity. We further improve the network capacity by rewiring the fixed nodes and by considering the current load of fixed nodes during packets transmission. Our purpose is to optimize the network capacity of hybrid networks from the perspective of network science, and provide some insights for the construction of future communication infrastructures. △ Less

Submitted 17 April, 2017; originally announced April 2017.

Comments: 17 pages, 7 figures

Heuristic for Maximizing Grouping Efficiency in the Cell Formation Problem

Authors: Ilya Bychkov, Mikhail Batsyn, Panos M. Pardalos

Abstract: In our paper we consider the Cell Formation Problem in Group Technology with grouping efficiency as an objective function. We present a heuristic approach for obtaining high-quality solutions of the CFP. The suggested heuristic applies an improvement procedure to obtain solutions with high grouping efficiency. This procedure is repeated many times for randomly generated cell configurations. Our co… ▽ More In our paper we consider the Cell Formation Problem in Group Technology with grouping efficiency as an objective function. We present a heuristic approach for obtaining high-quality solutions of the CFP. The suggested heuristic applies an improvement procedure to obtain solutions with high grouping efficiency. This procedure is repeated many times for randomly generated cell configurations. Our computational experiments are performed for popular benchmark instances taken from the literature with sizes from 10x20 to 50x150. Better solutions unknown before are found for 23 instances of the 24 considered. △ Less

Submitted 10 January, 2017; originally announced February 2017.

Comments: 15 pages, 7 tables

Optimal statistical decision for Gaussian graphical model selection

Authors: Valery A. Kalyagin, Alexander P. Koldanov, Petr A. Koldanov, Panos M. Pardalos

Abstract: Gaussian graphical model is a graphical representation of the dependence structure for a Gaussian random vector. It is recognized as a powerful tool in different applied fields such as bioinformatics, error-control codes, speech language, information retrieval and others. Gaussian graphical model selection is a statistical problem to identify the Gaussian graphical model from a sample of a given s… ▽ More Gaussian graphical model is a graphical representation of the dependence structure for a Gaussian random vector. It is recognized as a powerful tool in different applied fields such as bioinformatics, error-control codes, speech language, information retrieval and others. Gaussian graphical model selection is a statistical problem to identify the Gaussian graphical model from a sample of a given size. Different approaches for Gaussian graphical model selection are suggested in the literature. One of them is based on considering the family of individual conditional independence tests. The application of this approach leads to the construction of a variety of multiple testing statistical procedures for Gaussian graphical model selection. An important characteristic of these procedures is its error rate for a given sample size. In existing literature great attention is paid to the control of error rates for incorrect edge inclusion (Type I error). However, in graphical model selection it is also important to take into account error rates for incorrect edge exclusion (Type II error). To deal with this issue we consider the graphical model selection problem in the framework of the multiple decision theory. The quality of statistical procedures is measured by a risk function with additive losses. Additive losses allow both types of errors to be taken into account. We construct the tests of a Neyman structure for individual hypotheses and combine them to obtain a multiple decision statistical procedure. We show that the obtained procedure is optimal in the sense that it minimizes the linear combination of expected numbers of Type I and Type II errors in the class of unbiased multiple decision procedures. △ Less

Submitted 9 January, 2017; originally announced January 2017.

Comments: 14 pages

MSC Class: 62-09; 62H15; 62C05

Optimal decision for the market graph identification problem in sign similarity network

Authors: V. A. Kalyagin, P. A. Koldanov, P. M. Pardalos

Abstract: Investigation of the market graph attracts a growing attention in market network analysis. One of the important problem connected with market graph is to identify it from observations. Traditional way for the market graph identification is to use a simple procedure based on statistical estimations of Pearson correlations between pairs of stocks. Recently a new class of statistical procedures for t… ▽ More Investigation of the market graph attracts a growing attention in market network analysis. One of the important problem connected with market graph is to identify it from observations. Traditional way for the market graph identification is to use a simple procedure based on statistical estimations of Pearson correlations between pairs of stocks. Recently a new class of statistical procedures for the market graph identification was introduced and optimality of these procedures in Pearson correlation Gaussian network was proved. However the obtained procedures have a high reliability only for Gaussian multivariate distributions of stocks attributes. One of the way to correct this drawback is to consider a different networks generated by different measures of pairwise similarity of stocks. A new and promising model in this context is the sign similarity network. In the present paper the market graph identification problem in sign similarity network is considered. A new class of statistical procedures for the market graph identification is introduced and optimality of these procedures is proved. Numerical experiments detect essential difference in quality of optimal procedures in sign similarity and Pearson correlation networks. In particular it is observed that the quality of optimal identification procedure in sign similarity network is not sensitive to the assumptions on distribution of stocks attributes. △ Less

Submitted 20 December, 2015; originally announced December 2015.

Comments: 16 pages, 6 figures

MSC Class: 62C05

Information Theory Perspective on Network Robustness

Authors: Tiago A. Schieber, Laura Carpi, Alejandro C. Frery, Osvaldo A Rosso, Panos M. Pardalos, Martin G. Ravetti

Abstract: A crucial challenge in network theory is the study of the robustness of a network after facing a sequence of failures. In this work, we propose a dynamical definition of network's robustness based on Information Theory, that considers measurements of the structural changes caused by failures of the network's components. Failures are defined here, as a temporal process defined in a sequence. The ro… ▽ More A crucial challenge in network theory is the study of the robustness of a network after facing a sequence of failures. In this work, we propose a dynamical definition of network's robustness based on Information Theory, that considers measurements of the structural changes caused by failures of the network's components. Failures are defined here, as a temporal process defined in a sequence. The robustness of the network is then evaluated by measuring dissimilarities between topologies after each time step of the sequence, providing a dynamical information about the topological damage. We thoroughly analyze the efficiency of the method in capturing small perturbations by considering both, the degree and distance distributions. We found the network's distance distribution more consistent in capturing network structural deviations, as better reflects the consequences of the failures. Theoretical examples and real networks are used to study the performance of this methodology. △ Less

Submitted 30 October, 2015; v1 submitted 30 October, 2014; originally announced October 2014.

Comments: 5 pages, 2 figures, submitted

Measures of uncertainty in market network analysis

Authors: V. A. Kalyagin, A. P. Koldanov, P. A. Koldanov, P. M. Pardalos, V. A. Zamaraev

Abstract: Statistical uncertainty of different filtration techniques for market network analysis is studied. Two measures of statistical uncertainty are discussed. One is based on conditional risk for multiple decision statistical procedures and another one is based on average fraction of errors. It is shown that for some important cases the second measure is a particular case of the first one. Statistical… ▽ More Statistical uncertainty of different filtration techniques for market network analysis is studied. Two measures of statistical uncertainty are discussed. One is based on conditional risk for multiple decision statistical procedures and another one is based on average fraction of errors. It is shown that for some important cases the second measure is a particular case of the first one. Statistical uncertainty for some popular market network structures is analyzed. Results of numerical evaluation of statistical uncertainty for minimum spanning tree, market graph, maximum cliques and maximum independent sets are given. The most stable structures are derived. △ Less

Submitted 10 November, 2013; originally announced November 2013.

MSC Class: 68T37

Concepts of Stability in Discrete Optimization Involving Generalized Addition Operations

Authors: Vyacheslav V. Chistyakov, Panos M. Pardalos

Abstract: The paper addresses the tolerance approach to the sensitivity analysis of optimal solutions to the nonlinear optimization problem of the form $$\mbox{$\bigoplus\limits_{y\in S}C(y)\to\min$\quad over\quad $S\in\mathcal{S}$,}$$ where $\mathcal{S}$ is a collection of nonempty subsets of a finite set $X$ such that the union of $\mathcal{S}$ is $X$ and the intersection of $\mathcal{S}$ is empty, $C… ▽ More The paper addresses the tolerance approach to the sensitivity analysis of optimal solutions to the nonlinear optimization problem of the form $$\mbox{$\bigoplus\limits_{y\in S}C(y)\to\min$\quad over\quad $S\in\mathcal{S}$,}$$ where $\mathcal{S}$ is a collection of nonempty subsets of a finite set $X$ such that the union of $\mathcal{S}$ is $X$ and the intersection of $\mathcal{S}$ is empty, $C$ is a cost (or weight) function from $X$ into $\mathbb{R}^+=[0,\infty)$ or $(0,\infty)$, and $\oplus$ is a continuous, associative, commutative, nondecreasing and unbounded binary operation of generalized addition on $\mathbb{R}^+$, called an A-operation. We evaluate and present sharp estimates for upper and lower bounds of costs of elements from $X$, for which an optimal solution to the above problem remains stable. These bounds present new results in the sensitivity analysis as well as extend most known results in a unified way. We define an invariant of the optimization problem---the tolerance function, which is independent of optimal solutions, and establish its basic properties, among which we mention a characterization of the set of all optimal solutions, the uniqueness of optimal solutions and extremal values of the tolerance function on an optimal solution. △ Less

Submitted 17 September, 2013; originally announced September 2013.

Comments: 34 pages, 2 tables, LaTeX

MSC Class: 90C31 (Primary); 90C27; 90C26 (Secondary)

Journal ref: Journal of Optimization Theory and Applications 167, no. 2 (2015), 585-616

Simulating Protein Conformations through Global Optimization

Authors: A. Mucherino, O. Seref, P. M. Pardalos

Abstract: Many researches have been working on the protein folding problem from more than half century. Protein folding is indeed one of the major unsolved problems in science. In this work, we discuss a model for the simulation of protein conformations. This simple model is based on the idea of imposing few geometric requirements on chains of atoms representing the backbone of a protein conformation. The… ▽ More Many researches have been working on the protein folding problem from more than half century. Protein folding is indeed one of the major unsolved problems in science. In this work, we discuss a model for the simulation of protein conformations. This simple model is based on the idea of imposing few geometric requirements on chains of atoms representing the backbone of a protein conformation. The model leads to the formulation of a global optimization problem, whose solutions correspond to conformations satisfying the desired requirements. The global optimization problem is solved by the recently proposed Monkey Search algorithm. The simplicity of the optimization problem and the effectiveness of the used meta-heuristic search allowed the simulation of a large set of high-quality conformations. We show that, even though only few geometric requirements are imposed, some of the simulated conformation results to be similar (in terms of RMSD) to conformations real proteins actually have in nature. △ Less

Submitted 19 November, 2008; originally announced November 2008.

Comments: 11 pages, 2 figures (with 4 images), 1 table, 28 references; original research

MSC Class: 46N60; 47N60