<?xml version="1.0" encoding="utf-8"?> <feed xmlns="http://www.w3.org/2005/Atom"> <title type="text">Recent zbMATH articles in MSC 90</title> <id>https://zbmath.org/atom/cc/90</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/" /> <link href="https://zbmath.org/atom/cc/90" rel="self" /> <author> <name>Unknown author</name> </author> <generator>Werkzeug</generator> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Statistics and learning theory in the era of artificial intelligence. Abstracts from the workshop held June 23--28, 2024</title> <id>https://zbmath.org/1553.00022</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.00022" /> <content type="text">Summary: The workshop highlighted recent theoretical advances on inference in high-dimensional statistical models based on the interplay of techniques from mathematical statistics, machine learning, theoretical computer science and related areas. The workshop brought together about 50 researchers in order to present new results, exchange ideas and explore open problems.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Preface: 18th Cologne-Twente workshop on graphs and combinatorial optimization (CTW 2020)</title> <id>https://zbmath.org/1553.00038</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.00038" /> <content type="text">From the text: We are pleased to present this special issue of Discrete Applied Mathematics dedicated to the 18th Cologne-Twente Workshop (CTW) on Graphs and Combinatorial Optimization. The CTW is the international version of a series of workshops organized by Ulrich Faigle at the University of Twente in the Netherlands. The CTW2020 was supposed to take place in Ischia (Italy) but, due to the COVID-19 pandemic, it was held online. As in many CTW editions we also managed a post-proceedings special issue of Discrete Applied Mathematics. For this issue we received 48 papers. After a thorough refereeing process, 22 submissions were accepted for publication.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Global optimisation with constructive reals</title> <id>https://zbmath.org/1553.03192</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.03192" /> <author> <name>&quot;Ghica, Dan R.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:ghica.dan-r</uri> </author> <author> <name>&quot;Ambridge, Todd Waugh&quot;</name> <uri>https://zbmath.org/authors/?q=ai:ambridge.todd-waugh</uri> </author> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Partial packing coloring and quasi-packing coloring of the triangular grid</title> <id>https://zbmath.org/1553.05060</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.05060" /> <author> <name>&quot;Grochowski, Hubert&quot;</name> <uri>https://zbmath.org/authors/?q=ai:grochowski.hubert</uri> </author> <author> <name>&quot;Junosza-Szaniawski, Konstanty&quot;</name> <uri>https://zbmath.org/authors/?q=ai:junosza-szaniawski.konstanty</uri> </author> <content type="text">Summary: The concept of packing coloring in graph theory is motivated by the challenge of frequency assignment in radio networks. This approach entails assigning positive integers to vertices, with the requirement that for any given label (color) \(i\), the distance between any two vertices sharing this label must exceed \(i\). Recently, after over 20 years of intensive research, the minimal number of colors needed for packing coloring of an infinite square grid has been established to be 15. Moreover, it is known that a hexagonal grid requires a minimum of 7 colors for packing coloring, and a triangular grid is not colorable with any finite number of colors in a packing way. Therefore, two questions come to mind: What fraction of a triangular grid can be colored in a packing model, and how much do we need to weaken the condition of packing coloring to enable coloring a triangular grid with a finite number of colors? With the partial help of the Mixed Integer Linear Programming (MILP) solver, we have proven that it is possible to color at least 72.8\% but no more than 82.2\% of a triangular grid in a packing way. Additionally, we have investigated the relaxation of packing coloring, called quasi-packing coloring, which is a special case of \(S\)-packing coloring. We have established that the \(S\)-packing chromatic number for the triangular grid, where \(S = (1, 1, 2, 3, \dots)\), is between 11 and 33. Furthermore, we have proven that the aforementioned sequence \(S\) is the best possible in some sense. We have also considered the partial packing and quasi-packing coloring of an infinite hypercube and present several open problems for other classes of graphs.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Creating a network-state homomorphism through optimization</title> <id>https://zbmath.org/1553.05127</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.05127" /> <author> <name>&quot;Shang, Yilun&quot;</name> <uri>https://zbmath.org/authors/?q=ai:shang.yilun</uri> </author> <content type="text">Summary: In graph theory, a mapping between two graphs that generally preserves the structure is called a graph homomorphism, which has been a fundamental notion and extensively studied in combinatorial and algebraic areas. Real-valued states are often assigned to the nodes of graphs (also called networks) in theory and applications underpinning the emerging science of networks. In this paper, we present a simple way to create homomorphisms between a network and its state space. The distance-induced structure in the state space is of practical relevance. We characterize the optimal homomorphism with minimum cost in terms of a constrained optimization problem, and demonstrate the calculation with concrete examples.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Fixed-points for quantitative equational logics</title> <id>https://zbmath.org/1553.08014</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.08014" /> <author> <name>&quot;Mardare, Radu&quot;</name> <uri>https://zbmath.org/authors/?q=ai:mardare.radu</uri> </author> <author> <name>&quot;Panangaden, Prakash&quot;</name> <uri>https://zbmath.org/authors/?q=ai:panangaden.prakash</uri> </author> <author> <name>&quot;Plotkin, Gordon&quot;</name> <uri>https://zbmath.org/authors/?q=ai:plotkin.gordon-d</uri> </author> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Generating extreme copositive matrices near matrices obtained from COP-irreducible graphs</title> <id>https://zbmath.org/1553.15028</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.15028" /> <author> <name>&quot;Manainen, Maxim&quot;</name> <uri>https://zbmath.org/authors/?q=ai:manainen.maxim</uri> </author> <author> <name>&quot;Seliugin, Mikhail&quot;</name> <uri>https://zbmath.org/authors/?q=ai:seliugin.mikhail</uri> </author> <author> <name>&quot;Tarasov, Roman&quot;</name> <uri>https://zbmath.org/authors/?q=ai:tarasov.roman</uri> </author> <author> <name>&quot;Hildebrand, Roland&quot;</name> <uri>https://zbmath.org/authors/?q=ai:hildebrand.roland</uri> </author> <content type="text">As a main goal of the paper under review is to present an algorithmic procedure for obtaining new families of extremal copositive matrices. We recall that a real symmetric \(n\times n\) matrix \(A\) is called copositive if \(\langle Ax,x\rangle\geq 0\) for all \(n\)-tuples of non-negative coordinates. These matrices are completely different from positive semidefinite matrices, and are harder to generate. An important application of copositive matrices can be seen in optimization. However, dealing with these matrices is not as easy as expected. A copositive matrix is called an extreme point (or extreme element) for the copositive cone (consisting of all copositive matrices of a certain size) is a copositive matrix that cannot lie on the line segment joining any two different copositive matrices. Extremal copositive matrices have their own applications. In fact, optimization problems revolve about extremal points generally. This is where this paper excels in, where a systematic approach is presented to construct extremal copositive matrices. The obtained results are of significant importance in this field of research, and much further applications of them is expected to be seen in future work by interested researchers. Reviewer: Mohammad Sababheh (Amman)</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Random generation of linearly constrained fuzzy measures and domain coverage performance evaluation</title> <id>https://zbmath.org/1553.28005</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.28005" /> <author> <name>&quot;Wu, Jian-Zhang&quot;</name> <uri>https://zbmath.org/authors/?q=ai:wu.jianzhang</uri> </author> <author> <name>&quot;Beliakov, Gleb&quot;</name> <uri>https://zbmath.org/authors/?q=ai:beliakov.gleb</uri> </author> <author> <name>&quot;James, Simon&quot;</name> <uri>https://zbmath.org/authors/?q=ai:james.simon</uri> </author> <author> <name>&quot;Gagolewski, Marek&quot;</name> <uri>https://zbmath.org/authors/?q=ai:gagolewski.marek</uri> </author> <content type="text">Summary: The random generation of fuzzy measures under complex linear constraints holds significance in various fields, including optimization solutions, machine learning, decision making, and property investigation. However, most existing random generation methods primarily focus on addressing the monotonicity and normalization conditions inherent in the construction of fuzzy measures, rather than the linear constraints that are crucial for representing special families of fuzzy measures and additional preference information. In this paper, we present two categories of methods to address the generation of linearly constrained fuzzy measures using linear programming models. These methods enable a comprehensive exploration and coverage of the entire feasible convex domain. The first category involves randomly selecting a subset and assigning measure values within the allowable range under given linear constraints. The second category utilizes convex combinations of constrained extreme fuzzy measures and vertex fuzzy measures. Then we employ some indices of fuzzy measures, objective functions, and distances to domain boundaries to evaluate the coverage performance of these methods across the entire feasible domain. We further provide enhancement techniques to improve the coverage ratios. Finally, we discuss and demonstrate potential applications of these generation methods in practical scenarios.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Optimal scenario for road evacuation in an urban environment</title> <id>https://zbmath.org/1553.35172</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.35172" /> <author> <name>&quot;Bestard, Mickael&quot;</name> <uri>https://zbmath.org/authors/?q=ai:bestard.mickael</uri> </author> <author> <name>&quot;Franck, Emmanuel&quot;</name> <uri>https://zbmath.org/authors/?q=ai:franck.emmanuel</uri> </author> <author> <name>&quot;Navoret, Laurent&quot;</name> <uri>https://zbmath.org/authors/?q=ai:navoret.laurent</uri> </author> <author> <name>&quot;Privat, Yannick&quot;</name> <uri>https://zbmath.org/authors/?q=ai:privat.yannick</uri> </author> <content type="text">The authors consider a road network as a directed graph of \(N_{r}\in \mathbb{ N}^{\ast }\) roads, denoted as real intervals \([a_{i},b_{i}]\), and the time evolution of the density \(\rho _{i}\) on the \(i\)-th road according to the system: \(\partial _{t}\rho _{i}(t,x)+\partial _{t}f_{i}(\rho _{i}(t,x))=0\), \( (t,x)\in (0,T)\times \lbrack a_{i},b_{i}]\), with the initial and boundary conditions: \(\rho _{i}(0,x)=\rho _{i}^{0}(x)\), \(x\in \lbrack a_{i},b_{i}]\), \( f_{i}(\rho _{i}(t,a_{i}))=\gamma L_{i}(t)\), \(f_{i}(\rho _{i}(t,b_{i}))=\gamma R_{i}(t)\), \(t\in (0,T)\), where the flux \(f_{i}(\rho )\) is given by \(f_{i}(\rho )=\rho v_{i}^{\max}(1-\frac{\rho }{\rho _{i}^{\max}})\), \(v_{i}^{\max}\) and \(\rho_{i}^{\max}\) respectively denoting the maximal velocity and density allowed on the \(i\)-th road. The initial density \(\rho _{i}^{0}(x)\) and \(\gamma L_{i}\), \(\gamma R_{i}\) are functions allowing prescribing the flux at the left and right boundaries of the interval \([a_{i},b_{i}]\). At a junction \(J\) between \(J_{in}\) in-going and \(J_{\mathrm{out}}\) outgoing roads, a statistical traffic distribution matrix is introduced: \( A_{J}=(\alpha _{ji})_{(j,i)\in J_{\mathrm{out}}\times J_{in}}\), where \(\alpha _{ji}\) is the proportion of vehicles going to the \(j\)-th outgoing road among those coming from the \(i\)-th incoming road that satisfies \(0&lt;\alpha _{ji}&lt;1\), \( \sum_{j\in J_{\mathrm{out}}}\alpha _{ji}=1\). It allows to describe conditions imposed on the flux: \((\gamma L_{j})_{j\in J_{\mathrm{out}}}=A_{J}(\gamma R_{i})_{i\in J_{in}}\). The authors write the solution as: \(\gamma (t)=\phi ^{LP}(\rho (t))\), and they give the explicit expression of \(\phi ^{LP}\) for four types of junctions. They also introduce a problem with a vector of controls at the junctions and they write the flux as \(\gamma =\phi ^{LP}(\rho ,u)\), assuming that \(\phi ^{LP}\) is Lipschitz, and \(C^{1}\) with respect to its second variable \(u\). To define the sensitivity of the different data of the problem with respect to the control, they discretize the model with a first-order finite volume scheme. They introduce the optimal control problem: \( \inf_{u\in \mathcal{U}_{ad}}\mathcal{J}_{\theta }(u)\), where the admissible set \(\mathcal{U}_{ad}\) of controls is defined by \(\mathcal{U}_{ad}=L^{\infty }([0,T],[0,1]^{N_{r}})\), and \(\mathcal{J}_{\theta }\) is the regularized cost functional defined as: \(\mathcal{J}_{\theta }(u)=C_{T}(u)+\frac{\theta _{S}}{ 2}S(u)+\theta _{B}B(u)\), with \(C_{T}(u)=\sum_{i\in \chi _{\mathrm{path}}}\sum_{j=1}^{N_{c}}\rho _{i,j}(T;u)\), \(S(u)=\int_{0}^{T}( \sum_{i=1}^{N_{r}}u_{i}(t)-N_{\max})_{+}^{2}dt\), and \(B(u)= \sum_{i=1}^{N_{r}}TV(u_{i})\). Here \(\rho (T;u)\) is the solution to the semi-discrete control problem, \(N_{\max}\) the maximal number of active controls, and \(TV(u)=sup\{\int_{0}^{T}u(t)\phi ^{\prime }(t)dt\), \(\phi \in C_{c}^{1}([0,T])\), \(\left\Vert \phi \right\Vert _{L^{\infty }(0,T)}\leq 1\}\) . Assuming hypotheses on the data and \(\theta _{B}&gt;0\), the authors prove the existence of a solution to this optimal control problem, introducing a minimizing sequence and proving that the sequence of associated densities is uniformly bounded in \(W^{1,\infty }(0,T)\). They determine the optimality conditions, first defining an admissible perturbation of \(u\) in \(\mathcal{U} _{ad}\). They define a perturbed optimal control problem as: \(\inf_{u\in \mathcal{U}_{ad}}\mathcal{J}_{\theta ,\nu }(u)\), where \(\mathcal{J}_{\theta \nu }(u)=C_{T}(u)+\frac{\theta _{S}}{2}S(u)+\theta _{B}B_{\nu }(u)\), \(\nu &gt;0\) standing for a regularization parameter and \(B_{\nu }(u)\) being the sum of differentiable approximations in \(L^{2}(0,T)\) \(TV_{\nu }(u_{i})\) of \( TV(u_{i})\). They write the first-order optimality conditions for this approximated problem in a very concise and workable way. The rest of the paper is devoted to the presentation of a numerical algorithm, based on a finite volume scheme for the primal problem and an Euler scheme for the adjoint problem. For the optimization problem, they use a projected gradient descent method or a fixed point method, or even hybrid methods between the two preceding ones. The authors present the numerical simulations in the cases of simple junctions, of a traffic circle, and of a three routes network. They analyze the impact of the parameters on the results. Reviewer: Alain Brillard (Riedisheim)</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Second order dynamics featuring Tikhonov regularization and time scaling</title> <id>https://zbmath.org/1553.37109</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.37109" /> <author> <name>&quot;Csetnek, Ern枚 Robert&quot;</name> <uri>https://zbmath.org/authors/?q=ai:csetnek.erno-robert</uri> </author> <author> <name>&quot;Karapetyants, Mikhail A.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:karapetyants.mikhail-a</uri> </author> <content type="text">Summary: In a Hilbert setting we aim to study a second order in time differential equation, combining viscous and Hessian-driven damping, containing a time scaling parameter function and a Tikhonov regularization term. The dynamical system is related to the problem of minimization of a nonsmooth convex function. In the formulation of the problem as well as in our analysis we use the Moreau envelope of the objective function and its gradient and heavily rely on their properties. We show that there is a setting where the newly introduced system preserves and even improves the well-known fast convergence properties of the function and Moreau envelope along the trajectories and also of the gradient of Moreau envelope due to the presence of time scaling. Moreover, in a different setting we prove strong convergence of the trajectories to the element of minimal norm from the set of all minimizers of the objective. The manuscript concludes with various numerical results.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Optimization-aided construction of multivariate Chebyshev polynomials</title> <id>https://zbmath.org/1553.41003</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.41003" /> <author> <name>&quot;Dressler, M.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:dressler.mareike</uri> </author> <author> <name>&quot;Foucart, S.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:foucart.simon</uri> </author> <author> <name>&quot;Joldes, M.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:joldes.mioara</uri> </author> <author> <name>&quot;de Klerk, E.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:de-klerk.etienne</uri> </author> <author> <name>&quot;Lasserre, J. B.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:lasserre.jean-bernard</uri> </author> <author> <name>&quot;Xu, Y.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:xu.yuan</uri> </author> <content type="text">This paper is on the construction of multivariate Chebyshev polynomials through a semi-programming procedure. Using the equivalent characterizations of Chebyshev polynomials in dimension one, the paper first generalizes the definition of Chebyshev polynomials to the multivariate setting using \[ \min_{p\in\mathcal{P}_n^d} \|p\|_\Omega, \mbox{ subject to \(p\) being monic}, \] where \(\|p\|_\Omega:=\max_{x\in\Omega} |p(x)|\) and \(\mathcal{P}_{n}^d\) is the space of \(d\)-variate polynomials of degree up to \(n\). With specific definition of monic polynomials, the above problem becomes \[ \min_{p\in\mathcal{P}_{n-1}^d} \|m_k-p\|_\Omega, \] where \(m_k = x_1^{k_1}\cdots x_d^{k_d}\) and \(|k| = k_1+\cdots+k_d=n\). Moreover, the paper mainly considers four types of domains for \(\Omega\): the simplex \(S\), the cross-polytope \(C\) (\(\ell_1\)-ball), the Euclidean ball (\(\ell_2\)-ball), and the hypercube \(H\) (\(\ell_\infty\) ball). The paper then discusses the connection of multivariate Chebyshev polynomials with the solutions to the best approximation problem \(E_{\mathcal V}(f,\Omega) = \min_{v\in\mathcal V} \|f-v\|_\Omega = \|f-v^*\|_\Omega\), which can be expressed as its duality: \(E_{\mathcal V}(f,\Omega)=\max_{\lambda \in C(\Omega)^*} \lambda (f)\) subject to \(\lambda|_\mathcal{V} = 0\) and \(\|\lambda\|_{C(\Omega)^*} = 1\). The characterization of the best approximant \(v^*\) to \(f\in C(\Omega)\) is then given in terms of an extremal signature \(\sigma\) for \(\mathcal{V}\). To reduce the number of subproblems involved in solving the minimization problem, the paper discusses two reduction techniques. One is to discard zero indices \(k_i\), and the other is to utilize the group invariance property of the problem. Some known results of multivariate Chebyshev polynomials are then given for hypercube \(\Omega=H\), \(\Omega = B\), and \(\Omega = S\). More generally, the domain \(\Omega\) could be any compact basic semi-algebraic set determined by polynomials \(g_1,\ldots, g_H\) such that \(\Omega=\{x\in\mathbb{R}^d: g_1(x)\ge0,\ldots, g_H(x)\ge0\}\). The paper next discusses the main computational procedure to solve for the multivariate polynomials through semi-definite programming. First, the primal minimization problem can be reformulated as \[ \min_{c\in\mathbb{R}, p\in \mathcal{P}_{n-1}^d}c \quad \mbox{ subject to } \begin{cases}c+m_k-p\in \mathcal{P}_+^d(\Omega)\\ c-m_k+p\in \mathcal{P}_+^d(\Omega)\end{cases}, \] where \(\mathcal{P}_+^d(\Omega)\) is the cone of \(d\)-variate polynomials that are nonnegative on \(\Omega\). Its dual problem is then rewritten as \[ \max_{\mu\in \mathcal{M}(\Omega)} \int_\Omega m_k d\mu \quad \mbox{ subject to } \int_\Omega pd \mu =0 \quad \forall p\in \mathcal{P}_{n-1}^d \mbox{ and } \int_\Omega d|\mu|=1, \] where \(\mathcal{M}(\Omega)\) is the space of finite signed Borel measures on \(\Omega\). With \(\mathcal{M}_+(\Omega)\) denoting the cone of finite nonnegative Borel measures on \(\Omega\), the dual problem is equivalent to \[ \max_{\mu^\pm\in \mathcal{M}_+(\Omega)} \int_\Omega m_k d(\mu^+-\mu^-) \quad \mbox{ subject to } \int_\Omega pd (\mu^+-\mu^-) =0 \quad \forall p\in \mathcal{P}_{n-1}^d \mbox{ and } \int_\Omega d(\mu^++\mu^-)=1. \] Then, using the duality relation \(\mathcal M_+(\Omega)^* = \mathcal{P}_+^d\) and the connection between the dual cone of \(\mathcal{Q}(g_1,\ldots, g_H):=\{p: p=\sigma_0+\sigma_1 g_1+\cdots+\sigma_H g_H\}\) and the positive semidefinite matrices, the dual problem can be linked to a sequence \(\{\mathrm{ub}_t'\): \(t\in\mathbb{N}_0\}\) of dual semidefinite programs: \begin{align*} &amp;\mathrm{ub}_t':=\sup_{y^\pm\in\mathbb{R}^{\{0,\ldots, 2t\}^d}} \sum_{|\ell|\le N} \mathrm{coeff}_{m_\ell}(m_k)(y_\ell^+-y_\ell^-) \\ \mbox{ subject to }\ &amp;y_\ell^+-y_\ell^- =0 \quad \forall |\ell|\le n-1, y_0^+ +y_0^-=1, \\ \mbox { and }\ &amp;\mathrm{Hank}_t(y^\pm)\succeq 0, \mathrm{Hank}_{t-n_1'}(G_1y^\pm)\succeq 0,\ldots, \mathrm{Hank}_{t-n_H'}(G_H y^\pm) \succeq0, \end{align*} where \(n_h':=\lceil \mathrm{deg}(g_h)/2\rceil\) for \(h=1,\ldots, H\), \(y_\ell^\pm:=\int_\Omega m_\ell d\mu^\pm\) are the moments with respect to \(\mu^\pm\), \(y^\pm = (y_\ell^\pm)_{\ell\in\mathbb{N}_0^d}\), and \(\mathrm{Hank}(y)\) is the Hankel matrix determined by the sequence \(y=(y_\ell)_{\ell\in\mathbb{N}_0^d}\) having entries \(y_{i+j}, i,j\in \mathbb{N}_0^d\), and \(G_h(y)_\ell:=\sum_{|\ell'|\le \mathrm{deg}(g_h)}\mathrm{coeff}_{m_{\ell'}}(g_h)y_{\ell+\ell'}\). More importantly, one has \(\lim_{t\rightarrow\infty} \mathrm{ub}_t' = E_{\mathcal{P}_{n-1}^d}(f,\Omega)\). With the computational procedure, the paper demonstrates results of multivariate Chebyshev polynomials for \(d=3\) and \(n\) up to 6 in the cases of \(\Omega= C, B, S\). Especially, explicit Chebyshev polynomials are found and proved for the case \(m_{2,2,1}\) for \(\Omega=B\) and the case \(m_{2,1,1}\) for \(\Omega=S\). Reviewer: Xiaosheng Zhuang (Hong Kong)</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">A linear programming approach to Fuglede's conjecture in \(\mathbb{Z}_p^3\)</title> <id>https://zbmath.org/1553.43003</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.43003" /> <author> <name>&quot;Malikiosis, Romanos Diogenes&quot;</name> <uri>https://zbmath.org/authors/?q=ai:malikiosis.romanos-diogenes</uri> </author> <content type="text">Summary: We present an approach to Fuglede's conjecture in \(\mathbb{Z}_p^3\) using linear programming bounds, obtaining the following partial result: if \(A\subseteq \mathbb{Z}_p^3\) with \(p^2-p\sqrt{p}+\sqrt{p}&lt;|A|&lt;p^2\), then \(A\) is not spectral.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">A geometric approach to apriori estimates for optimal transport maps</title> <id>https://zbmath.org/1553.49014</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.49014" /> <author> <name>&quot;Brendle, Simon&quot;</name> <uri>https://zbmath.org/authors/?q=ai:brendle.simon.1</uri> </author> <author> <name>&quot;L茅ger, Flavien&quot;</name> <uri>https://zbmath.org/authors/?q=ai:leger.flavien</uri> </author> <author> <name>&quot;McCann, Robert J.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:mccann.robert-j</uri> </author> <author> <name>&quot;Rankin, Cale&quot;</name> <uri>https://zbmath.org/authors/?q=ai:rankin.cale</uri> </author> <content type="text">Summary: A key inequality which underpins the regularity theory of optimal transport for costs satisfying the Ma-Trudinger-Wang condition is the Pogorelov second-derivative bound. This translates to an apriori interior \(C^1\) estimate for smooth optimal maps. Here we give a new derivation of this estimate which relies in part on Kim, McCann and Warren's observation that the graph of an optimal map becomes a volume maximizing spacelike submanifold when the product of the source and target domains is endowed with a suitable pseudo-Riemannian geometry that combines both the marginal densities and the cost.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Optimal control, well-posedness and sensitivity analysis for a class of generalized evolutionary systems</title> <id>https://zbmath.org/1553.49017</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.49017" /> <author> <name>&quot;Li, Xiuwen&quot;</name> <uri>https://zbmath.org/authors/?q=ai:li.xiuwen</uri> </author> <author> <name>&quot;Luo, Zhi&quot;</name> <uri>https://zbmath.org/authors/?q=ai:luo.zhi</uri> </author> <author> <name>&quot;Liu, Zhenhai&quot;</name> <uri>https://zbmath.org/authors/?q=ai:liu.zhenhai</uri> </author> <content type="text">The authors study a system governed by the following fractional differential variational-hemivariational inequality in a reflexive Banach space \(E\): \[ \left\{ \begin{array}{l} ^CD_t^\alpha x(t) \in Ax(t) + F(t,x(t),u(t))\quad \mbox{a.e.}\,\,t \in I := [0,b], \\ u(t) \in SOL(K; g(t,x(t),\cdot0, J(x(t),\cdot), J(x(t),\cdot),\phi,h)\quad \mbox{a.e.}\,\,t \in I,\\ x(0) = x_0. \end{array} \right. \] Here \(^CD_t^\alpha,\) \(0 &lt; \alpha \leq 1\) denotes the Caputo fractional derivative, \(A\) is an infinitesimal generator of a compact and uniformly bounded \(C_0\)-semigroup in \(E,\) \(F \colon I \times E \times U \multimap E,\) where \(U\) is a reflexive Banach space, is a multimap with convex closed values. For a nonempty convex closed subset \(K \subset U\), the notation \(SOL(K;g(t,x(t),\cdot),J(x(t),\cdot),\phi,h)\) stands for the solution set of the mixed variational-hemivariational inequality of the form \[ \langle g(t,x(t),u(t)),v - u(t)\rangle_U + J^0(x(t),\gamma u(t);\gamma(v - u(t))) + \phi(v,u(t)) \geq \langle h,v - u(t)\rangle_U \] for all \(v \in K\), where \(J^0\) denotes the Clarke directional derivative of a locally Lipschitz function \(J\). The authors demonstrate the nonemptiness and compactness of the solution set to the above problem. The existence of an optimal control is proved and the well-posedness of the problem, including the existence, uniqueness and stability of solutions is studied and a sensitivity analysis of the problem related to multiparameters is explored. An application to a fractional heat equation is considered. Reviewer: Valerii V. Obukhovskij (Voronezh)</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Generalized relative interiors and generalized convexity in infinite-dimensional spaces</title> <id>https://zbmath.org/1553.49022</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.49022" /> <author> <name>&quot;Long, Vo Si Trong&quot;</name> <uri>https://zbmath.org/authors/?q=ai:vo-si-trong-long.</uri> </author> <author> <name>&quot;Mordukhovich, Boris S.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:mordukhovich.boris-s</uri> </author> <author> <name>&quot;Nam, Nguyen Mau&quot;</name> <uri>https://zbmath.org/authors/?q=ai:nam.nguyen-mau</uri> </author> <content type="text">Summary: This paper focuses on investigating generalized relative interior notions for sets in locally convex topological vector spaces with particular attentions to graphs of set-valued mappings and epigraphs of extended-real-valued functions. We introduce, study, and utilize a novel notion of \textit{quasi-near convexity} of sets that is an infinite-dimensional extension of the widely acknowledged notion of near convexity. Quasi-near convexity is associated with the quasi-relative interior of sets, which is investigated in the paper together with other generalized relative interior notions for sets, not necessarily convex. In this way, we obtain new results on generalized relative interiors for graphs of set-valued mappings in convexity and generalized convexity settings.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">On the convergence of efficient solutions to semi-infinite set-optimization problems</title> <id>https://zbmath.org/1553.49023</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.49023" /> <author> <name>&quot;Anh, Lam Quoc&quot;</name> <uri>https://zbmath.org/authors/?q=ai:anh.lam-quoc</uri> </author> <author> <name>&quot;Lam Van Day&quot;</name> <uri>https://zbmath.org/authors/?q=ai:lam-van-day.</uri> </author> <author> <name>&quot;Duy, Tran Quoc&quot;</name> <uri>https://zbmath.org/authors/?q=ai:duy.tran-quoc</uri> </author> <content type="text">In this paper, a semi-infinite set optimization problem is studied, regarding the stability of its efficient solutions under perturbations of both objective and constraint maps. First, it is shown that the constraint map is continuous and compact-valued, under suitable assumptions. Then this result is used to study convergence conditions for the semi-infinite problem. Reviewer: Nicolas Hadjisavvas (Ermoupoli)</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">A comparative study of sensitivity computations in ESDIRK-based optimal control problems</title> <id>https://zbmath.org/1553.49028</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.49028" /> <author> <name>&quot;Christensen, Anders Hilmar Damm&quot;</name> <uri>https://zbmath.org/authors/?q=ai:christensen.anders-hilmar-damm</uri> </author> <author> <name>&quot;J酶rgensen, John Bagterp&quot;</name> <uri>https://zbmath.org/authors/?q=ai:jorgensen.john-bagterp</uri> </author> <content type="text">Summary: This paper compares the impact of iterated and direct approaches to sensitivity computation in fixed step-size explicit singly diagonally implicit Runge-Kutta (ESDIRK) methods when applied to optimal control problems (OCPs). We strictly use the principle of internal numerical differentiation (IND) for the iterated approach, i.e., reusing iteration matrix factorizations, the number of Newton-type iterations, and Newton iterates, to compute the sensitivities. The direct method computes the sensitivities without using the Newton schemes. We compare the impact of these sensitivity computations in OCPs for the quadruple tank system (QTS). We discretize the OCPs using multiple shooting and solve these with a sequential quadratic programming (SQP) solver. We benchmark the iterated and direct approaches against a base case. This base case applies the ESDIRK methods with exact Newton schemes and a direct approach for sensitivity computations. In these OCPs, we vary the number of integration steps between control intervals and evaluate the performance based on the number of SQP and QPs iterations, KKT violations, function evaluations, Jacobian updates, and iteration matrix factorizations. We also provide examples using the continuous-stirred tank reactor (CSTR), and the IPOPT algorithm instead of the SQP. For OCPs solved using SQP, the QTS results show the direct method converges only once, while the iterated approach and base case converges in all situations. Similar results are seen with the CSTR. Using IPOPT, both the iterated approach and base case converge in all cases. In contrast, the direct method only converges in all cases regarding the CSTR.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">A method for constructing an optimal control strategy in a linear terminal problem</title> <id>https://zbmath.org/1553.49032</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.49032" /> <author> <name>&quot;Kostsyukevich, Dmitri沫 Arkad'evich&quot;</name> <uri>https://zbmath.org/authors/?q=ai:kostyukevich.dmitrii-arkadevich</uri> </author> <author> <name>&quot;Dmitruk, Nataliya Mikha沫lovna&quot;</name> <uri>https://zbmath.org/authors/?q=ai:dmitruk.nataliya-mikhailovna</uri> </author> <content type="text">Summary: This paper deals with an optimal control problem for a linear discrete system subject to unknown bounded disturbances, where the control goal is to steer the system with guarantees into a given terminal set while minimising the terminal cost function. We define an optimal control strategy which takes into account the state of the system at one future time instant and propose an efficient numerical method for its construction. The results of numerical experiments show an improvement in performance under the optimal control strategy in comparison to the optimal open-loop worst-case control while maintaining comparable computation times.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Shape optimization under a constraint on the worst-case scenario</title> <id>https://zbmath.org/1553.49037</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.49037" /> <author> <name>&quot;Caubet, Fabien&quot;</name> <uri>https://zbmath.org/authors/?q=ai:caubet.fabien</uri> </author> <author> <name>&quot;Dambrine, Marc&quot;</name> <uri>https://zbmath.org/authors/?q=ai:dambrine.marc</uri> </author> <author> <name>&quot;Gargantini, Giulio&quot;</name> <uri>https://zbmath.org/authors/?q=ai:gargantini.giulio</uri> </author> <author> <name>&quot;Maynadier, J茅r么me&quot;</name> <uri>https://zbmath.org/authors/?q=ai:maynadier.jerome</uri> </author> <content type="text">Summary: This work falls within the general framework of robust shape optimization under constraints, where a physical parameter of the problem is poorly known. In particular, we study problems where one of the constraints concerns the maximal possible value that a given shape functional can assume when the uncertain parameter varies within an admissible range. Two different approaches are considered: the first one based on the approximation of the set of admissible uncertain parameters by a convex polyhedron, and the second one relying on the notion of subdifferential in the sense of Clarke. The main contributions of this work consist in the theoretical proof of convergence of the first approach under suitable hypotheses of convexity of the set of admissible parameters and of the constraint, and the adaptation of Clarke's subdifferential in the context of robust shape optimization. The two techniques are compared numerically in three examples, with the objective of minimizing the volume of elastic structures under a constraint on the worst-case scenario for the mechanical compliance and the von Mises stress.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Learning optimal admission control in partially observable queueing networks</title> <id>https://zbmath.org/1553.60154</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.60154" /> <author> <name>&quot;Anselmi, Jonatha&quot;</name> <uri>https://zbmath.org/authors/?q=ai:anselmi.jonatha</uri> </author> <author> <name>&quot;Gaujal, Bruno&quot;</name> <uri>https://zbmath.org/authors/?q=ai:gaujal.bruno</uri> </author> <author> <name>&quot;Rebuffi, Louis-S茅bastien&quot;</name> <uri>https://zbmath.org/authors/?q=ai:rebuffi.louis-sebastien</uri> </author> <content type="text">Summary: We develop an efficient reinforcement learning algorithm that learns the optimal admission control policy in a partially observable queueing network. Specifically, only the arrival and departure times from the network are observable, optimality refers to the average holding/rejection cost in infinite horizon, and efficiency is with respect to regret performance. While reinforcement learning in partially-observable Markov Decision Processes (MDP) is prohibitively expensive in general, we show that the regret at time \(T\) induced by our algorithm is \(\tilde{O} \left( \sqrt{T \log (1/\rho)} \right)\) where \(\rho \in (0, 1)\) is connected to the mixing time of the underlying MDP. In contrast with existing regret bounds, ours does not depend on the \textit{diameter} (\(D)\) of the underlying MDP, which in most queueing systems is at least exponential in \(S\), i.e., the maximal number of jobs in the network. Instead, the role of the diameter is played by the \(\log (1/\rho)\) term, which may depend on \(S\) but we find that such dependence is ``minimal''. In the case of acyclic or \textit{hyperstable} queueing networks, we prove that \(\log (1/\rho) = O(S)\), which overall provides a regret bound of the order of \(\tilde{O} \left( \sqrt{TS} \right)\). In the general case, numerical simulations support the claim that the term \(\log (1/\rho)\) remains extremely small compared to the diameter. The novelty of our approach is to leverage Norton's theorem for queueing networks and an efficient reinforcement learning algorithm for MDPs with the structure of birth-and-death processes.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Singular control of (reflected) Brownian motion: a computational method suitable for queueing applications</title> <id>https://zbmath.org/1553.60155</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.60155" /> <author> <name>&quot;Ata, Baris&quot;</name> <uri>https://zbmath.org/authors/?q=ai:ata.baris</uri> </author> <author> <name>&quot;Harrison, J. Michael&quot;</name> <uri>https://zbmath.org/authors/?q=ai:harrison.j-michael</uri> </author> <author> <name>&quot;Si, Nian&quot;</name> <uri>https://zbmath.org/authors/?q=ai:si.nian</uri> </author> <content type="text">Summary: Motivated by applications in queueing theory, we consider a class of singular stochastic control problems whose state space is the \(d\)-dimensional positive orthant. The original problem is approximated by a drift control problem, to which we apply a recently developed computational method that is feasible for dimensions up to \(d=30\) or more. To show that nearly optimal solutions are obtainable using this method, we present computational results for a variety of examples, including queueing network examples that have appeared previously in the literature.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">On the length of a queue in a mixed priority system under conditions of critical loading</title> <id>https://zbmath.org/1553.60156</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.60156" /> <author> <name>&quot;Bergovin, A. K.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:bergovin.a-k</uri> </author> <author> <name>&quot;Ushakov, V. G.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:ushakov.vadim-gennadevich|ushakov.vladimir-g</uri> </author> <content type="text">Summary: A study is performed of a single-channel queueing system with three Poisson arrivals. The service times for requirements of each arrival have an arbitrary absolutely continuous distribution. Requirements of the first arrival take relative priority over those of the second arrival and absolute priority of new service over requirements of the third arrival. Requirements of the second arrival take relative priority over those of the third arrival. The limit distribution of the number of requirements of the third arrival in the system is found while the loading and time simultaneously tend to unity and infinity, respectively.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Analysis of a two-queue discrete-time model with random alternating service under high occupancy in one queue</title> <id>https://zbmath.org/1553.60157</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.60157" /> <author> <name>&quot;Devos, Arnaud&quot;</name> <uri>https://zbmath.org/authors/?q=ai:devos.arnaud</uri> </author> <author> <name>&quot;Walraevens, Joris&quot;</name> <uri>https://zbmath.org/authors/?q=ai:walraevens.joris</uri> </author> <author> <name>&quot;Bruneel, Herwig&quot;</name> <uri>https://zbmath.org/authors/?q=ai:bruneel.herwig</uri> </author> <content type="text">Summary: We investigate a discrete-time two-queue system with a single server. At the beginning of every time slot, the single server randomly selects either queue 1 or queue 2 to serve. The decision of the server to select either queue 1 or queue 2 in each time slot is independent of the state of the system and is determined by a single parameter. The service times of the customers are deterministically equal to 1 time slot. The numbers of arrivals into both queues during consecutive slots are characterized by a joint probability generating function. By extending prior research, we analyze the behavior of the system as the number of customers in the first queue approaches infinity, thereby obtaining exact asymptotics for the stationary joint probability distribution of customer numbers in both queues.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Strategy analysis of retrial queue with parallel customer and standby server</title> <id>https://zbmath.org/1553.60159</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.60159" /> <author> <name>&quot;Liu, Xinlei&quot;</name> <uri>https://zbmath.org/authors/?q=ai:liu.xinlei</uri> </author> <author> <name>&quot;Xu, Xiuli&quot;</name> <uri>https://zbmath.org/authors/?q=ai:xu.xiuli</uri> </author> <author> <name>&quot;Liu, Mingxin&quot;</name> <uri>https://zbmath.org/authors/?q=ai:liu.mingxin</uri> </author> <content type="text">Summary: The objective of this study is devoted to studying the equilibrium strategy of an unreliable M/M/1+1 retrial queue model, which contains two types of parallel customers and batch service provided by a standby server. Two kinds of customers in this queuing system enter the system in parallel and follow the exponential distribution with different parameters. If the server stays idle, an arrival obtains service immediately; Otherwise, he enters the retrial space and waits for service. When a failure occurs, new customers will not be allowed to enter and the customer who is being served will be excluded from the system. Meanwhile, the system enables the standby server to serve customers in the retrial space with batch service mode. Based on the revenue-cost theory, we propose a benefit function and perform the equilibrium analysis for two types of parallel customers in both fully observable and almost observable cases. In addition, the average social benefits of this particular system are detailed analyzed by using symbolic calculation. Finally, the numerical illustrations that aid in visualizing the changes in customer behavior strategies and social benefits as the different system parameters.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Palm problems arising in BAR approach and its applications</title> <id>https://zbmath.org/1553.60160</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.60160" /> <author> <name>&quot;Miyazawa, Masakiyo&quot;</name> <uri>https://zbmath.org/authors/?q=ai:miyazawa.masakiyo</uri> </author> <content type="text">Summary: We consider Palm distributions arising in a Markov process with time homogeneous transitions which is jointly stationary with multiple point processes. Motivated by a BAR approach studied in the recent paper (Braverman et al. in the BAR approach for multi-class queueing networks with SBP service policies, 2023), we are interested in two problems; when this Markov process inherits the same Markov structure under the Palm distributions, and how the state changes at counting instants of the point processes can be handled to derive stationary equations when there are simultaneous counts and each of them influences the state changes. We affirmatively answer the first problem, and propose a framework for resolving the second problem, which is applicable to a general stationary process, which is not needed to be Markov. We also discuss how those results can be applied in deriving BAR's for the diffusion approximation of queueing models in heavy traffic. In particular, as their new application, the heavy traffic limit of the stationary distribution is derived for a single-server queue with a finite waiting room.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Input estimation from discrete workload observations in a L茅vy-driven storage system</title> <id>https://zbmath.org/1553.60161</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.60161" /> <author> <name>&quot;Nieman, Dennis&quot;</name> <uri>https://zbmath.org/authors/?q=ai:nieman.dennis</uri> </author> <author> <name>&quot;Mandjes, Michel&quot;</name> <uri>https://zbmath.org/authors/?q=ai:mandjes.michel</uri> </author> <author> <name>&quot;Ravner, Liron&quot;</name> <uri>https://zbmath.org/authors/?q=ai:ravner.liron</uri> </author> <content type="text">Summary: Our goal is to estimate the characteristic exponent of the input to a L茅vy-driven storage system from a sample of equispaced workload observations. The estimator relies on an approximate moment equation associated with the Laplace-Stieltjes transform of the workload at exponentially distributed sampling times. The estimator is pointwise consistent for any observation grid. Moreover, a high frequency sampling scheme yields asymptotically normal estimation errors for a class of input processes. A resampling scheme that uses the available information in a more efficient manner is suggested and assessed via simulation experiments.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Capacity allocation in a two-channel service system from a social planner's perspective</title> <id>https://zbmath.org/1553.60162</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.60162" /> <author> <name>&quot;Tun莽alp, Feray&quot;</name> <uri>https://zbmath.org/authors/?q=ai:tuncalp.feray</uri> </author> <author> <name>&quot;脰rmeci, Lerzan&quot;</name> <uri>https://zbmath.org/authors/?q=ai:ormeci.lerzan</uri> </author> <author> <name>&quot;G眉ne艧, Evrim D.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:gunes.evrim-didem</uri> </author> <content type="text">Summary: This paper considers a capacity allocation problem in a two-channel service system. Customers can receive service from either a single-server queueing system, which serves the customers waiting in line one by one, or a clearing service system, which serves a fixed number of customers simultaneously according to its capacity. Customers who join the queueing system should wait till they receive service. In contrast, customers who join the clearing system face the risk of service denial when there are more customers than the clearing system's capacity. The social planner aims to minimize the total expected cost of all customers by determining the capacities and the arrival rates for the two channels. There are two settings: an unobservable setting where only the expected waiting time information is available and an observable setting where real-time information about the exact workload of the queueing system is known. We also consider the same system under the same settings with strategic customers who choose one of the two channels strategically to minimize their costs. The planner still has the same objective but can now decide only on the capacity allocation. Comparing the performance of the resulting systems allows us to understand the value of coordination and information. Extensions of these systems that serve two customer types are also explored.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Queues with correlated inter-arrival and service times</title> <id>https://zbmath.org/1553.60163</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.60163" /> <author> <name>&quot;Wang, Qixin&quot;</name> <uri>https://zbmath.org/authors/?q=ai:wang.qixin</uri> </author> <author> <name>&quot;Hu, Jian-Qiang&quot;</name> <uri>https://zbmath.org/authors/?q=ai:hu.jian-qiang</uri> </author> <content type="text">Summary: We study a type of correlated queue in which its inter-arrival and service times are correlated, with their joint distribution being characterized by a copula function. This characterization allows for very generally correlated inter-arrival and service times. For such a queue, we first derive an infinite system of linear equations for the moments of the waiting time, based on which we design an algorithm to calculate the moments of the waiting time. In contrast with traditional methods, our algorithm incorporates a recursive procedure which is computationally much more efficient. Furthermore, we show how the moments and covariances of the inter-departure times of the queue can be obtained based on the moments of the waiting time. Numerical experiments are provided to validate our method.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">New smoothing function for solving absolute value equations</title> <id>https://zbmath.org/1553.65016</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.65016" /> <author> <name>&quot;Chalekh, Randa&quot;</name> <uri>https://zbmath.org/authors/?q=ai:chalekh.randa</uri> </author> <author> <name>&quot;Djeffal, El Amir&quot;</name> <uri>https://zbmath.org/authors/?q=ai:djeffal.el-amir</uri> </author> <content type="text">Summary: In this paper, we use a smoothing-type algorithm in this paper to solve the AVE, which stands for the absolute value equation \(Ax-|x|=b\), where \(A\) is an arbitrary \(n\times n\) real matrix and \(b\in \mathbb{R}^n\). We reformulate AVE as a system of smooth equations and propose two new smoothing functions. We prove that the algorithm is well-defined when the singular value of \(A\) exceeds one, and under the same assumption, the algorithm is convergent. We show the algorithm's effectiveness with these two functions and compare it with some previously known functions.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">New conjugate gradient image processing methods</title> <id>https://zbmath.org/1553.65047</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.65047" /> <author> <name>&quot;Hassan, Basim A.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:hassan.basim-a</uri> </author> <author> <name>&quot;Moghrabi, Issam A. R.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:moghrabi.issam-a-r</uri> </author> <author> <name>&quot;Sulaiman, Ibrahim M.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:sulaiman.ibrahim-mohammed|sulaiman.ibrahim-m-a</uri> </author> <content type="text">Summary: The particular choice of the coefficient that scales the latest search direction to compute the new one is usually the focal point in conjugate gradient methods. In this paper, a quadratic model is utilized to produce new conjugacy coefficients for the conjugate gradient technique, which are then used to solve picture restoration issues. The algorithms show global convergence and have the required descent property. The results obtained from the numerical tests, demonstrate that the new conjugate gradient approaches outperform the traditional FR conjugate gradient method when employed in solving image restoration problems.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">A superlinearly convergent subgradient method for sharp semismooth problems</title> <id>https://zbmath.org/1553.65052</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.65052" /> <author> <name>&quot;Charisopoulos, Vasileios&quot;</name> <uri>https://zbmath.org/authors/?q=ai:charisopoulos.vasileios</uri> </author> <author> <name>&quot;Davis, Damek&quot;</name> <uri>https://zbmath.org/authors/?q=ai:davis.damek-shea</uri> </author> <content type="text">Summary: Subgradient methods comprise a fundamental class of nonsmooth optimization algorithms. Classical results show that certain subgradient methods converge sublinearly for general Lipschitz convex functions and converge linearly for convex functions that grow sharply away from solutions. Recent work has moreover extended these results to certain nonconvex problems. In this work, we seek to improve the complexity of these algorithms by asking the following question. Is it possible to design a superlinearly convergent subgradient method? We provide a positive answer to this question for a broad class of sharp semismooth functions.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Relaxation quadratic approximation greedy pursuit method based on sparse learning</title> <id>https://zbmath.org/1553.65054</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.65054" /> <author> <name>&quot;Li, Shihai&quot;</name> <uri>https://zbmath.org/authors/?q=ai:li.shihai</uri> </author> <author> <name>&quot;Ma, Changfeng&quot;</name> <uri>https://zbmath.org/authors/?q=ai:ma.changfeng</uri> </author> <content type="text">Summary: A high-performance sparse model is very important for processing high-dimensional data. Therefore, based on the quadratic approximate greed pursuit (QAGP) method, we can make full use of the information of the quadratic lower bound of its approximate function to get the relaxation quadratic approximate greed pursuit (RQAGP) method. The calculation process of the RQAGP method is to construct two inexact quadratic approximation functions by using the \(m\)-strongly convex and \(L\)-smooth characteristics of the objective function and then solve the approximation function iteratively by using the Iterative Hard Thresholding (IHT) method to get the solution of the problem. The convergence analysis is given, and the performance of the method in the sparse logistic regression model is verified on synthetic data and real data sets. The results show that the RQAGP method is effective.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Two modified inertial algorithms for a class of split common null point problems with demi-contractive mapping</title> <id>https://zbmath.org/1553.65057</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.65057" /> <author> <name>&quot;Tang, Yan&quot;</name> <uri>https://zbmath.org/authors/?q=ai:tang.yan</uri> </author> <author> <name>&quot;Zhang, Shiqing&quot;</name> <uri>https://zbmath.org/authors/?q=ai:zhang.shiqing.1|zhang.shiqing</uri> </author> <author> <name>&quot;Zhou, Haiyun&quot;</name> <uri>https://zbmath.org/authors/?q=ai:zhou.haiyun</uri> </author> <content type="text">Summary: We focus on two alternating inertial projection iterative algorithms to a class of split common null point problem, specifically, the common solution of the pseudomonotone variational inequality problem and the fixed-point problem of demi-contractive mapping. We construct the relation between the inertial parameters and Mann's iteration coefficients to obtain the convergence, which in turn allows some interesting results, that is, the traditional constraints on inertia parameters can be removed. Meanwhile, we give two numerical examples to verify the superiority and effectiveness of the schemes.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">A non-local system modeling bi-directional traffic flows</title> <id>https://zbmath.org/1553.65100</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.65100" /> <author> <name>&quot;Chiarello, Felisia Angela&quot;</name> <uri>https://zbmath.org/authors/?q=ai:chiarello.felisia-angela</uri> </author> <author> <name>&quot;Goatin, Paola&quot;</name> <uri>https://zbmath.org/authors/?q=ai:goatin.paola</uri> </author> <content type="text">The authors investigate a mathematical model addressing the dynamics of two groups of agents moving in opposite directions. This research contributes to the macroscopic traffic flow literature by introducing a system of conservation laws with non-local fluxes, which are coupled in the speed function. The scientific problem addressed in the paper lies in modelling and analysing bi-directional traffic flows using a macroscopic framework. Traditional traffic flow models such as the Lighthill-Whitham-Richards (LWR) model focus on local dynamics. In contrast, the authors extend the classical model by incorporating non-local effects, allowing the velocity of agents to depend on a weighted average of downstream traffic density. This approach accounts for the behavioural adaptation of agents based on their observations of traffic conditions ahead. The study draws from a mixed-type system proposed in earlier works, where hyperbolicity and the existence of solutions were challenging to establish due to oscillations arising in non-hyperbolic regions of the phase space. By introducing non-local terms in the speed functions, the authors aim to ensure the existence of solutions while preserving the physical realism of the model. To address these challenges, the authors formulate a \(2 \times 2\) system of conservation laws with non-local fluxes. The density of agents moving in each direction is governed by equations that incorporate convolution terms representing the weighted densities of both groups within specified visibility ranges. The kernels characterising these convolutions are designed to respect physical constraints such as positivity, normalisation, and compact support. The authors employ a finite volume numerical scheme to approximate solutions, ensuring convergence under a suitable CFL condition. Rigorous analysis establishes key properties of the approximate solutions, including positivity, boundedness in \( L^1 \) and \( L^\infty \), and bounded total variation. These properties form the basis for proving the existence of weak solutions locally in time using a Lax-Wendroff type argument and Helly's theorem. The study presents several numerical tests to explore the behaviour of the proposed model under varying conditions. These tests examine the impact of kernel support size, periodic boundary conditions, and agent heterogeneity in velocity and look-ahead distance. The results demonstrate that the solutions of the non-local model exhibit consistent behaviour with their local counterparts when kernel supports are sufficiently small. Furthermore, the numerical simulations reveal the role of kernel and velocity parameters in influencing solution stability and oscillatory behaviour. For example, agents with longer look-ahead distances exhibit reduced oscillations, highlighting the importance of non-local terms in regulating traffic dynamics. This research is significant for its theoretical and practical contributions to the field of traffic flow modelling. The incorporation of non-local effects addresses limitations of classical models by capturing more realistic agent interactions. The authors' analytical framework ensures mathematical rigour, while the numerical experiments provide insights into practical scenarios, paving the way for applications in traffic management and urban planning. By bridging theoretical developments and empirical observations, this work offers a robust foundation for further investigations into non-local macroscopic models across diverse fields. For the entire collection see [Zbl 1530.65011]. Reviewer: Denys Dutykh (Le Bourget-du-Lac)</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Phase transition of the 3-majority opinion dynamics with noisy interactions</title> <id>https://zbmath.org/1553.68042</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.68042" /> <author> <name>&quot;d'Amore, Francesco&quot;</name> <uri>https://zbmath.org/authors/?q=ai:damore.francesco</uri> </author> <author> <name>&quot;Ziccardi, Isabella&quot;</name> <uri>https://zbmath.org/authors/?q=ai:ziccardi.isabella</uri> </author> <content type="text">Summary: Communication noise is a common feature in several real-world scenarios where systems of agents need to communicate in order to pursue some collective task. Indeed, many biologically inspired systems that try to achieve agreements on some opinion must implement \textit{resilient} dynamics, i.e. that are not strongly affected by noisy communications. In this work, we study the \textsc{3-Majority} dynamics, an opinion dynamics that has been shown to be an efficient protocol for the majority consensus problem, in which we introduce a simple feature of uniform communication noise, following [the authors, Lect. Notes Comput. Sci. 13298, 98--115 (2022; Zbl 07615853)]. We prove that, in the fully connected communication network of \(n\) agents and in the binary opinion case, the process induced by the \textsc{3-Majority} dynamics exhibits a phase transition. For a noise probability \(p &lt; 1 / 3\), the dynamics reach in logarithmic time an almost-consensus metastable phase which lasts for a polynomial number of rounds with high probability. We characterize this phase by showing that there exists an attractive equilibrium value \(s_{\text{eq}} \in [n]\) for the bias of the system, i.e. the difference between the majority community size and the minority one. Moreover, we show that the agreement opinion is the initial majority one if the bias towards it is of magnitude \(\Omega(\sqrt{n \log n})\) in the initial configuration. If, instead, \(p &gt; 1 / 3\), we show that no form of consensus is possible, and any information regarding the initial majority opinion is lost in logarithmic time with high probability. Despite more communications per-round being allowed, the \textsc{3-Majority} dynamics surprisingly turns out to be less resilient to noise than the \textsc{Undecided-State} dynamics, whose noise threshold value is \(p = 1 / 2\).</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Core allocation to minimize total flow time in a multicore system in the presence of a processing time constraint</title> <id>https://zbmath.org/1553.68067</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.68067" /> <author> <name>&quot;Vesilo, Rein&quot;</name> <uri>https://zbmath.org/authors/?q=ai:vesilo.rein</uri> </author> <content type="text">Summary: Data centers are a vital and fundamental infrastructure component of the cloud. The requirement to execute a large number of demanding jobs places a premium on processing capacity. Parallelizing jobs to run on multiple cores reduces execution time. However, there is a decreasing marginal benefit to using more cores, with the speedup function quantifying the achievable gains. A critical performance metric is flow time. Previous results in the literature derived closed-form expressions for the optimal allocation of cores to minimize total flow time for a power-law speedup function if all jobs are present at time 0. However, this work did not place a constraint on the makespan. For many diverse applications, fast response times are essential, and latency targets are specified to avoid adverse impacts on user experience. This paper is the first to determine the optimal core allocations for a multicore system to minimize total flow time in the presence of a completion deadline (where all jobs have the same deadline). The allocation problem is formulated as a nonlinear optimization program that is solved using the Lagrange multiplier technique. Closed-form expressions are derived for the optimal core allocations, total flow time, and makespan, which can be fitted to a specified deadline by adjusting the value of a single Lagrange multiplier. Compared to the unconstrained problem, the shortest job first property for optimal allocation is maintained; however, a number of other properties require revising and other properties are only retained in a modified form (such as the scale-free and size-dependence properties). It is found that with a completion deadline the optimal solution may contain groups of simultaneous completions. In general, all possible patterns of single- and group-completion need to be considered, producing an exponential search space. However, the paper determines analytically that the optimal completion pattern consists of a sequence of single completions followed by a single group of simultaneous completions at the end, which reduces the search space dimension to being linear. The paper validates the Lagrange multiplier approach by verifying constraint qualifications.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">A QUBO formulation for the tree containment problem</title> <id>https://zbmath.org/1553.68097</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.68097" /> <author> <name>&quot;Dinneen, Michael J.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:dinneen.michael-j</uri> </author> <author> <name>&quot;Ghodla, Pankaj S.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:ghodla.pankaj-s</uri> </author> <author> <name>&quot;Linz, Simone&quot;</name> <uri>https://zbmath.org/authors/?q=ai:linz.simone</uri> </author> <content type="text">Summary: Phylogenetic (evolutionary) trees and networks are leaf-labeled graphs that are widely used to represent the evolutionary relationships between entities such as species, languages, cancer cells, and viruses. To reconstruct and analyze phylogenetic networks, the problem of deciding whether or not a given rooted phylogenetic network embeds a given rooted phylogenetic tree is of recurring interest. This problem, formally know as Tree Containment, is NP-complete in general and polynomial-time solvable for certain classes of phylogenetic networks. In this paper, we connect ideas from quantum computing and phylogenetics to present an efficient Quadratic Unconstrained Binary Optimization formulation for Tree Containment in the general setting. For an instance \((\mathcal{N}, \mathcal{T})\) of Tree Containment, where \(\mathcal{N}\) is a phylogenetic network with \(n_{\mathcal{N}}\) vertices and \(\mathcal{T}\) is a phylogenetic tree with \(n_{\mathcal{T}}\) vertices, the number of logical qubits that are required for our formulation is \(O(n_{\mathcal{N}} n_{\mathcal{T}})\).</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">4/3 rectangle tiling lower bound</title> <id>https://zbmath.org/1553.68105</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.68105" /> <author> <name>&quot;G艂uch, Grzegorz&quot;</name> <uri>https://zbmath.org/authors/?q=ai:gluch.grzegorz</uri> </author> <author> <name>&quot;Lory艣, Krzysztof&quot;</name> <uri>https://zbmath.org/authors/?q=ai:lorys.krzysztof</uri> </author> <content type="text">Summary: The problem that we consider is the following: given an \(n\times n\) array \(A\) of positive numbers and a natural number \(p\), find a tiling using at most \(p\) rectangles (which means that each array element must be covered by some rectangle and no two rectangles must overlap) that minimizes the maximum weight of any rectangle (the weight of a rectangle is the sum of elements which are covered by it). We prove that it is NP-hard to approximate this problem to within a factor of \(1 \frac{1}{3}\) (the previous best result was \(1\frac{1}{4}\)).</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">On the complexity of reachability in parametric Markov decision processes</title> <id>https://zbmath.org/1553.68119</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.68119" /> <author> <name>&quot;Winkler, Tobias&quot;</name> <uri>https://zbmath.org/authors/?q=ai:winkler.tobias</uri> </author> <author> <name>&quot;Junges, Sebastian&quot;</name> <uri>https://zbmath.org/authors/?q=ai:junges.sebastian</uri> </author> <author> <name>&quot;P茅rez, Guillermo A.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:perez.guillermo-a</uri> </author> <author> <name>&quot;Katoen, Joost-Pieter&quot;</name> <uri>https://zbmath.org/authors/?q=ai:katoen.joost-pieter</uri> </author> <content type="text">Summary: This paper studies parametric Markov decision processes (pMDPs), an extension to Markov decision processes (MDPs) where transitions probabilities are described by polynomials over a finite set of parameters. Fixing values for all parameters yields MDPs. In particular, this paper studies the complexity of finding values for these parameters such that the induced MDP satisfies some reachability constraints. We discuss different variants depending on the comparison operator in the constraints and the domain of the parameter values. We improve all known lower bounds for this problem, and notably provide ETR-completeness results for distinct variants of this problem. Furthermore, we provide insights in the functions describing the induced reachability probabilities, and how pMDPs generalise concurrent stochastic reachability games. For the entire collection see [Zbl 1423.68023].</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Combinations of qualitative winning for stochastic parity games</title> <id>https://zbmath.org/1553.68164</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.68164" /> <author> <name>&quot;Chatterjee, Krishnendu&quot;</name> <uri>https://zbmath.org/authors/?q=ai:chatterjee.krishnendu</uri> </author> <author> <name>&quot;Piterman, Nir&quot;</name> <uri>https://zbmath.org/authors/?q=ai:piterman.nir</uri> </author> <content type="text">Summary: We study Markov decision processes and turn-based stochastic games with parity conditions. There are three qualitative winning criteria, namely, sure winning, which requires all paths to satisfy the condition, almost-sure winning, which requires the condition to be satisfied with probability 1, and limit-sure winning, which requires the condition to be satisfied with probability arbitrarily close to 1. We study the combination of two of these criteria for parity conditions, e.g., there are two parity conditions one of which must be won surely, and the other almost-surely. The problem has been studied recently by \textit{R. Berthon} et al. [LIPIcs -- Leibniz Int. Proc. Inform. 80, Article 121, 15 p. (2017; Zbl 1442.90199)] for MDPs with combination of sure and almost-sure winning, under infinite-memory strategies, and the problem has been established to be in \(\text{NP}\cap\text{co-NP}\). Even in MDPs there is a difference between finite-memory and infinite-memory strategies. Our main results for combination of sure and almost-sure winning are as follows: (a) we show that for MDPs with finite-memory strategies the problem is in \(\text{NP}\cap\text{co-NP}\); (b) we show that for turn-based stochastic games the problem is co-NP-complete, both for finite-memory and infinite-memory strategies; and (c) we present algorithmic results for the finite-memory case, both for MDPs and turn-based stochastic games, by reduction to non-stochastic parity games. In addition we show that all the above complexity results also carry over to combination of sure and limit-sure winning, and results for all other combinations can be derived from existing results in the literature. Thus we present a complete picture for the study of combinations of two qualitative winning criteria for parity conditions in MDPs and turn-based stochastic games. For the entire collection see [Zbl 1423.68023].</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">On min sum vertex cover and generalized min sum set cover</title> <id>https://zbmath.org/1553.68211</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.68211" /> <author> <name>&quot;Bansal, Nikhil&quot;</name> <uri>https://zbmath.org/authors/?q=ai:bansal.nikhil</uri> </author> <author> <name>&quot;Batra, Jatin&quot;</name> <uri>https://zbmath.org/authors/?q=ai:batra.jatin</uri> </author> <author> <name>&quot;Farhadi, Majid&quot;</name> <uri>https://zbmath.org/authors/?q=ai:farhadi.majid</uri> </author> <author> <name>&quot;Tetali, Prasad&quot;</name> <uri>https://zbmath.org/authors/?q=ai:tetali.prasad|tetali.prasad-vsrv</uri> </author> <content type="text">Summary: We study the Generalized Min Sum Set Cover (GMSSC) problem, wherein given a collection of hyperedges \(E\) with arbitrary covering requirements \(\{k_e\in\mathbb{Z}^+:e\in E\}\), the goal is to find an ordering of the vertices to minimize the total cover time of the hyperedges; a hyperedge \(e\) is considered covered by the first time when \(k_e\) and many of its vertices appear in the ordering. We give a \(4.642\) approximation algorithm for GMSSC, coming close to the best possible bound of 4, already for the classical special case (with all \(k_e=1\)) of Min Sum Set Cover (MSSC) studied by Feige, Lov谩sz, and Tetali, and improving upon the previous best known bound of \(12.4\) due to Im, Sviridenko, and van der Zwaan. Our algorithm is based on transforming the LP solution by a suitable \textit{kernel} and applying randomized rounding. As part of the analysis of our algorithm, we also derive an inequality on the lower tail of a sum of independent Bernoulli random variables, which might be of independent interest and broader utility. Min Sum Vertex Cover (MSVC) is a well-known special case of MSSC in which the input hypergraph is a graph (i.e., \(|e|=2\)) and \(k_e=1\) for every edge \(e\in E\). We give a \(16/9\simeq 1.778\) approximation for MSVC and show a matching integrality gap for the natural LP relaxation. This improves upon the previous best \(1.999946\) approximation of Barenholz, Feige, and Peleg. Finally, we revisit MSSC and consider the \(\ell_p\) norm of cover-time of the hyperedges. Using a dual fitting argument, we show that the natural greedy algorithm achieves tight, up to NP-hardness, approximation guarantees of \((p+1)^{1+1/p}\) for all \(p\geq 1\), giving another proof of the result of Golovin, Gupta, Kumar, and Tangwongsan, and showing its tightness up to NP-hardness. For \(p=1\), this gives yet another proof of the 4 approximation for MSSC.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">A general label setting algorithm and tractability analysis for the multiobjective temporal shortest path problem</title> <id>https://zbmath.org/1553.68213</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.68213" /> <author> <name>&quot;Bazgan, Cristina&quot;</name> <uri>https://zbmath.org/authors/?q=ai:bazgan.cristina</uri> </author> <author> <name>&quot;Kager, Johannes&quot;</name> <uri>https://zbmath.org/authors/?q=ai:kager.johannes</uri> </author> <author> <name>&quot;Thielen, Clemens&quot;</name> <uri>https://zbmath.org/authors/?q=ai:thielen.clemens</uri> </author> <author> <name>&quot;Vanderpooten, Daniel&quot;</name> <uri>https://zbmath.org/authors/?q=ai:vanderpooten.daniel</uri> </author> <content type="text">Summary: Given a directed temporal graph, a start node \( s\), and \( p \) objectives, the task in the single-source multiobjective temporal shortest path problem (SSMTSPP) consists of computing the set of nondominated images of temporal \( s \)-\( v \)-paths for each node \( v\ne s\) as well as one corresponding efficient path for each of these images. This problem generalizes both the multiobjective shortest path problem in static graphs and the single-objective temporal shortest path problem. In this article, we provide a general label setting algorithm for the SSMTSPP that can handle a large variety of different objectives. The only condition imposed on the objectives is a monotonicity property that generalizes the nonnegativity of the arc costs required for the well-known label setting algorithm for solving the static single-source shortest path problem in both the single objective and the multiobjective case. Our analysis of the presented algorithm shows that its worst-case running time is polynomial in the sum of the input size of the problem instance and the number of nondominated images, which implies that it runs in polynomial time as long as the number of nondominated images is polynomial in the instance size (i.e., for all versions of the problem). To complement this result, we provide a complete classification into tractable and intractable problems for all SSMTSPPs involving a large variety of objectives. In particular, using our general analysis, this provides a large range of specific SSMTSPPs for which our general label setting algorithm runs in polynomial time. {\copyright} 2024 The Author(s). \textit{Networks} published by Wiley Periodicals LLC.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Euclidean maximum matchings in the plane -- local to global</title> <id>https://zbmath.org/1553.68217</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.68217" /> <author> <name>&quot;Biniaz, Ahmad&quot;</name> <uri>https://zbmath.org/authors/?q=ai:biniaz.ahmad</uri> </author> <author> <name>&quot;Maheshwari, Anil&quot;</name> <uri>https://zbmath.org/authors/?q=ai:maheshwari.anil</uri> </author> <author> <name>&quot;Smid, Michiel&quot;</name> <uri>https://zbmath.org/authors/?q=ai:smid.michiel-h-m</uri> </author> <content type="text">Summary: Let \(M\) be a perfect matching on a set of points in the plane where every edge is a line segment between two points. We say that \(M\) is \textit{globally maximum} if it is a maximum-length matching on all points. We say that \(M\) is \(k\)-\textit{local maximum} if for any subset \(M'=\{a_1b_1,\dots ,a_kb_k\}\) of \(k\) edges of \(M\) it holds that \(M'\) is a maximum-length matching on points \(\{a_1,b_1,\dots ,a_k,b_k\}\). We show that local maximum matchings are good approximations of global ones. Let \(\mu_k\) be the infimum ratio of the length of any \(k\)-local maximum matching to the length of any global maximum matching, over all finite point sets in the Euclidean plane. It is known that \(\mu_k\geqslant \frac{k-1}{k}\) for any \(k\geqslant 2\). We show the following improved bounds for \(k\in \{2,3\}: \sqrt{3/7}\leqslant \mu_2 &lt; 0.93\) and \(\sqrt{3}/2\leqslant \mu_3 &lt; 0.98\). We also show that every pairwise crossing matching is unique and it is globally maximum. Towards our proof of the lower bound for \(\mu_2\) we show the following result which is of independent interest: If we increase the radii of pairwise intersecting disks by factor \(2/\sqrt{3}\), then the resulting disks have a common intersection.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">An exact quadratic algorithm for the shortest tree transformation</title> <id>https://zbmath.org/1553.68229</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.68229" /> <author> <name>&quot;Gorbunov, K. Yu.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:gorbunov.konstantin-yu</uri> </author> <author> <name>&quot;Lyubetsky, V. A.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:lyubetsky.vassily-a</uri> </author> <content type="text">Summary: The article proposes a new exact algorithm of quadratic complexity that solves the problem of the shortest transformation (``alignment'') of one weighted tree into another, taking into account arbitrary costs of operations on trees. Three operations are considered: adding vertex deletions to an edge or root of a tree and shifting a subtree with deletions.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Temporal interval cliques and independent sets</title> <id>https://zbmath.org/1553.68231</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.68231" /> <author> <name>&quot;Hermelin, Danny&quot;</name> <uri>https://zbmath.org/authors/?q=ai:hermelin.danny</uri> </author> <author> <name>&quot;Itzhaki, Yuval&quot;</name> <uri>https://zbmath.org/authors/?q=ai:itzhaki.yuval</uri> </author> <author> <name>&quot;Molter, Hendrik&quot;</name> <uri>https://zbmath.org/authors/?q=ai:molter.hendrik</uri> </author> <author> <name>&quot;Niedermeier, Rolf&quot;</name> <uri>https://zbmath.org/authors/?q=ai:niedermeier.rolf</uri> </author> <content type="text">Summary: Temporal graphs have been recently introduced to model changes in a given network that occur throughout a fixed period of time. The \textsc{Temporal} \(\Delta\) \textsc{Clique} problem, which generalizes the well known \textsc{Clique} problem to temporal graphs, has been studied in the context of finding nodes of interest in dynamic networks [\textit{J. Viard} et al., Theor. Comput. Sci. 609, Part 1, 245--252 (2016; Zbl 1331.68158)]. We introduce the \textsc{Temporal} \(\Delta\) \textsc{Independent Set} problem, a temporal generalization of \textsc{Independent Set}. This problem is e.g. motivated in the context of finding conflict-free schedules for maximum subsets of tasks, that have certain (time-varying) constraints within a given time period. We are specifically interested in the case where each task needs to be performed in a certain time-interval on each day and two tasks are in conflict on a certain day if their time-intervals on that day overlap. This leads us to consider both problems on the restricted class of temporal unit interval graphs, i.e., temporal graphs where each layer is a unit interval graph. We present several hardness results as well as positive results. On the algorithmic side, we provide constant-factor approximation algorithms for instances of both problems where \(\tau\), the total number of time steps (layers) of the temporal graph, and \(\Delta\), a parameter that allows us to model conflict tolerance, are constants. We develop an exact \textsf{FPT} algorithm for \textsc{Temporal} \(\Delta\) \textsc{Clique} with respect to parameter \(\tau + k\). Finally, we use the notion of order preservation for temporal unit interval graphs that, informally, requires the intervals of every layer to obey a common ordering. For both problems, we provide an \textsf{FPT} algorithm parameterized by the size of minimum vertex deletion set to order preservation.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Better hardness results for the minimum spanning tree congestion problem</title> <id>https://zbmath.org/1553.68234</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.68234" /> <author> <name>&quot;Luu, Huong&quot;</name> <uri>https://zbmath.org/authors/?q=ai:luu.huong</uri> </author> <author> <name>&quot;Chrobak, Marek&quot;</name> <uri>https://zbmath.org/authors/?q=ai:chrobak.marek</uri> </author> <content type="text">Summary: In the spanning tree congestion problem, given a connected graph \(G\), the objective is to compute a spanning tree \(T\) in \(G\) for which the maximum edge congestion is minimized, where the congestion of an edge \(e\) of \(T\) is the number of vertex pairs adjacent in \(G\) for which the path connecting them in \(T\) traverses \(e\). The problem is known to be \({\mathbb{N}\mathbb{P}}\)-hard, but its approximability is still poorly understood, and it is not even known whether the optimum can be efficiently approximated with ratio \(o(n)\). In the decision version of this problem, denoted \(K\)-\textsf{STC}, we need to determine if \(G\) has a spanning tree with congestion at most \(K\). It is known that \(K\)-\textsf{STC} is \({\mathbb{N}\mathbb{P}}\)-complete for \(K\ge 8\), and this implies a lower bound of 1.125 on the approximation ratio of minimizing congestion. On the other hand, \(3\)-\textsf{STC} can be solved in polynomial time, with the complexity status of this problem for \(K\in{\left\{4,5,6,7 \right\}}\) remaining an open problem. We substantially improve the earlier hardness result by proving that \(K\)-\textsf{STC} is \({\mathbb{N}\mathbb{P}}\)-complete for \(K\ge 5\). This leaves only the case \(K=4\) open, and improves the lower bound on the approximation ratio to 1.2. For the entire collection see [Zbl 1524.68008].</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Better hardness results for the minimum spanning tree congestion problem</title> <id>https://zbmath.org/1553.68235</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.68235" /> <author> <name>&quot;Luu, Huong&quot;</name> <uri>https://zbmath.org/authors/?q=ai:luu.huong</uri> </author> <author> <name>&quot;Chrobak, Marek&quot;</name> <uri>https://zbmath.org/authors/?q=ai:chrobak.marek</uri> </author> <content type="text">Summary: In the spanning tree congestion problem, given a connected graph \(G\), the objective is to compute a spanning tree \(T\) in \(G\) that minimizes its maximum edge congestion, where the congestion of an edge \(e\) of \(T\) is the number of edges in \(G\) for which the unique path in \(T\) between their endpoints traverses \(e\). The problem is known to be \(\mathbb{N}\mathbb{P}\)-hard, but its approximability is still poorly understood, and it is not even known whether the optimum solution can be efficiently approximated with ratio \(o(n)\). In the decision version of this problem, denoted \(\boldsymbol{K}\)-\textsf{STC}, we need to determine if \(G\) has a spanning tree with congestion at most \(K\). It is known that \(\boldsymbol{K}\)-\textsf{STC} is \(\mathbb{N}\mathbb{P}\)-complete for \(K\ge 8\), and this implies a lower bound of 1.125 on the approximation ratio of minimizing congestion. On the other hand, \(\boldsymbol{3}\)-\textsf{STC} can be solved in polynomial time, with the complexity status of this problem for \(K\in{\left\{4,5,6,7 \right\}}\) remaining an open problem. We substantially improve the earlier hardness results by proving that \(\boldsymbol{K}\)-\textsf{STC} is \(\mathbb{N}\mathbb{P}\)-complete for \(K\ge 5\). This leaves only the case \(K=4\) open, and improves the lower bound on the approximation ratio to 1.2. Motivated by evidence that minimizing congestion is hard even for graphs of small constant radius, we also consider \(\boldsymbol{K}\)-\textsf{STC} restricted to graphs of radius 2, and we prove that this variant is \(\mathbb{N}\mathbb{P}\)-complete for all \(K\ge 6\).</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Computational complexity of the police officer patrol problem on weighted digraphs</title> <id>https://zbmath.org/1553.68243</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.68243" /> <author> <name>&quot;Tomisawa, Masaki&quot;</name> <uri>https://zbmath.org/authors/?q=ai:tomisawa.masaki</uri> </author> <author> <name>&quot;Tohyama, Hiroaki&quot;</name> <uri>https://zbmath.org/authors/?q=ai:tohyama.hiroaki</uri> </author> <content type="text">Summary: A vertex cover of a graph is a set of vertices that includes at least one endpoint of every edge of the graph and can be regarded as the placement of police officers or fixed surveillance cameras so that each street of a neighborhood represented by the graph can be confirmed visually without moving from their position. Given a graph \(G\) and a natural number \(k\), the vertex cover problem is the problem of deciding whether there exists a vertex cover in \(G\) of size at most \(k\). The vertex cover problem is one of Karp's 21 \textbf{NP}-complete problems. Recently, we introduced an edge routing problem that a single police officer must confirm all the streets. The officer is allowed to move, but can confirm any street visually from an incident intersection without traversing it. We showed that the problem of deciding whether there exists a patrol route for a given mixed graph in which each edge is either traversed exactly once or confirmed visually is \textbf{NP}-complete. In this paper, we show that the police officer patrol problem remains \textbf{NP}-complete even if given graphs are weighted digraphs.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Finite-time analysis of natural actor-critic for POMDPs</title> <id>https://zbmath.org/1553.68258</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.68258" /> <author> <name>&quot;Cayci, Semih&quot;</name> <uri>https://zbmath.org/authors/?q=ai:cayci.semih</uri> </author> <author> <name>&quot;He, Niao&quot;</name> <uri>https://zbmath.org/authors/?q=ai:he.niao</uri> </author> <author> <name>&quot;Srikant, R.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:srikant.rayadurgam</uri> </author> <content type="text">Summary: We study the reinforcement learning problem for partially observed Markov decision processes (POMDPs) with large state spaces. We consider a natural actor-critic method that employs an internal memory state for policy parameterization to address partial observability, function approximation in both actor and critic to address the curse of dimensionality, and a multistep temporal difference learning algorithm for policy evaluation. We establish nonasymptotic error bounds for actor-critic methods for partially observed systems under function approximation. In particular, in addition to the function approximation and statistical errors that also arise in MDPs, we explicitly characterize the error due to the use of finite-state controllers. This additional error is stated in terms of the total variation distance between the belief state in POMDPs and the posterior distribution of the hidden state when using a finite-state controller. Further, in the specific case of sliding-window controllers, we show that this inference error can be made arbitrarily small by using larger window sizes under certain ergodicity conditions.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">A fast self-adaptive intuitionistic fuzzy latent factor model</title> <id>https://zbmath.org/1553.68261</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.68261" /> <author> <name>&quot;Lin, Zhanpeng&quot;</name> <uri>https://zbmath.org/authors/?q=ai:lin.zhanpeng</uri> </author> <author> <name>&quot;Hong, Wenxing&quot;</name> <uri>https://zbmath.org/authors/?q=ai:hong.wenxing</uri> </author> <author> <name>&quot;Xu, Xiuqin&quot;</name> <uri>https://zbmath.org/authors/?q=ai:xu.xiuqin</uri> </author> <author> <name>&quot;Lin, Mingwei&quot;</name> <uri>https://zbmath.org/authors/?q=ai:lin.mingwei</uri> </author> <author> <name>&quot;Xu, Zeshui&quot;</name> <uri>https://zbmath.org/authors/?q=ai:xu.zeshui</uri> </author> <content type="text">Summary: Latent factor (LF) model is an efficient method for extracting potential useful information from high-dimensional and incomplete (HDI) matrices. Gradient descent (GD) is a classical learning algorithm and often applied in LF models. However, the standard GD-based LF models rely heavily on learning rate setting, while existing adaptive GD algorithms still update the learning rates corresponding to all parameters uniformly with solidified static rules. This rigidity hinders the model's capacity for parameter-specific learning rate adjustments, thereby prolonging training time and increasing computational expense. Motivated by this discovery, we propose a dynamic single-latent-factor-dependent and self-adaptive intuitionistic fuzzy updating (SLF-SIFU) algorithm and an intuitionistic fuzzy latent factor (IFLF) model. Its main ideas are two fold-ideas: 1) use intuitionistic fuzzy numbers (IFNs) to dynamically model the uncertain relationship between learning rates and gradients during each iteration of each latent factor parameter for guiding learning rate update; 2) decouple the GD algorithm to separate gradient magnitude and direction information, which prevent the extremely large gradient from invalidating the learning rate and causing oscillatory convergence. Experiments on four widely-used HDI datasets show that the IFLF model outperforms state-of-the-art LF models in terms of accuracy and convergence speed with good generalizability.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Covering segments on a line with drones</title> <id>https://zbmath.org/1553.68290</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.68290" /> <author> <name>&quot;Bereg, Sergey&quot;</name> <uri>https://zbmath.org/authors/?q=ai:bereg.sergey-n</uri> </author> <author> <name>&quot;D铆az-B谩帽ez, Jos茅-Miguel&quot;</name> <uri>https://zbmath.org/authors/?q=ai:diaz-banez.jose-miguel</uri> </author> <author> <name>&quot;Kasiuk, Alina&quot;</name> <uri>https://zbmath.org/authors/?q=ai:kasiuk.alina</uri> </author> <author> <name>&quot;P茅rez-Cuti帽o, Miguel-Angel&quot;</name> <uri>https://zbmath.org/authors/?q=ai:perez-cutino.miguel-angel</uri> </author> <author> <name>&quot;Rodr铆guez, Fabio&quot;</name> <uri>https://zbmath.org/authors/?q=ai:rodriguez.fabio</uri> </author> <content type="text">Summary: Covering a set of segments in a plane with vehicles of limited autonomy is a problem of practical interest. The limited battery endurance imposes periodical visits to a static base station. Typically, two optimization problems are considered: minimize the number of tours, and minimize the total traveled distance. In a general setting, the problems are NP-hard and in this letter, we study the one-dimensional version. For covering segments on a line, we design efficient solutions for both optimization problems. First, we design a greedy algorithm that is optimal for the first task, and for both tasks when only one segment is considered. Being \(n\) and \(m\) the number of segments and tours of an optimal solution, respectively, our algorithm runs in \(O(m+n)\) time. For the second criterion, our solution is based on Dynamic Programming and runs in \(O(n^2m)\) time.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Tight FPT approximation for constrained \(k\)-center and \(k\)-supplier</title> <id>https://zbmath.org/1553.68297</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.68297" /> <author> <name>&quot;Goyal, Dishant&quot;</name> <uri>https://zbmath.org/authors/?q=ai:goyal.dishant</uri> </author> <author> <name>&quot;Jaiswal, Ragesh&quot;</name> <uri>https://zbmath.org/authors/?q=ai:jaiswal.ragesh</uri> </author> <content type="text">Summary: In this work, we study a range of \textit{constrained} versions of the \textit{k-supplier} and \textit{k-center} problems. In the classical (\textit{unconstrained}) \(k\)-supplier problem, we are given a set of clients \(C\) in a metric space \(\mathcal{X}\), with distance function \(d(., .)\). We are also given a set of feasible facility locations \(L \subseteq \mathcal{X}\). The goal is to open a set \(F\) of \(k\) facilities in \(L\) to minimize the maximum distance of any client to the closest open facility, i.e., minimize, \(\operatorname{cost}(F, C) \equiv \max_{j \in C} \{d(F, j) \}\), where \(d(F, j)\) is the distance of client \(j\) to the closest facility in \(F\). The \(k\)-center problem is a special case of the \(k\)-supplier problem where \(L = C\). We study various constrained versions of the \(k\)-supplier problem such as: \textit{capacitated}, \textit{fault-tolerant}, \(\ell\)-diversity, etc. These problems fall under a broad framework of \textit{constrained clustering}. A unified framework for constrained clustering was proposed by \textit{H. Ding} and \textit{J. Xu} [Algorithmica 82, No. 4, 808--852 (2020; Zbl 1435.68340)] in the context of the \(k\)-median and \(k\)-means objectives. We extend this framework to the \(k\)-supplier and \(k\)-center objectives in this work. This unified framework allows us to obtain results simultaneously for the following constrained versions of the \(k\)-supplier problem: \textit{\(r\)-gather, \(r\)-capacity, balanced, chromatic, fault-tolerant, strongly private, \(\ell\)-diversity, and fair \(k\)-supplier problems, with and without outliers}. We design Fixed-Parameter Tractable (FPT) algorithms for these problems. FPT algorithms have polynomial running time if the parameter under consideration is a constant. This may be relevant even to a practitioner since the parameter \(k\) is a small number in many real clustering scenarios. We obtain the following results: \begin{itemize} \item We give 3 and 2 approximation algorithms for the constrained \(k\)-supplier and \(k\)-center problems, respectively, with \(\mathsf{FPT}\) running time \(k^{O (k)} \cdot n^{O (1)}\), where \(n = | C \cup L |\). Moreover, these approximation guarantees are tight; that is, for any constant \(\varepsilon &gt; 0\), no algorithm can achieve \((3 - \varepsilon)\) and \((2 - \varepsilon)\) approximation guarantees for the constrained \(k\)-supplier and \(k\)-center problems in \(\mathsf{FPT}\) time, assuming \(\mathsf{FPT} \neq \mathsf{W} [2]\). \item We study the constrained clustering problem with outliers. Our algorithm gives 3 and 2 approximation guarantees for the constrained \textit{outlier \(k\)}-supplier and \(k\)-center problems, respectively, with \(\mathsf{FPT}\) running time \((k + m)^{O (k)} \cdot n^{O (1)}\), where \(n = | C \cup L |\) and \(m\) is the number of outliers. \item Our techniques generalise for distance function \(d (., .)^z\). That is, for any positive real number \(z\), if the cost of a client is defined by \(d (., .)^z\) instead of \(d(., .)\), then our algorithm gives \(3^z\) and \(2^z\) approximation guarantees for the constrained \(k\)-supplier and \(k\)-center problems, respectively. \end{itemize}</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Airports and railways with unsplittable demand</title> <id>https://zbmath.org/1553.68298</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.68298" /> <author> <name>&quot;Jowhari, Hossein&quot;</name> <uri>https://zbmath.org/authors/?q=ai:jowhari.hossein</uri> </author> <author> <name>&quot;Nematollahi, Shamisa&quot;</name> <uri>https://zbmath.org/authors/?q=ai:nematollahi.shamisa</uri> </author> <content type="text">Summary: In the problem of airports and railways with unsplittable demand (ARUD), we are given a complete graph \(G=(V,E)\) with weights on the vertices \(a:V\to\mathbb{R}^+\), and the length of the edges \(\ell:V\times V\to\mathbb{R}^+\). Additionally, a positive integer \(k\) serves as the capacity parameter. We are also provided with a function \(b:V\to\mathbb{N}\) that defines a non-zero demand for each city. The goal is to compute a spanning forest \(R\) of \(G\) and a subset \(A\subseteq V\) of minimum cost such that each component in \(R\) has one open facility and the total demand in each component is at most \(k\) (the capacity constraint). The cost of the solution \((A,R)\) is defined as \(\sum_{v\in A}a(v)+\sum_{e\in E(R)} \ell(e)\). This problem is a generalization of the Airport and Railways (AR) problem introduced by \textit{A. Adamaszek} et al. [LIPIcs -- Leibniz Int. Proc. Inform. 47, Article 6, 14 p. (2016; Zbl 1388.68298)]. In Adamaszek et al. version, each vertex has a unit demand. This paper presents a bi-criteria approximation algorithm for the metric ARUD problem in the sense that the algorithm is allowed to exceed the capacity constraints by \(O(k)\) while the cost of the solution is compared with the cost of an optimal solution that does not violate the capacity constraint. Our approach builds upon an existing approximation algorithm for the metric AR problem, developed by \textit{A. Adamaszek} et al. [LIPIcs -- Leibniz Int. Proc. Inform. 96, Article 5, 13 p. (2018; Zbl 1487.68254)], and further leverages the well-known rounding algorithm of Shmoys and Tardos for the Generalized Assignment Problem (GAP). Assuming the total demand is polynomially bounded in the number of vertices, our algorithm runs in polynomial time. We also show that it is NP-hard to find an approximate solution for ARUD within any factor without violating the capacity constraints. This is the case even when each demand is polynomially bounded in the number of vertices. Furthermore, we determine the complexity of ARUD for some fixed values of \(k\).</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Approximation schemes for min-sum \(k\)-clustering</title> <id>https://zbmath.org/1553.68299</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.68299" /> <author> <name>&quot;Naderi, Ismail&quot;</name> <uri>https://zbmath.org/authors/?q=ai:naderi.ismail</uri> </author> <author> <name>&quot;Rezapour, Mohsen&quot;</name> <uri>https://zbmath.org/authors/?q=ai:rezapour.mohsen</uri> </author> <author> <name>&quot;Salavatipour, Mohammad R.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:salavatipour.mohammad-r</uri> </author> <content type="text">Summary: We consider the Min-Sum \(k\)-Clustering (\(k\)-MSC) problem. Given a set of points in a metric which is represented by an edge-weighted graph \(G=(V, E)\) and a parameter \(k\), the goal is to partition the points \(V\) into \(k\) clusters such that the sum of distances between all pairs of the points within the same cluster is minimized.\par The \(k\)-MSC problem is known to be APX-hard on general metrics. The best known approximation algorithms for the problem obtained by \textit{B. Behsaz} et al. [Algorithmica 81, No. 3, 1006--1030 (2019; Zbl 1418.68239)] achieve an approximation ratio of \(O(\log|V|)\) in polynomial time for general metrics and an approximation ratio \(2+\varepsilon\) in quasi-polynomial time for metrics with bounded doubling dimension. No approximation schemes for \(k\)-MSC (when \(k\) is part of the input) is known for any non-trivial metrics prior to our work. In fact, most of the previous works rely on the simple fact that there is a 2-approximate reduction from \(k\)-MSC to the balanced \(k\)-median problem and design approximation algorithms for the latter to obtain an approximation for \(k\)-MSC.\par In this paper, we obtain the first Quasi-Polynomial Time Approximation Schemes (QPTAS) for the problem on metrics induced by graphs of bounded treewidth, graphs of bounded highway dimension, graphs of bounded doubling dimensions (including fixed dimensional Euclidean metrics), and planar and minor-free graphs. We bypass the barrier of 2 for \(k\)-MSC by introducing a new clustering problem, which we call min-hub clustering, which is a generalization of balanced \(k\)-median and is a trade off between center-based clustering problems (such as balanced \(k\)-median) and pair-wise clustering (such as Min-Sum \(k\)-clustering). We then show how one can find approximation schemes for Min-hub clustering on certain classes of metrics. For the entire collection see [Zbl 1520.68006].</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Approximation schemes for Min-Sum \(k\)-Clustering</title> <id>https://zbmath.org/1553.68300</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.68300" /> <author> <name>&quot;Naderi, Ismail&quot;</name> <uri>https://zbmath.org/authors/?q=ai:naderi.ismail</uri> </author> <author> <name>&quot;Rezapour, Mohsen&quot;</name> <uri>https://zbmath.org/authors/?q=ai:rezapour.mohsen</uri> </author> <author> <name>&quot;Salavatipour, Mohammad R.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:salavatipour.mohammad-r</uri> </author> <content type="text">Summary: We consider the Min-Sum \(k\)-Clustering (\(k\)-MSC) problem. Given a set of points in a metric which is represented by an edge-weighted graph \(G=(V,E)\) and a parameter \(k\), the goal is to partition the points \(V\) into \(k\) clusters such that the sum of distances between all pairs of the points within the same cluster is minimized. The \(k\)-MSC problem is known to be APX-hard on general metrics. The best known approximation algorithms for the problem obtained by \textit{B. Behsaz} et al. [Algorithmica 81, No. 3, 1006--1030 (2019; Zbl 1418.68239)] achieve an approximation ratio of \(O(\log |V|)\) in polynomial time for general metrics and an approximation ratio \(2+\epsilon\) in quasi-polynomial time for metrics with bounded doubling dimension. No approximation schemes for \(k\)-MSC (when \(k\) is part of the input) is known for any non-trivial metrics prior to our work. In fact, most of the previous works rely on the simple fact that there is a 2-approximate reduction from \(k\)-MSC to the balanced \(k\)-median problem and design approximation algorithms for the latter to obtain an approximation for \(k\)-MSC. In this paper, we obtain the first Quasi-Polynomial Time Approximation Schemes (QPTAS) for the problem on metrics induced by graphs of bounded treewidth, graphs of bounded highway dimension, graphs of bounded doubling dimensions (including fixed dimensional Euclidean metrics), and planar and minor-free graphs. We bypass the barrier of 2 for \(k\)-MSC by introducing a new clustering problem, which we call min-hub clustering, which is a generalization of balanced \(k\)-median and is a trade off between center-based clustering problems (such as balanced \(k\)-median) and pair-wise clustering (such as Min-Sum \(k\)-clustering). We then show how one can find approximation schemes for Min-hub clustering on certain classes of metrics.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">A study on the effects of normalized TSP features for automated algorithm selection</title> <id>https://zbmath.org/1553.68308</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.68308" /> <author> <name>&quot;Heins, Jonathan&quot;</name> <uri>https://zbmath.org/authors/?q=ai:heins.jonathan</uri> </author> <author> <name>&quot;Bossek, Jakob&quot;</name> <uri>https://zbmath.org/authors/?q=ai:bossek.jakob</uri> </author> <author> <name>&quot;Pohl, Janina&quot;</name> <uri>https://zbmath.org/authors/?q=ai:pohl.janina-susanne</uri> </author> <author> <name>&quot;Seiler, Moritz&quot;</name> <uri>https://zbmath.org/authors/?q=ai:seiler.moritz</uri> </author> <author> <name>&quot;Trautmann, Heike&quot;</name> <uri>https://zbmath.org/authors/?q=ai:trautmann.heike</uri> </author> <author> <name>&quot;Kerschke, Pascal&quot;</name> <uri>https://zbmath.org/authors/?q=ai:kerschke.pascal</uri> </author> <content type="text">Summary: Classic automated algorithm selection (AS) for (combinatorial) optimization problems heavily relies on so-called instance features, i.e., numerical characteristics of the problem at hand ideally extracted with computationally low-demanding routines. For the traveling salesperson problem (TSP) a plethora of features have been suggested. Most of these features are, if at all, only normalized imprecisely raising the issue of feature values being strongly affected by the instance size. Such artifacts may have detrimental effects on algorithm selection models. We propose a normalization for two feature groups which stood out in multiple AS studies on the TSP: (a) features based on a minimum spanning tree (MST) and (b) nearest neighbor relationships of the input instance. To this end we theoretically derive minimum and maximum values for properties of MSTs and \(k\)-nearest neighbor graphs (NNG) of Euclidean graphs. We analyze the differences in feature space between normalized versions of these features and their unnormalized counterparts. Our empirical investigations on various TSP benchmark sets point out that the feature scaling succeeds in eliminating the effect of the instance size. A proof-of-concept AS-study shows promising results: models trained with normalized features tend to outperform those trained with the respective vanilla features.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">How majority-vote crossover and estimation-of-distribution algorithms cope with fitness valleys</title> <id>https://zbmath.org/1553.68309</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.68309" /> <author> <name>&quot;Witt, Carsten&quot;</name> <uri>https://zbmath.org/authors/?q=ai:witt.carsten</uri> </author> <content type="text">Summary: The benefits of using crossover in crossing fitness gaps have been studied extensively in evolutionary computation. Recent runtime results show that majority-vote crossover is particularly efficient at optimizing the well-known \textsc{Jump} benchmark function that includes a fitness gap next to the global optimum. Also estimation-of-distribution algorithms (EDAs), which use an implicit crossover, are much more efficient on \textsc{Jump} than typical mutation-based algorithms. However, the allowed gap size for polynomial runtimes with EDAs is at most logarithmic in the problem dimension \(n\). In this paper, we investigate variants of the \textsc{Jump} function where the gap is shifted and appears in the middle of the typical search trajectory. Such gaps can still be overcome efficiently in time \(O(n \log n)\) by majority-vote crossover and an estimation-of-distribution algorithm, even for gap sizes almost \(\sqrt{n}\). However, if the global optimum is located in the gap instead of the usual all-ones string, majority-vote crossover would nevertheless approach the all-ones string and be highly inefficient. In sharp contrast, an EDA can still find such a shifted optimum efficiently. Thanks to a general property called \textit{fair sampling}, the EDA will with high probability sample from almost every fitness level of the function, including levels in the gap, and sample the global optimum even though the overall search trajectory points towards the all-ones string. Finally, we derive limits on the gap size allowing efficient runtimes for the EDA.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Exploiting potentialities for space-based quantum communication network: downlink quantum key distribution modelling and scheduling analysis</title> <id>https://zbmath.org/1553.81070</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.81070" /> <author> <name>&quot;Wang, Xingyu&quot;</name> <uri>https://zbmath.org/authors/?q=ai:wang.xingyu</uri> </author> <author> <name>&quot;Li, Taoyong&quot;</name> <uri>https://zbmath.org/authors/?q=ai:li.taoyong</uri> </author> <author> <name>&quot;Dong, Chen&quot;</name> <uri>https://zbmath.org/authors/?q=ai:dong.chen</uri> </author> <author> <name>&quot;Wei, Jiahua&quot;</name> <uri>https://zbmath.org/authors/?q=ai:wei.jiahua</uri> </author> <author> <name>&quot;Yu, Huicun&quot;</name> <uri>https://zbmath.org/authors/?q=ai:yu.huicun</uri> </author> <author> <name>&quot;Zhao, Shanghong&quot;</name> <uri>https://zbmath.org/authors/?q=ai:zhao.shanghong</uri> </author> <author> <name>&quot;Shi, Lei&quot;</name> <uri>https://zbmath.org/authors/?q=ai:shi.lei.2</uri> </author> <content type="text">Summary: The goal of the space-based quantum network is to form the backbone of the quantum internet for long-distance secure data transfer, networked distributed quantum information processing, and other applications. Consider that the quantum network evolved from a recent form where a satellite performs a sequence of satellite-to-ground quantum key distribution (SatQKD) missions that allow any two ground nodes to have the symmetric encryption keys, we here develop a framework for the SatQKD downlink modelling and scheduling analysis. Incorporated with the orbital calculation and the meteorological data to downlink SatQKD modelling, the dynamic characteristics of the satellite-to-ground optical transmission could be simulated. Our work shows that the satellite downlink scheduling allows for the possibility to consider different strategies for SatQKD missions such as extending connection for distant ground nodes, prioritized delivery and promoting keys utilization, which may guide design and analysis of future missions for future satellite application. {{\copyright} 2023 The Author(s). Published by IOP Publishing Ltd on behalf of the Institute of Physics and Deutsche Physikalische Gesellschaft}</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Approximation and scalarization in multiobjective optimization</title> <id>https://zbmath.org/1553.90001</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90001" /> <author> <name>&quot;Helfrich, Stephan&quot;</name> <uri>https://zbmath.org/authors/?q=ai:helfrich.stephan</uri> </author> <content type="text">Summary: In multiobjective optimization problems, where multiple objectives are to be optimized simultaneously, unique optimal solutions usually do not exist. Instead, one is interested in the set of all nondominated images that reflect each possible trade-off of the individual objectives, and at least one efficient solution associated to each nondominated image. In cases in that the number of nondominated images is enormous, computing approximation sets is a preferable and frequently chosen alternative. Such sets contain, for each image, a solution whose image is as good up to a multiplicative constant. Scalarizations, which transform the multiobjective optimization problem into solvable or approximable single-objective optimization problems by means of additional parameters, are an important building block to obtain both exact and approximate solution sets. This thesis deals with a systematic study of scalarizations, the structure of their parameter sets as well as their interrelations to efficient and approximate solutions.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Approximation in deterministic and stochastic machine scheduling</title> <id>https://zbmath.org/1553.90002</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90002" /> <author> <name>&quot;J盲ger, Sven Joachim&quot;</name> <uri>https://zbmath.org/authors/?q=ai:jager.sven-joachim</uri> </author> <content type="text">Summary: Classical combinatorial optimization is based on the assumption that for a given problem instance all problem data are available at the beginning (offline optimization). However, many optimization problems in practice require that some decisions be made before all information about the problem is completely known. In online optimization it is assumed that the data become known over time, whereas in stochastic optimization, unknown problem parameters are assumed to be distributed according to known probability distributions. In this thesis algorithms for scheduling problems under the three assumptions described above are developed and analyzed. In the considered problems the task is to create a schedule for the processing of a set of jobs on machines running in parallel. The jobs have different processing times and priorities. The goal is to minimize the sum of completion times of all jobs, weighted by the job priorities. In some problems there are additional requirements on feasible schedules. We restrict ourselves to algorithms that can be executed in polynomial time. Since all investigated offline optimization problems are NP-hard, under this constraint the algorithms cannot always yield an optimal schedule. Therefore, for such problems we concentrate on approximation algorithms that compute in polynomial time a schedule with a provable performance guarantee. A similar approach is adopted in the two models with uncertainty. In the developed online algorithms we bound the relative deviation of the achieved objective value from the optimum with perfect information. In stochastic scheduling we are interested in upper bounds for the ratio of the expected objective value resulting from the considered policy to the expected objective value under an optimal policy. A well-known rule for non-preemptive scheduling of jobs on identical machines in the presence of complete information is to start at any moment when a machine is free a job with maximum quotient of its priority divided by its processing time. We refine the known performance guarantee of this rule for the case that the number of machines is fixed. In addition, we transfer the rule to the stochastic scheduling problem, in which the processing times are random. This yields a policy with a performance guarantee depending on the coefficients of variation of the processing times. This performance guarantee is significantly better than the best previously known guarantee for the same policy from 1999. For instances with bounded coefficients of variation no efficiently computable policy with a better performance guarantee is known for this problem. The use of an efficiently solvable linear relaxation of the investigated problem is a common method in the design of approximation algorithms. The solution is employed for the construction of a good schedule for the initial problem. In this step randomness can be incorporated. Instead of comparing the objective value of the constructed schedule directly with that of the unknown optimal schedule, we bound the maximum possible ratio of the obtained objective value to the optimum value of the relaxation. In this dissertation this technique is applied in both an approximation algorithm for deterministic scheduling and an approximative stochastic scheduling policy. Finally, we conceive algorithms and policies for different deterministic and stochastic scheduling problems, respectively, where the jobs appear gradually and are unknown beforehand. Almost all linear relaxations cannot be solved without knowing the entire problem instance. For the preemptive relaxation employed in this thesis, however, an optimal solution can be constructed by means of a simple rule while the jobs are being processed. A further method applied is the assignment of jobs to machines using a greedy algorithm. Although the used greedy algorithms do not resort to a solution to a linear relaxation, the ratio of the objective value attained by the algorithm to the optimum objective value of such a relaxation can be bounded. To this end, a feasible dual solution is constructed, depending on the steps performed by the algorithm. A multiple of its objective value is an upper bound for the objective value of the constructed schedule. Using these techniques, we develop an online algorithm for computing preemptive schedules on unrelated machines with an improved constant performance guarantee. Furthermore, we enhance a recently published online algorithm for preemptively scheduling jobs with precedence constraints on identical machines, which additionally relies on network flow techniques. Finally, we design non-preemptive stochastic online scheduling policies for a single machine as well as for unrelated parallel machines. For these we obtain improved performance guarantees depending on two different parameters of the probability distributions.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Exact mixed-integer programming</title> <id>https://zbmath.org/1553.90003</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90003" /> <author> <name>&quot;Jarck, Kati&quot;</name> <uri>https://zbmath.org/authors/?q=ai:jarck.kati</uri> </author> <content type="text">Summary: In this thesis, we develop and implement an efficient algorithm that can exactly solve instances of the mixed-integer programming problem that are given by rational data. For a feasible instance, a truly optimal solution will be computed; for an infeasible instance, a provably correct infeasibility certificate will be issued. Our exact mixed-integer programming solver is part of the constraint integer programming software SCIP, which is developed and maintained at the Zuse Institute Berlin. Mixed-integer programming solvers have experienced tremendous progress in the last decades, while almost no attention has been paid to exact computations. Most mixed-integer programming solvers, in particular, the state-of-the-art ones CPLEX, Gurobi, MOSEK, SCIP, and Xpress, are numerical solvers, i.e., they use finite-precision binary floating-point arithmetic, which is a compromise between speed and correctness. Such solvers cannot provide any guarantee of correct results. Due to a number of reasons, for many industrial applications near optimal solutions are sufficient. This situation changes fundamentally when mixed-integer programming is used to establish theoretical results, when feasibility questions are considered, and when serious legal and financial consequences may result from incorrect solutions. To underline the necessity of exact solvers, this thesis, first, analyzes how strong the error-proneness inherent in finite-precision binary floating-point systems influences the results of numerical mixed-integer programming solvers. We employ two important theoretical concepts from numerical mathematics therefor: condition of a problem instance and stability of an algorithm. In addition, we test the stability of SCIP on the Miplib benchmarking libraries, discuss how to identify instances of the mixed-integer programming problem on which current solvers face numerical difficulties, and build the first large test set of numerically difficult instances. This thesis, then, shows that it is possible to solve instances of the mixed-integer programming problem exactly over the rational numbers without introducing a large overhead in running time compared to solving them numerically. This applies to numerically easy as well as to numerically difficult instances. While earlier attempts in that direction showed slow-downs of orders of magnitudes, we provide the first efficient exact branch-and-bound solver. As our focus is exclusively on the branch-and-bound procedure, we compared the exact solver against a numerical solver restricted to pure branch-and-bound. The key ingredients of the exact solver are as follows. The first one is the new hybrid rational/safe floating-point approach. The second one is to dynamically choose the fastest of several safe dual bounding methods depending on the structure of the instance. The third one is the sophisticated integration of iterative refinement for linear programming, a new technique to improve the stability of numerical linear programming solvers, into the solution process of the exact mixed-integer programming solver.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">On the impact of bounded minors in integer programming</title> <id>https://zbmath.org/1553.90004</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90004" /> <author> <name>&quot;Kuhlmann, Stefan&quot;</name> <uri>https://zbmath.org/authors/?q=ai:kuhlmann.stefan</uri> </author> <content type="text">(no abstract)</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Optimization of stationary expansion planning and transient network control by mixed-integer nonlinear programming</title> <id>https://zbmath.org/1553.90005</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90005" /> <author> <name>&quot;Lenz, Ralf&quot;</name> <uri>https://zbmath.org/authors/?q=ai:lenz.ralf</uri> </author> <content type="text">(no abstract)</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Tighter relaxations in mixed-integer nonlinear programming</title> <id>https://zbmath.org/1553.90006</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90006" /> <author> <name>&quot;M眉ller, Benjamin&quot;</name> <uri>https://zbmath.org/authors/?q=ai:muller.benjamin</uri> </author> <content type="text">Summary: Mixed-integer nonlinear programming (MINLP) is one of the most important classes of mathematical optimization problems that combines difficulties from mixed-integer linear programming and nonlinear programming, namely optimizing over a set that is described by integrality, linear, and nonlinear restrictions. This class of optimization problems is essential when constructing accurate models of real-world applications such as energy production and distribution, logistics, engineering design, manufacturing, and fields in chemical and biological sciences. To the best of our knowledge, all state-of-the-art algorithms for solving nonconvex MINLPs to global optimality are based on branch and bound. The performance of these algorithms mainly depends on tight relaxations of a MINLP that are refined throughout a tree search. For this reason, the contribution of this thesis is to present new methods to construct and strengthen relaxations for mixed-integer nonlinear programs. One application of MINLP is the recursive circle packing problem (RCPP), which arises in the tube industry when packing pipes into rectangular containers. Solving a compact formulation for the RCPP is entirely out of reach for state-of-the-art MINLP solvers because relaxations for this problem are known to be weak. To construct significantly tighter relaxations, we present an exact reformulation of the RCPP that is based on a Dantzig-Wolfe decomposition of a nonconvex MINLP formulation. We use column generation techniques to design an algorithm that solves the continuous relaxation of the reformulation to global optimality. This relaxation is substantially tighter than relaxations for a compact MINLP formulation, which enables us to solve 287 out of 800 instances to global optimality that could not be solved so far. The most fundamental ingredient in MINLP solvers is the well-known McCormick relaxation for a product of two variables x and y over a box-constrained domain. This relaxation is far from being tight if the feasible region of a MINLP and its convexification projected in the x-y-space is a strict subset of the box. We develop an algorithm that solves a sequence of linear programs to compute globally valid inequalities on x and y in a similar fashion as optimization-based bound tightening. These valid inequalities enable us to exploit polyhedral results from the literature to tighten the classic McCormick relaxation. Additionally, we present two novel propagation algorithms that compute stronger bounds for \(x\), \(y\), and \(xy\). The resulting implementation reduces the average running time by 36\% on difficult MINLPs. Due to both theoretical and practical considerations, relaxations of MINLPs are usually required to be convex. Nonetheless, current optimization solvers improved tremendously during the last decades and are nowadays able to solve problems with a moderate presence of nonconvexities. This progress opens the door for the use of potentially tighter relaxations that contain only a few nonconvexities. Such a nonconvex relaxation can be obtained via the aggregation of constraints: a surrogate relaxation. These relaxations were actively studied for linear integer programs in the 70s and 80s, but they have been scarcely considered since. We revisit these relaxations in a MINLP setting and show the computational benefits and challenges they can have. Additionally, we study a generalization of such relaxation that allows for multiple aggregations simultaneously and present the first algorithm in the literature that is capable of computing the best set of aggregations. We propose a multitude of computational enhancements for improving its practical performance and evaluate the algorithm's ability to generate tight relaxations through extensive computational experiments. Our results show that we are able to improve the best known bounds for unsolved instances and decrease the average gap by a factor of two on difficult instances. Finally, we present the concept of variable holes for nonconvex MINLPs. Due to the presence of nonconvex nonlinear constraints, the set of feasible assignments of a variable can be disconnected. The resulting forbidden regions are called variable holes and can be viewed as a generalization of integrality restrictions. By exploiting these holes, it is possible to strengthen the relaxation of a MINLP by applying techniques that have been exclusively developed for integer variables to continuous variables. Unfortunately, computing a variable hole is in general NP-hard. Still, for many MINLPs, it is enough to consider relaxations that are described by few constraints to detect variable holes. Based on this observation, we develop three algorithms that are capable of computing variable holes for practical instances. Our computational study shows that integrating variable holes into pseudo cost branching rules decreases the average running time by 62\% on affected instances.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Faster algorithms for Steiner tree and related problems: from theory to practice</title> <id>https://zbmath.org/1553.90007</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90007" /> <author> <name>&quot;Rehfeldt, Daniel Markus&quot;</name> <uri>https://zbmath.org/authors/?q=ai:rehfeldt.daniel-markus</uri> </author> <content type="text">Summary: The Steiner tree problem in graphs (SPG) is one of the most studied problems in combinatorial optimization. Part of its theoretical appeal might be attributed to the fact that the SPG generalizes two other classic optimization problems: Shortest paths, and minimum spanning trees. On the practical side, many applications can be modeled as SPG or closely related problems. The SPG has seen impressive theoretical advancements in the last decade. However, the state of the art in (practical) exact SPG solution, set in a series of milestone papers by Polzin and Vahdati Daneshmand, has remained largely unchallenged for almost 20 years. While the DIMACS Challenge 2014 and the PACE Challenge 2018 brought renewed interest into the exact solution of SPGs, even the best new solvers fall far short of reaching the state of the art. This thesis seeks to once again advance exact SPG solution. Since many practical applications are not modeled as pure SPGs, but rather as closely related problems, this thesis also aims to combine SPG advancements with improvement in the exact solution of such related problems. Initially, we establish a broad theoretical basis to guide the subsequent algorithmic developments. In this way, we provide various new theoretical results for SPG and well-known relatives such as the maximum-weight connected subgraph problem. These results include the strength of linear programming relaxations, polyhedral descriptions, and complexity results. We go on to introduce many algorithmic components such as reduction techniques, cutting planes, graph transformations, and heuristics-both for SPG and related problems. Many of these methods and techniques are provably stronger than previous results from the literature. For example, we introduce a new reduction concept that is strictly stronger than the well-known and widely used bottleneck Steiner distance. We also provide theoretical analyses (e.g. concerning complexity) of the new algorithms. The individual components are combined in an exact branch-and-cut algorithm. Notably, all problem classes can be handled by a single branch-and-cut kernel. As a result, we obtain an exact solver for SPG and 14 related problems. The new solver is on each of the 15 problem classes faster than all other (problem-specific) solvers from the literature, often by orders of magnitude. In particular, the solver outperforms the long-reigning state-of-the-art solver for SPG. Finally, many benchmark instances from the literature for several problem classes can be solved for the first time to optimality-some containing millions of edges. These problem classes include the SPG, the prize-collecting Steiner tree problem, the maximum-weight connected subgraph problem, and the Euclidean Steiner tree problem.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Local evaluation of policies for discounted Markov decision roblems</title> <id>https://zbmath.org/1553.90008</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90008" /> <author> <name>&quot;Tuchscherer, Andreas&quot;</name> <uri>https://zbmath.org/authors/?q=ai:tuchscherer.andreas</uri> </author> <content type="text">Summary: Providing realistic performance indicators of online algorithms for a given online optimization problem is a difficult task in general. Due to significant drawbacks of other concepts like competitive analysis, Markov decision problems (MDPs) may yield an attractive alternative whenever reasonable stochastic information about future requests is available. However, the number of states in MDPs emerging from real applications is usually exponential in the original input parameters. Therefore, the standard methods for analyzing policies, i.e., online algorithms in our context, are infeasible. In this thesis we propose a new computational tool to evaluate the behavior of policies for discounted MDPs locally, i.e., depending on a particular initial state. The method is based on a column generation algorithm for approximating the total expected discounted cost of an unknown optimal policy, a concrete policy, or a single action (which assumes actions at other states to be made according to an optimal policy). The algorithm determines an $\varepsilon$-approximation by inspecting only relatively small local parts of the total state space. We prove that the number of states required for providing the approximation is independent of the total number of states, which underlines the practicability of the algorithm. The approximations obtained by our algorithm are typically much better than the theoretical bounds obtained by other approaches. We investigate the pricing problem and the structure of the linear programs encountered in the column generation. Moreover, we propose and analyze different extensions of the basic algorithm in order to achieve good approximations fast. The potential of our analysis tool is exemplified for discounted MDPs emerging from different online optimization problems, namely online bin coloring, online target date assignment, and online elevator control. The results of the experiments are quite encouraging: our method is mostly capable to provide performance indicators for online algorithms that much better reflect observations made in simulations than competitive analysis does. Moreover, the analysis allows to reveal weaknesses of the considered online algorithms. This way, we developed a new online algorithm for the online bin coloring problem that outperforms existing ones in our analyses and simulations.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Cutting plane selection for mixed-integer linear programming</title> <id>https://zbmath.org/1553.90009</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90009" /> <author> <name>&quot;Turner, Mark Ruben&quot;</name> <uri>https://zbmath.org/authors/?q=ai:turner.mark-ruben</uri> </author> <content type="text">Summary: Mixed-Integer Linear Programming (MILP) is a ubiquitous and practical modelling paradigm that is essential for optimising a broad range of real-world systems. The backbone of all modern MILP solvers is the branch-and-cut algorithm, which is a hybrid of the branch-and-bound and cutting planes algorithms. Cutting planes (cuts) are linear inequalities that tighten the relaxation of a MILP. While a lot of research has gone into deriving valid cuts for MILPs, less emphasis has been put on determining which cuts to select. Cuts in general are generated in rounds, and a subset of the generated cuts must be added to the relaxation. The decision on which subset of cuts to add is called cut selection. This is a crucial task since adding too many cuts makes the relaxation large and slow to optimise over. Conversely, adding too few cuts results in an insufficiently tightened relaxation, and more relaxations need to be enumerated. To further emphasise the difficulty, the effectiveness of an applied cut is both dependent on the other applied cuts, and the state of the MILP solver. In this thesis, we present theoretical results on the importance and difficulty of cut selection, as well as practical results that use cut selection to improve general MILP solver performance. Improving general MILP solver performance is of great importance for practitioners and has many runoff effects. Reducing the solve time of currently solved systems can directly improve efficiency within the application area. In addition, improved performance enables larger systems to be modelled and optimised, and MILP to be used in areas where it was previously impractical due to time restrictions. Each chapter of this thesis corresponds to a publication on cut selection, where the contributions of this thesis can naturally be divided into four components. The first two components are motivated by instance-dependent performance. In practice, for each subroutine, including cut selection, MILP solvers have adjustable parameters with hard-coded default values. It is ultimately unrealistic to expect these default values to perform well for every instance. Rather, it would be ideal if the parameters were dependent on the given instance. To show this motivation is well founded, we first introduce a family of parametric MILP instances and cuts to showcase worst-case performance of cut selection for any fixed parameter value. We then introduce a graph neural network architecture and reinforcement learning framework for learning instance-dependent cut scoring parameters. In the following component, we formalise language for determining if a cut has theoretical usefulness from a polyhedral point of view in relation to other cuts. In addition, to overcome issues of infeasible projections and dual degeneracy, we introduce analytic center based distance measures. We then construct a lightweight multi-output regression model that predicts relative solver performance of an instance for a set of distance measures. The final two components are motivated by general MILP solver improvement via cut selection. Such improvement was shown to be possible, albeit difficult to achieve, by the first half of this thesis. We relate branch-and-bound and cuts through their underlying disjunctions. Using a history of previously computed Gomory mixed-integer cuts, we reduce the solve time of SCIP over the 67\% of affected MIPLIB 2017 instances by 4\%. In the final component, we introduce new cut scoring measures and filtering methods based on information from other MILP solving processes. The new cut selection techniques reduce the solve time of SCIP over the 97\% of affected MIPLIB 2017 instances by 5\%.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">The power of recourse in online optimization. Robust solutions for scheduling, matroid and MST problems</title> <id>https://zbmath.org/1553.90010</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90010" /> <author> <name>&quot;Verschae Tannenbaum, Jos茅 Claudio&quot;</name> <uri>https://zbmath.org/authors/?q=ai:verschae-tannenbaum.jose-claudio</uri> </author> <content type="text">Summary: Uncertainty on the input data is one of the most challenging problems in optimization. Two well known paradigms of optimization under lack of information are the online and the multi-stage robust models. In online problems the information is revealed piece by piece in several stages, and the optimizer must take irrevocable decisions when a new piece of information is revealed. The quality of algorithms is measured with the competitive factor, that compares solutions to the offline optimum in the worst case. In multi-stage robust problems the input is also revealed in several stages, and the optimizer can adjust the solution to the input data by the use of recourse. The objective is to choose the recourse optimally. Despite their usefulness in several situations, both models have often be subject to criticism: the bounds obtained in online problems can be over conservative, and multi-stage robust problems suffer from a excessively high computational complexity. In this thesis, we study a relaxed online framework where a limited amount of recourse is permitted. For several relevant problems, we can show that a very limited amount of recourse allows to obtain near-optimal solutions. For these problems, our model cope with the inherent problems of the two paradigms discussed above. We propose two general models for bounding the recourse allowed. In the first one, we bound the amount of recourse independently in each stage. The second one bounds the recourse in an amortized manner. Both models find applications in different areas. Three different problems are considered in this thesis. First we study online machine scheduling problems, where jobs arrive one by one. Whenever a job appears we must assign it to some machine. The amount of recourse is controlled with the migration factor, that is, the worst case ratio between the total processing time of jobs migrated and the size of the arriving job. The amortized variant of this measure is the reassignment factor. We study a general class of objective functions in this framework, that allows us to model the prominent minimum makespan problem and the machine covering problem, among many others. We show that constant reassignment factors are enough to maintain near optimal solutions in every stage. On the other hand, the migration factor model does not allow such result. Secondly, we study matroid intersection problems. Matroids are combinatorial structures that capture fundamental properties of several optimization problems. We study an online variant where batches of elements are revealed in every stage. In each stage we are allowed to insert to the solution a given number of elements. In this framework, comparing the constructed solutions to the offline optimum give unbounded competitive ratios. Therefore we compare our algorithms against the best sequence of solutions that have our same recourse power. Our main result in an \(O(c^2)\)-competitive algorithm for the intersection of c matroids. Last, we consider the minimum spanning tree problem. In our online setting, nodes of a metric graph are revealed one by one. In every stage we must construct a spanning tree of small cost. The recourse is bounded by limiting the number of edges \(k\) to insert in each stage. With an amortized version of this idea, we can obtain near optimal solutions with constant k. This contrasts the non-amortized setting where the best possible competitive guarantee is 2. Also, we show a conjecture that would imply the existence of a constant competitive algorithm in the non-amortized setting. Moreover, we show that all these results transfer to an online version of the traveling salesmen problem by increasing by a constant competitive ratio and \(k\).</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Effects of memory on inventory control and pricing policy for imperfect production with rework process</title> <id>https://zbmath.org/1553.90011</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90011" /> <author> <name>&quot;Jain, Madhu&quot;</name> <uri>https://zbmath.org/authors/?q=ai:jain.madhu</uri> </author> <author> <name>&quot;Indoria, Harsh&quot;</name> <uri>https://zbmath.org/authors/?q=ai:indoria.harsh</uri> </author> <author> <name>&quot;Chaudhary, Aditya&quot;</name> <uri>https://zbmath.org/authors/?q=ai:chaudhary.aditya</uri> </author> <author> <name>&quot;Singh, Praveendra&quot;</name> <uri>https://zbmath.org/authors/?q=ai:singh.praveendra</uri> </author> <content type="text">Summary: Fractional calculus is a pertinent way to study the memory effect in an inventory model for investigating its dynamical behavior. Since inventory management is a memory-dependent process, fractional calculus approach may be employed to discover some fruitful insights and can help to gain more profit. In realistic scenarios, the manufacturing process cannot be perfect, and it delivers some faulty units due to many inevitable reasons. In literature, an imperfect production inventory problem under the memory effect has not been studied. Our study aims to investigate the memory effect on a production inventory system. In this article, a fractional order inventory control problem is formulated by considering an imperfect manufacturing process and price-sensitive demand. The faulty units are repaired through a rework process. Caputo fractional derivatives and integrals are used to consider the memory effect. Due to the nonlinear cost elements in the formulated problem, optimal pricing and production policies are investigated by using a quasi-Newton optimization algorithm and particle swarm optimization approach. The managerial implications of the proposed study are discussed with the help of numerical illustrations. The numerical outcomes suggest that consideration of memory in the inventory system boosts the profitability of the firm.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Efficient demand management for the on-time arrival problem: a convexified multi-objective approach assuming macroscopic traffic dynamics</title> <id>https://zbmath.org/1553.90012</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90012" /> <author> <name>&quot;Menelaou, C.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:menelaou.charalambos</uri> </author> <author> <name>&quot;Timotheou, S.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:timotheou.stelios</uri> </author> <author> <name>&quot;Kolios, P.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:kolios.p</uri> </author> <author> <name>&quot;Panayiotou, C. G.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:panayiotou.christos-g</uri> </author> <content type="text">Summary: This work proposes a novel solution approach to address the on-time arrival (OTA) problem, considering macroscopic traffic dynamics. In this context, all drivers who intend to use the road infrastructure are required to communicate their origin-destination pair and desired arrival time to a central scheduler prior to starting their trip. In response, the scheduler assigns a departure time and a multi-regional route to each driver to make possible their on-time arrival at the destination. The OTA problem is formulated as a nonconvex, nonlinear, multi-objective optimization problem considering two objective criteria. The first criterion aims at minimizing the travel time of all drivers in the network to prevent congestion, while the second criterion seeks to minimize the discrepancy between the desired and actual arrival time. The proposed formulation is solved efficiently through an approximated convex solution that leverages the normal boundary intersection (NBI) method to efficiently generate a representative sample of the Pareto front. Additionally, two solution methodologies based on ``knee'' solution and the Nash bargaining game is proposed which can be used to select a unique solution across all the Pareto points, that offers a reasonable trade-off between the two objective criteria. Finally, simulation results demonstrate that the proposed solution can significantly reduce congestion while ensuring that most drivers will arrive at their destination on their desired time.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Corrigendum to: ``Bilevel time minimizing transportation problem''</title> <id>https://zbmath.org/1553.90013</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90013" /> <author> <name>&quot;Sonia&quot;</name> <uri>https://zbmath.org/authors/?q=ai:sonia.</uri> </author> <author> <name>&quot;Khandelwal, Ankit&quot;</name> <uri>https://zbmath.org/authors/?q=ai:khandelwal.ankit</uri> </author> <content type="text">Summary: This is a corrigendum to our research paper [ibid. 5, No. 4, 714--723 (2008; Zbl 1152.90344)]. We deeply regret a minor error in the formulation of an intermediate problem solved as part of the algorithm. The intermediate problem, \((TP)_t^T\), used to iteratively generate the prospective solution pairs, was initially modeled as a linear programming problem. But the correct formulation of its objective function now involves a binary function, thus making it an NP-hard problem. The algorithm is no longer polynomially bound as it involves solving a finite number of mixed 0-1 programming problems. The manuscript's original contribution stands correct and there is no change to the structure or the accuracy of the algorithm. The changes required to the original paper, due to this error, are presented in this corrigendum.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Erratum to: ``Edge selections in bilinear dynamic networks''</title> <id>https://zbmath.org/1553.90014</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90014" /> <author> <name>&quot;Castello B. De Oliveira, Arthur&quot;</name> <uri>https://zbmath.org/authors/?q=ai:castello-b-de-oliveira.arthur</uri> </author> <author> <name>&quot;Siami, Milad&quot;</name> <uri>https://zbmath.org/authors/?q=ai:siami.milad</uri> </author> <author> <name>&quot;Sontag, Eduardo D.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:sontag.eduardo-d</uri> </author> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Are the queueing systems in practice random or uncertain? Evidence from online car-hailing data in Beijing</title> <id>https://zbmath.org/1553.90015</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90015" /> <author> <name>&quot;Liu, Yang&quot;</name> <uri>https://zbmath.org/authors/?q=ai:liu.yang.199</uri> </author> <author> <name>&quot;Qin, Zhongfeng&quot;</name> <uri>https://zbmath.org/authors/?q=ai:qin.zhongfeng</uri> </author> <author> <name>&quot;Li, Xiang&quot;</name> <uri>https://zbmath.org/authors/?q=ai:li.xiang.2</uri> </author> <content type="text">Summary: In order to rationally characterize the nondeterministic phenomena in queueing systems, there exist two mathematical systems, one is probability theory concerned with the analysis of random phenomena and the other is uncertainty theory concerned with the analysis of uncertain phenomena. Before using the above two mathematical systems to model the real queueing systems, we often need to face such a question, are the real queueing systems random or uncertain? In order to answer this question, we collect the arriving times of passengers from online car-hailing platform in Beijing, and then analyze the collected data based on stochastic renewal process and uncertain renewal process. Finally, by comparing samples and confidence intervals of the total numbers of passengers arriving on the online car-hailing platform under two mathematical systems, we come to the conclusion that the queueing systems in the real world are uncertain rather than random.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Correction to: ``Flexible layouts for the mixed-model assembly of heterogeneous vehicles''</title> <id>https://zbmath.org/1553.90016</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90016" /> <author> <name>&quot;Hottenrott, Andreas&quot;</name> <uri>https://zbmath.org/authors/?q=ai:hottenrott.andreas</uri> </author> <author> <name>&quot;Grunow, Martin&quot;</name> <uri>https://zbmath.org/authors/?q=ai:grunow.martin</uri> </author> <content type="text">Correction to the authors' paper [ibid. 41, No. 4, 943--979 (2019; Zbl 1527.90091)].</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Streaming approximation scheme for minimizing total completion time on parallel machines subject to varying processing capacity</title> <id>https://zbmath.org/1553.90017</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90017" /> <author> <name>&quot;Fu, Bin&quot;</name> <uri>https://zbmath.org/authors/?q=ai:fu.bin</uri> </author> <author> <name>&quot;Huo, Yumei&quot;</name> <uri>https://zbmath.org/authors/?q=ai:huo.yumei</uri> </author> <author> <name>&quot;Zhao, Hairong&quot;</name> <uri>https://zbmath.org/authors/?q=ai:zhao.hairong</uri> </author> <content type="text">Summary: We study the problem of minimizing total completion time on parallel machines subject to varying processing capacity. In this paper, we develop an approximation scheme for the problem under the data stream model where the input data is massive and cannot fit into memory and thus can only be scanned a few times. Our algorithm can compute an approximate value of the optimal total completion time in one pass and output the schedule with the approximate value in two passes.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Mixed graph colouring as scheduling multi-processor tasks with equal processing times</title> <id>https://zbmath.org/1553.90018</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90018" /> <author> <name>&quot;Sotskov, Yuri沫 Nazarovich&quot;</name> <uri>https://zbmath.org/authors/?q=ai:sotskov.yurii-nazarovich</uri> </author> <content type="text">Summary: A problem of scheduling partially ordered unit-time tasks processed on dedicated machines is formulated as a mixed graph colouring problem, i. e., as an assignment of integers (colours) \(\{1, 2, \dots, t\}\) to the vertices (tasks) \(V =\{ v_1, v_2, \dots, v_n\}\), of the mixed graph \(G = (V, A, E)\) such that if vertices \(v_p\) and \(v_q\) are joined by an edge \([ v_p, v_q] \in E\) their colours have to be different. Further, if two vertices \(v_{p}\) and \(v_{q}\) are joined by an arc \(( v_i, v_j) \in A\) the colour of vertex \(v_i\) has to be no greater than the colour of vertex \(v_j\). We prove that an optimal colouring of a mixed graph \(G = (V, A, E)\) is equivalent to the scheduling problem \(GcMPT|p_i = 1|C_{\max}\) of finding an optimal schedule for partially ordered multi-processor tasks with unit (equal) processing times. Contrary to classical shop-scheduling problems, several dedicated machines are required to process an individual task in the scheduling problem \(GcMPT|p_i = 1|C_{\max}\). Moreover, along with precedence constraints given on the set \(V =\{ v_1, v_2, \dots, v_n\}\), it is required that a subset of tasks must be processed simultaneously. Due to the theorems proved in this article, most analytical results that have been proved for the scheduling problems \(GcMPT |p_i = 1|C_{\max}\) so far, have analogous results for optimal colourings of the mixed graphs \(G = (V, A, E)\), and vice versa.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Notice of duplicate publication: ``Analyse de la signifiance de diverses proc茅dures d'agr茅gation multicritere''</title> <id>https://zbmath.org/1553.90019</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90019" /> <content type="text">From the text: Please note that the article [\textit{J.-M. Martel} and \textit{B. Roy}, INFOR 44, No. 3, 191--215 (2006; Zbl 1548.90262)] has been removed from INFOR: Information Systems and Operational Research as it is a duplicate publication of [\textit{J.-M. Martel} and \textit{B. Roy}, ibid. 43, No. 3, 221--245 (2005; Zbl 1548.90261)].</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Correction to: ``A novel approach for modelling strategic alliances and partnerships based on the DEA-R models''</title> <id>https://zbmath.org/1553.90020</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90020" /> <author> <name>&quot;Sohrabi, Abozar&quot;</name> <uri>https://zbmath.org/authors/?q=ai:sohrabi.abozar</uri> </author> <author> <name>&quot;Gerami, Javad&quot;</name> <uri>https://zbmath.org/authors/?q=ai:gerami.javad</uri> </author> <author> <name>&quot;Mozaffari, Mohammad Reza&quot;</name> <uri>https://zbmath.org/authors/?q=ai:mozaffari.mohammad-reza</uri> </author> <content type="text">Correction to the authors' paper [ibid. 41, No. 3, 1629--1678 (2024; Zbl 1548.90266)].</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">On the power of symmetric linear programs</title> <id>https://zbmath.org/1553.90021</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90021" /> <author> <name>&quot;Atserias, Albert&quot;</name> <uri>https://zbmath.org/authors/?q=ai:atserias.albert</uri> </author> <author> <name>&quot;Dawar, Anuj&quot;</name> <uri>https://zbmath.org/authors/?q=ai:dawar.anuj</uri> </author> <author> <name>&quot;Ochremiak, Joanna&quot;</name> <uri>https://zbmath.org/authors/?q=ai:ochremiak.joanna</uri> </author> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">A simple method for convex optimization in the oracle model</title> <id>https://zbmath.org/1553.90022</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90022" /> <author> <name>&quot;Dadush, Daniel&quot;</name> <uri>https://zbmath.org/authors/?q=ai:dadush.daniel</uri> </author> <author> <name>&quot;Hojny, Christopher&quot;</name> <uri>https://zbmath.org/authors/?q=ai:hojny.christopher</uri> </author> <author> <name>&quot;Huiberts, Sophie&quot;</name> <uri>https://zbmath.org/authors/?q=ai:huiberts.sophie</uri> </author> <author> <name>&quot;Weltge, Stefan&quot;</name> <uri>https://zbmath.org/authors/?q=ai:weltge.stefan</uri> </author> <content type="text">Summary: We give a simple and natural method for computing approximately optimal solutions for minimizing a convex function \(f\) over a convex set \(K\) given by a separation oracle. Our method utilizes the Frank-Wolfe algorithm over the cone of valid inequalities of \(K\) and subgradients of \(f\). Under the assumption that \(f\) is \(L\)-Lipschitz and that \(K\) contains a ball of radius \(r\) and is contained inside the origin centered ball of radius \(R\), using \(O\left( \frac{(RL)^2}{\varepsilon^2} \cdot \frac{R^2}{r^2}\right)\) iterations and calls to the oracle, our main method outputs a point \(x \in K\) satisfying \(f(x) \le \varepsilon + \min_{z \in K} f(z)\). Our algorithm is easy to implement, and we believe it can serve as a useful alternative to existing cutting plane methods. As evidence towards this, we show that it compares favorably in terms of iteration counts to the standard LP based cutting plane method and the analytic center cutting plane method, on a testbed of combinatorial, semidefinite and machine learning instances.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">On circuit diameter bounds via circuit imbalances</title> <id>https://zbmath.org/1553.90023</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90023" /> <author> <name>&quot;Dadush, Daniel&quot;</name> <uri>https://zbmath.org/authors/?q=ai:dadush.daniel</uri> </author> <author> <name>&quot;Koh, Zhuan Khye&quot;</name> <uri>https://zbmath.org/authors/?q=ai:koh.zhuan-khye</uri> </author> <author> <name>&quot;Natura, Bento&quot;</name> <uri>https://zbmath.org/authors/?q=ai:natura.bento</uri> </author> <author> <name>&quot;V茅gh, L谩szl贸 A.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:vegh.laszlo-a</uri> </author> <content type="text">Summary: We study the circuit diameter of polyhedra, introduced by \textit{S. Borgwardt} et al. [SIAM J. Discrete Math. 29, No. 1, 113--121 (2015; Zbl 1335.90058)] as a relaxation of the combinatorial diameter. We show that the circuit diameter of a system \(\{x\in \mathbb{R}^n: Ax=b,\, 0 \kern-5pt | \le x\le u\}\) for \(A\in \mathbb{R}^{m\times n}\) is bounded by \(O(m\min \{m, n - m\}\log (m+\kappa_A)+n\log n)\), where \(\kappa_A\) is the circuit imbalance measure of the constraint matrix. This yields a strongly polynomial circuit diameter bound if e.g., all entries of \(A\) have polynomially bounded encoding length in \(n\). Further, we present circuit augmentation algorithms for LPs using the minimum-ratio circuit cancelling rule. Even though the standard minimum-ratio circuit cancelling algorithm is not finite in general, our variant can solve an LP in \(O(mn^2\log (n+\kappa_A))\) augmentation steps.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Approximating optimal transport with linear programs</title> <id>https://zbmath.org/1553.90024</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90024" /> <author> <name>&quot;Quanrud, Kent&quot;</name> <uri>https://zbmath.org/authors/?q=ai:quanrud.kent</uri> </author> <content type="text">Summary: In the regime of bounded transportation costs, additive approximations for the optimal transport problem are reduced (rather simply) to relative approximations for positive linear programs, resulting in faster additive approximation algorithms for optimal transport. For the entire collection see [Zbl 1407.68030].</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">A new Dai-Liao conjugate gradient method based on approximately optimal stepsize for unconstrained optimization</title> <id>https://zbmath.org/1553.90025</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90025" /> <author> <name>&quot;Ni, Yan&quot;</name> <uri>https://zbmath.org/authors/?q=ai:ni.yan</uri> </author> <author> <name>&quot;Zexian, Liu&quot;</name> <uri>https://zbmath.org/authors/?q=ai:zexian.liu</uri> </author> <content type="text">Summary: Conjugate gradient methods are a class of very effective iterative methods for large-scale unconstrained optimization. In this paper, a new Dai-Liao conjugate gradient method for solving large-scale unconstrained optimization problem is proposed. Based on the approximately optimal stepsize for the gradient method, we derive three new choices for the important parameters \(t_k\) in Dai-Liao conjugate gradient method. The search direction satisfies the sufficient descent condition, and the global convergences of the proposed method for uniformly convex and general functions are proved under some mild conditions. Numerical experiments on a set of test problems from the CUTEst library show that the proposed method is superior to some well-known conjugate gradient methods.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Algorithms for Euclidean-regularised optimal transport</title> <id>https://zbmath.org/1553.90026</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90026" /> <author> <name>&quot;Pasechnyuk, Dmitry A.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:pasechnyuk.dmitry-a</uri> </author> <author> <name>&quot;Persiianov, Michael&quot;</name> <uri>https://zbmath.org/authors/?q=ai:persiianov.michael</uri> </author> <author> <name>&quot;Dvurechensky, Pavel&quot;</name> <uri>https://zbmath.org/authors/?q=ai:dvurechensky.pavel-e</uri> </author> <author> <name>&quot;Gasnikov, Alexander&quot;</name> <uri>https://zbmath.org/authors/?q=ai:gasnikov.aleksandr-v</uri> </author> <content type="text">Summary: This paper addresses the Optimal Transport problem, which is regularized by the square of Euclidean \(\ell_2\)-norm. It offers theoretical guarantees regarding the iteration complexities of the Sinkhorn-Knopp algorithm, Accelerated Gradient Descent, Accelerated Alternating Minimisation, and Coordinate Linear Variance Reduction algorithms. Furthermore, the paper compares the practical efficiency of these methods and their counterparts when applied to the entropy-regularized Optimal Transport problem. This comparison is conducted through numerical experiments carried out on the MNIST dataset. For the entire collection see [Zbl 1543.90002].</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Total dual dyadicness and dyadic generating sets</title> <id>https://zbmath.org/1553.90027</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90027" /> <author> <name>&quot;Abdi, Ahmad&quot;</name> <uri>https://zbmath.org/authors/?q=ai:abdi.ahmad</uri> </author> <author> <name>&quot;Cornu茅jols, G茅rard&quot;</name> <uri>https://zbmath.org/authors/?q=ai:cornuejols.gerard-p</uri> </author> <author> <name>&quot;Guenin, Bertrand&quot;</name> <uri>https://zbmath.org/authors/?q=ai:guenin.bertrand</uri> </author> <author> <name>&quot;Tun莽el, Levent&quot;</name> <uri>https://zbmath.org/authors/?q=ai:tuncel.levent</uri> </author> <content type="text">Summary: A vector is \textit{dyadic} if each of its entries is a dyadic rational number, i.e. of the form \(\frac{a}{2^k}\) for some integers \(a, k\) with \(k\ge 0\). A linear system \(Ax\le b\) with integral data is \textit{totally dual dyadic} if whenever \(\min \{b^\top y:A^\top y=w,\,y\ge \mathbf{0}\}\) for \(w\) integral, has an optimal solution, it has a dyadic optimal solution. In this paper, we study total dual dyadicness, and give a co-NP characterization of it in terms of \textit{dyadic generating sets for cones and subspaces}, the former being the dyadic analogue of \textit{Hilbert bases}, and the latter a polynomial-time recognizable relaxation of the former. Along the way, we see some surprising turn of events when compared to total dual integrality, primarily led by the \textit{density} of the dyadic rationals. Our study ultimately leads to a better understanding of total dual integrality and polyhedral integrality. We see examples from dyadic matroids, \(T\)-joins, cycles, and perfect matchings of a graph.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">On the maximal number of columns of a \(\Delta \)-modular integer matrix: bounds and computations</title> <id>https://zbmath.org/1553.90028</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90028" /> <author> <name>&quot;Averkov, Gennadiy&quot;</name> <uri>https://zbmath.org/authors/?q=ai:averkov.gennadiy</uri> </author> <author> <name>&quot;Schymura, Matthias&quot;</name> <uri>https://zbmath.org/authors/?q=ai:schymura.matthias</uri> </author> <content type="text">Summary: We study the maximal number of pairwise distinct columns in a \(\Delta \)-modular integer matrix with \(m\) rows. Recent results by \textit{J. Lee} et al. [Math. Oper. Res. 48, No. 4, 2267--2286 (2023; Zbl 1541.90250)] provide an asymptotically tight upper bound of \(\mathcal{O}\left( m^2\right)\) for fixed \(\Delta \). We complement this and obtain an upper bound of the form \(\mathcal{O}(\Delta )\) for fixed \(m\), and with the implied constant depending polynomially on \(m\).</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">On the complexity of separating cutting planes for the knapsack polytope</title> <id>https://zbmath.org/1553.90029</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90029" /> <author> <name>&quot;Del Pia, Alberto&quot;</name> <uri>https://zbmath.org/authors/?q=ai:del-pia.alberto</uri> </author> <author> <name>&quot;Linderoth, Jeff&quot;</name> <uri>https://zbmath.org/authors/?q=ai:linderoth.jeff-t</uri> </author> <author> <name>&quot;Zhu, Haoran&quot;</name> <uri>https://zbmath.org/authors/?q=ai:zhu.haoran.1</uri> </author> <content type="text">Summary: We close three open problems on the separation complexity of valid inequalities for the knapsack polytope. Specifically, we establish that the separation problems for extended cover inequalities, \((1, k)\)-configuration inequalities, and weight inequalities are all \(\mathcal{N}\mathcal{P} \)-complete. We also show that, when the number of constraints of the LP relaxation is constant and its optimal solution is an extreme point, then the separation problems of both extended cover inequalities and weight inequalities can be solved in polynomial time. Moreover, we provide a natural generalization of \((1, k)\)-configuration inequality which is easier to separate and contains the original \((1, k)\)-configuration inequality as a strict sub-family.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">On computing small variable disjunction branch-and-bound trees</title> <id>https://zbmath.org/1553.90030</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90030" /> <author> <name>&quot;Gl盲ser, Max&quot;</name> <uri>https://zbmath.org/authors/?q=ai:glaser.max</uri> </author> <author> <name>&quot;Pfetsch, Marc E.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:pfetsch.marc-e</uri> </author> <content type="text">Summary: This article investigates smallest branch-and-bound trees and their computation. We first revisit the notion of hiding sets to deduce lower bounds on the size of branch-and-bound trees for certain binary programs, using both variable disjunctions and general disjunctions. We then provide exponential lower bounds for variable disjunctions by a disjoint composition of smaller binary programs. Moreover, we investigate the complexity of finding small branch-and-bound trees using variable disjunctions: We show that it is not possible to approximate the size of a smallest branch-and-bound tree within a factor of \(2^{\frac{1}{5}n}\) in time \(O(2^{\delta n})\) with \(\delta &lt;\frac{1}{5} \), unless the strong exponential time hypothesis fails. Similarly, for any \(\varepsilon &gt; 0\), no polynomial time \(2^{(\frac{1}{2} - \varepsilon )n} \)-approximation is possible, unless \text{P} = \text{NP}. We also show that computing the size of a smallest branch-and-bound tree exactly is \({\#P} \)-hard. Similar results hold for estimating the size of the tree produced by branching rules like most-infeasible branching. Finally, we discuss that finding small branch-and-bound trees generalizes finding short treelike resolution refutations, and thus non-automatizability results transfer from this setting.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">An abstract model for branch and cut</title> <id>https://zbmath.org/1553.90031</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90031" /> <author> <name>&quot;Kazachkov, Aleksandr M.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:kazachkov.aleksandr-m</uri> </author> <author> <name>&quot;Le Bodic, Pierre&quot;</name> <uri>https://zbmath.org/authors/?q=ai:le-bodic.pierre</uri> </author> <author> <name>&quot;Sankaranarayanan, Sriram&quot;</name> <uri>https://zbmath.org/authors/?q=ai:sankaranarayanan.sriram</uri> </author> <content type="text">Summary: Branch and cut is the dominant paradigm for solving a wide range of mathematical programming problems -- linear or nonlinear -- combining efficient search (via branch and bound) and relaxation-tightening procedures (via cutting planes, or cuts). While there is a wealth of computational experience behind existing cutting strategies, there is simultaneously a relative lack of theoretical explanations for these choices, and for the tradeoffs involved therein. Recent papers have explored abstract models for branching and for comparing cuts with branch and bound. However, to model practice, it is crucial to understand the impact of jointly considering branching and cutting decisions. In this paper, we provide a framework for analyzing how cuts affect the size of branch-and-cut trees, as well as their impact on solution time. Our abstract model captures some of the key characteristics of real-world phenomena in branch-and-cut experiments, regarding whether to generate cuts only at the root or throughout the tree, how many rounds of cuts to add before starting to branch, and why cuts seem to exhibit nonmonotonic effects on the solution process.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">One segregation problem for the sum of two quasiperiodic sequences</title> <id>https://zbmath.org/1553.90032</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90032" /> <author> <name>&quot;Mikhailova, Liudmila&quot;</name> <uri>https://zbmath.org/authors/?q=ai:mikhailova.ludmila-viktorovna</uri> </author> <content type="text">Summary: The subject of the study is a noise-proof segregation problem for the sequence being the sum of two independent quasiperiodic sequences. The problem is stated for the case when every quasiperiodic sequence is formed from the known number of identical given subsequences-fragments. A posteriori approach to this problem leads to solving an unexplored discrete optimization problem. A polynomial-time algorithm that guarantees the optimal solution to this optimization problem is proposed. Additionally, there are some examples of numerical simulation for illustration. For the entire collection see [Zbl 1543.90002].</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Wind farm layout optimization under uncertainty</title> <id>https://zbmath.org/1553.90033</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90033" /> <author> <name>&quot;Agra, Agostinho&quot;</name> <uri>https://zbmath.org/authors/?q=ai:agra.agostinho</uri> </author> <author> <name>&quot;Cerveira, Adelaide&quot;</name> <uri>https://zbmath.org/authors/?q=ai:cerveira.adelaide</uri> </author> <content type="text">Summary: Wind power is a major source of green energy production. However, the energy generation of wind power is highly affected by uncertainty. Here, we consider the problem of designing the cable network that interconnects the turbines to the substation in wind farms, aiming to minimize both the infrastructure cost and the cost of the energy losses during the wind farm's lifetime. Nonetheless, the energy losses depend on wind direction and speed, which are rarely known with certainty in real situations. Hence, the design of the network should consider these losses as uncertain parameters. We assume that the exact probability distribution of these parameters is unknown but belongs to an ambiguity set and propose a distributionally robust two-stage mixed integer model. The model is solved using a decomposition algorithm. Three enhancements are proposed given the computational difficulty in solving real problem instances. Computational results are reported based on real data.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Loss-optimal classification trees: a generalized framework and the logistic case</title> <id>https://zbmath.org/1553.90034</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90034" /> <author> <name>&quot;Aldinucci, Tommaso&quot;</name> <uri>https://zbmath.org/authors/?q=ai:aldinucci.tommaso</uri> </author> <author> <name>&quot;Lapucci, Matteo&quot;</name> <uri>https://zbmath.org/authors/?q=ai:lapucci.matteo</uri> </author> <content type="text">Summary: Classification trees are one of the most common models in interpretable machine learning. Although such models are usually built with greedy strategies, in recent years, thanks to remarkable advances in mixed-integer programming (MIP) solvers, several exact formulations of the learning problem have been developed. In this paper, we argue that some of the most relevant ones among these training models can be encapsulated within a general framework, whose instances are shaped by the specification of loss functions and regularizers. Next, we introduce a novel realization of this framework: specifically, we consider the logistic loss, handled in the MIP setting by a piece-wise linear approximation, and couple it with \(\ell_1\)-regularization terms. The resulting optimal logistic classification tree model numerically proves to be able to induce trees with enhanced interpretability properties and competitive generalization capabilities, compared to the state-of-the-art MIP-based approaches.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Fix-and-optimize metaheuristics for minmax regret binary integer programming problems under interval uncertainty</title> <id>https://zbmath.org/1553.90035</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90035" /> <author> <name>&quot;Carvalho, Iago A.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:carvalho.iago-augusto</uri> </author> <author> <name>&quot;Noronha, Thiago F.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:noronha.thiago-f</uri> </author> <author> <name>&quot;Duhamel, Christophe&quot;</name> <uri>https://zbmath.org/authors/?q=ai:duhamel.christophe</uri> </author> <content type="text">Summary: The Binary Integer Programming problem (BIP) is a mathematical optimization problem, with linear objective function and constraints, on which the domain of all variables is \(\{0, 1\}\). In BIP, every variable is associated with a determined cost coefficient. The Minmax regret Binary Integer Programming problem under interval uncertainty (M-BIP) is a generalization of BIP in which the cost coefficient associated to the variables is not known in advance, but are assumed to be bounded by an interval. The objective of M-BIP is to find a solution that possesses the minimum maximum regret among all possible solutions for the problem. In this paper, we show that the decision version of M-BIP is \(\Sigma^p_2\)-complete. Furthermore, we tackle M-BIP by both exact and heuristic algorithms. We extend three exact algorithms from the literature to M-BIP and propose two fix-and-optimize heuristic algorithms. Computational experiments, performed on the Minmax regret Weighted Set Covering problem under Interval Uncertainties (M-WSCP) as a test case, indicates that one of the exact algorithms outperforms the others. Furthermore, it shows that the proposed fix-and-optimize heuristics, that can be easily employed to solve any minmax regret optimization problem under interval uncertainty, are competitive with ad-hoc algorithms for the M-WSCP.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Sparse multi-term disjunctive cuts for the epigraph of a function of binary variables</title> <id>https://zbmath.org/1553.90036</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90036" /> <author> <name>&quot;Chen, Rui&quot;</name> <uri>https://zbmath.org/authors/?q=ai:chen.rui</uri> </author> <author> <name>&quot;Luedtke, James&quot;</name> <uri>https://zbmath.org/authors/?q=ai:luedtke.james</uri> </author> <content type="text">Summary: We propose a new method for separating valid inequalities for the epigraph of a function of binary variables. The proposed inequalities are disjunctive cuts defined by disjunctive terms obtained by enumerating a subset \(I\) of the binary variables. We show that by restricting the support of the cut to the same set of variables \(I\), a cut can be obtained by solving a linear program with \(2^{|I|}\) constraints. While this limits the size of the set \(I\) used to define the multi-term disjunction, the procedure enables generation of multi-term disjunctive cuts using far more terms than existing approaches. We present two approaches for choosing the subset of variables. Experience on three MILP problems with block diagonal structure using \(|I|\) up to size 10 indicates the sparse cuts can often close nearly as much gap as the multi-term disjunctive cuts without this restriction and in a fraction of the time. We also find that including these cuts within a cut-and-branch solution method for these MILP problems leads to significant reductions in solution time or ending optimality gap for instances that were not solved within the time limit. Finally, we describe how the proposed approach can be adapted to optimally ``tilt'' a given valid inequality by modifying the coefficients of a sparse subset of the variables.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">On SOCP-based disjunctive cuts for solving a class of integer bilevel nonlinear programs</title> <id>https://zbmath.org/1553.90037</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90037" /> <author> <name>&quot;Gaar, Elisabeth&quot;</name> <uri>https://zbmath.org/authors/?q=ai:gaar.elisabeth</uri> </author> <author> <name>&quot;Lee, Jon&quot;</name> <uri>https://zbmath.org/authors/?q=ai:lee.jon</uri> </author> <author> <name>&quot;Ljubi膰, Ivana&quot;</name> <uri>https://zbmath.org/authors/?q=ai:ljubic.ivana</uri> </author> <author> <name>&quot;Sinnl, Markus&quot;</name> <uri>https://zbmath.org/authors/?q=ai:sinnl.markus</uri> </author> <author> <name>&quot;Tan谋nm谋艧, K眉bra&quot;</name> <uri>https://zbmath.org/authors/?q=ai:taninmis.kubra</uri> </author> <content type="text">Summary: We study a class of integer bilevel programs with second-order cone constraints at the upper-level and a convex-quadratic objective function and linear constraints at the lower-level. We develop disjunctive cuts (DCs) to separate bilevel-infeasible solutions using a second-order-cone-based cut-generating procedure. We propose DC separation strategies and consider several approaches for removing redundant disjunctions and normalization. Using these DCs, we propose a branch-and-cut algorithm for the problem class we study, and a cutting-plane method for the problem variant with only binary variables. We present an extensive computational study on a diverse set of instances, including instances with binary and with integer variables, and instances with a single and with multiple linking constraints. Our computational study demonstrates that the proposed enhancements of our solution approaches are effective for improving the performance. Moreover, both of our approaches outperform a state-of-the-art generic solver for mixed-integer bilevel linear programs that is able to solve a linearized version of our binary instances.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Automatic MILP Solver configuration by learning problem similarities</title> <id>https://zbmath.org/1553.90038</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90038" /> <author> <name>&quot;Hosny, Abdelrahman&quot;</name> <uri>https://zbmath.org/authors/?q=ai:hosny.abdelrahman</uri> </author> <author> <name>&quot;Reda, Sherief&quot;</name> <uri>https://zbmath.org/authors/?q=ai:reda.sherief</uri> </author> <content type="text">Summary: A large number of real-world optimization problems can be formulated as Mixed Integer Linear Programs (MILP). MILP solvers expose numerous configuration parameters to control their internal algorithms. Solutions, and their associated costs or runtimes, are significantly affected by the choice of the configuration parameters, even when problem instances have the same number of decision variables and constraints. On one hand, using the default solver configuration leads to suboptimal solutions. On the other hand, searching and evaluating a large number of configurations for every problem instance is time-consuming and, in some cases, infeasible. In this study, we aim to predict configuration parameters for unseen problem instances that yield lower-cost solutions without the time overhead of searching-and-evaluating configurations at the solving time. Toward that goal, we first investigate the cost correlation of MILP problem instances that come from the same distribution when solved using different configurations. We show that instances that have similar costs using one solver configuration also have similar costs using another solver configuration in the same runtime environment. After that, we present a methodology based on Deep Metric Learning to learn MILP similarities that correlate with their final solutions' costs. At inference time, given a new problem instance, it is first projected into the learned metric space using the trained model, and configuration parameters are instantly predicted using previously-explored configurations from the nearest neighbor instance in the learned embedding space. Empirical results on real-world problem benchmarks show that our method predicts configuration parameters that improve solutions' costs by up to 38\% compared to existing approaches.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Stochastic adversarial noise in the ``black box'' optimization problem</title> <id>https://zbmath.org/1553.90039</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90039" /> <author> <name>&quot;Lobanov, Aleksandr&quot;</name> <uri>https://zbmath.org/authors/?q=ai:lobanov.aleksandr</uri> </author> <content type="text">Summary: This paper is devoted to the study of the solution of a stochastic convex black box optimization problem. Where the black box problem means that the gradient-free oracle only returns the value of objective function, not its gradient. We consider non-smooth and smooth setting of the solution to the black box problem under adversarial stochastic noise. For two techniques creating gradient-free methods: smoothing schemes via \(L_1\) and \(L_2\) randomizations, we find the maximum allowable level of adversarial stochastic noise that guarantees convergence. Finally, we analyze the convergence behavior of the algorithms under the condition of a large value of noise level. For the entire collection see [Zbl 1543.90002].</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Accelerated zero-order SGD method for solving the black box optimization problem under ``overparametrization'' condition</title> <id>https://zbmath.org/1553.90040</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90040" /> <author> <name>&quot;Lobanov, Aleksandr&quot;</name> <uri>https://zbmath.org/authors/?q=ai:lobanov.aleksandr</uri> </author> <author> <name>&quot;Gasnikov, Alexander&quot;</name> <uri>https://zbmath.org/authors/?q=ai:gasnikov.aleksandr-v</uri> </author> <content type="text">Summary: This paper is devoted to solving a convex stochastic optimization problem in a overparameterization setup for the case where the original gradient computation is not available, but an objective function value can be computed. For this class of problems we provide a novel gradient-free algorithm, whose creation approach is based on applying a gradient approximation with \(l_2\) randomization instead of a gradient oracle in the biased Accelerated SGD algorithm, which generalizes the convergence results of the AC-SA algorithm to the case where the gradient oracle returns a noisy (inexact) objective function value. We also perform a detailed analysis to find the maximum admissible level of adversarial noise at which we can guarantee to achieve the desired accuracy. We verify the theoretical results of convergence using a model example. For the entire collection see [Zbl 1543.90002].</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">A risk analytics model for strategic workforce planning: readiness of enlisted military personnel</title> <id>https://zbmath.org/1553.90041</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90041" /> <author> <name>&quot;MacDonald, Leo&quot;</name> <uri>https://zbmath.org/authors/?q=ai:macdonald.leo</uri> </author> <author> <name>&quot;Paul, Jomon Aliyas&quot;</name> <uri>https://zbmath.org/authors/?q=ai:paul.jomon-aliyas</uri> </author> <content type="text">Summary: We develop a dynamic stochastic model of military workforce planning that incorporates uncertainties about personnel gains and losses across ranks. We then apply it to determine the probability of not meeting required targets as well as the resulting shortages and overages in the short, medium, and long terms along with the evaluation of policies to mitigate these risks. Our model allows decision makers to adjust recruiting and training practices to minimize the risk of not meeting target personnel levels as well as to value retention and reenlistment policies by calculating the expected marginal value of retaining additional service members. Moreover, it allows us to create a penalty function to optimize recruiting and training levels. The outcome is a tool to evaluate and ensure comprehensive force readiness.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Hierarchical optimal control with stochastic resource constraints</title> <id>https://zbmath.org/1553.90042</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90042" /> <author> <name>&quot;Maryasin, O. Yu.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:maryasin.o-yu</uri> </author> <author> <name>&quot;Kolodkina, A. S.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:kolodkina.a-s</uri> </author> <content type="text">Summary: We consider a method for solving the problem of optimal control of a composite dynamic system with stochastic resource constraints. The method is based on the method of hierarchical optimization, which includes iterative solution of local problems and the coordination problem. To solve local problems, we apply the model predictive control. Taking into account stochastic resource constraints leads to the solution of one-stage problems of stochastic programming.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Statistical performance of subgradient step-size update rules in Lagrangian relaxations of chance-constrained optimization models</title> <id>https://zbmath.org/1553.90043</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90043" /> <author> <name>&quot;Ritter, Charlotte&quot;</name> <uri>https://zbmath.org/authors/?q=ai:ritter.charlotte</uri> </author> <author> <name>&quot;Singh, Bismark&quot;</name> <uri>https://zbmath.org/authors/?q=ai:singh.bismark</uri> </author> <content type="text">Summary: Lagrangian relaxation schemes, coupled with a subgradient procedure, are frequently employed to solve chance-constrained optimization models. Subgradient procedures typically rely on step-size update rules. Although there is extensive research on the properties of these step-size update rules, there is little consensus on which rules are most suitable practically; especially, when the underlying model is a computationally challenging instance of a chance-constrained program. To close this gap, we seek to determine whether a single step-size rule can be statistically guaranteed to perform better than others. We couple the Lagrangian procedure with three strategies to identify lower bounds for two-stage chance-constrained programs. We consider two instances of such models that differ in the presence of binary variables in the second-stage. With a series of computational experiments, we demonstrate -- in marked contrast to existing theoretical results -- that no significant statistical differences in terms of optimality gaps is detected between six well-known step-size update rules. Despite this, our results demonstrate that a Lagrangian procedure provides computational benefit over a naive solution method -- regardless of the underlying step-size update rule. For the entire collection see [Zbl 1543.90002].</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Real acceleration of communication process in distributed algorithms with compression</title> <id>https://zbmath.org/1553.90044</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90044" /> <author> <name>&quot;Tkachenko, Svetlana&quot;</name> <uri>https://zbmath.org/authors/?q=ai:tkachenko.svetlana</uri> </author> <author> <name>&quot;Andreev, Artem&quot;</name> <uri>https://zbmath.org/authors/?q=ai:andreev.artem-aleksandrovich</uri> </author> <author> <name>&quot;Beznosikov, Aleksandr&quot;</name> <uri>https://zbmath.org/authors/?q=ai:beznosikov.aleksandr</uri> </author> <author> <name>&quot;Gasnikov, Alexander&quot;</name> <uri>https://zbmath.org/authors/?q=ai:gasnikov.aleksandr-v|gasnikov.alexander</uri> </author> <content type="text">Summary: Modern applied optimization problems become more and more complex every day. Due to this fact, distributed algorithms that can speed up the process of solving an optimization problem through parallelization are of great importance. The main bottleneck of distributed algorithms is communications, which can slow down the method dramatically. One way to solve this issue is to use compression of transmitted information. In the current literature on theoretical distributed optimization, it is generally accepted that as much as we compress information, so much we reduce communication time. But in reality, the communication time depends not only on the size of the transmitted information, but also, for example, on the message startup time. In this paper, we study distributed optimization algorithms under the assumption of a more complex and closer-to-reality dependence of transmission time on compression. In particular, we describe the real speedup achieved by compression, analyze how much it makes sense to compress information, and present an adaptive way to select the power of compression depending on unknown or changing parameters of the communication process. For the entire collection see [Zbl 1543.90002].</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Enhanced branch-and-bound algorithm for chance constrained programs with Gaussian mixture models</title> <id>https://zbmath.org/1553.90045</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90045" /> <author> <name>&quot;Wei, Jinxiang&quot;</name> <uri>https://zbmath.org/authors/?q=ai:wei.jinxiang</uri> </author> <author> <name>&quot;Hu, Zhaolin&quot;</name> <uri>https://zbmath.org/authors/?q=ai:hu.zhaolin</uri> </author> <author> <name>&quot;Luo, Jun&quot;</name> <uri>https://zbmath.org/authors/?q=ai:luo.jun.1|luo.jun.2|luo.jun.5|luo.jun.4|luo.jun.6</uri> </author> <author> <name>&quot;Zhu, Shushang&quot;</name> <uri>https://zbmath.org/authors/?q=ai:zhu.shushang</uri> </author> <content type="text">Summary: We study a class of chance constrained programs (CCPs) where the underlying distribution is modeled by a Gaussian mixture model. As the original work, \textit{Z. Hu} et al. [IISE Trans. 54, No. 12, 1117--1130 (2022; \url{doi:10.1080/24725854.2021.2001608})] developed a spatial branch-and-bound (B\&amp;B) algorithm to solve the problems. In this paper, we propose an enhanced procedure to speed up the computation of B\&amp;B algorithm. We design an enhanced pruning strategy that explores high-potential domains and an augmented branching strategy that prevents redundant computations. We integrate the new strategies into original framework to develop an enhanced B\&amp;B algorithm, and illustrate how the enhanced algorithm improves on the original approach. Furthermore, we extend the enhanced B\&amp;B framework to handle the CCPs with multiple chance constraints, which is not considered in the previous work. We evaluate the performance of our new algorithm through extensive numerical experiments and apply it to solve a real-world portfolio selection problem.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Efficient solutions to the \(m\)-machine robust flow shop under budgeted uncertainty</title> <id>https://zbmath.org/1553.90046</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90046" /> <author> <name>&quot;Levorato, Mario&quot;</name> <uri>https://zbmath.org/authors/?q=ai:levorato.mario</uri> </author> <author> <name>&quot;Sotelo, David&quot;</name> <uri>https://zbmath.org/authors/?q=ai:sotelo.david</uri> </author> <author> <name>&quot;Figueiredo, Rosa&quot;</name> <uri>https://zbmath.org/authors/?q=ai:figueiredo.rosa-m-v</uri> </author> <author> <name>&quot;Frota, Yuri&quot;</name> <uri>https://zbmath.org/authors/?q=ai:frota.yuri-abitbol-de-menezes</uri> </author> <content type="text">Summary: This work presents two solution methods for the \(m\)-machine robust permutation flow shop problem with processing time uncertainty. The goal is to minimize the makespan of the worst-case scenario by utilizing an approach based on budgeted uncertainty, in which only a subset of operations will reach their worst-case processing time values. To obtain efficient solutions to this problem, we first extend an existing two-machine worst-case procedure, based on dynamic programming, generalizing it to \(m\) machines. The worst-case calculation is then incorporated into two proposed solution methods: an exact column-and-constraint generation algorithm and a GRASP metaheuristic. Based on experiments with four sets of literature-based instances, empirical results demonstrate the ability of the GRASP to efficiently produce an optimal or near-optimal solution in most cases.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">A branch-price-and-cut algorithm for stochastic crowd shipping last-mile delivery with correlated marginals</title> <id>https://zbmath.org/1553.90047</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90047" /> <author> <name>&quot;Silva, Marco&quot;</name> <uri>https://zbmath.org/authors/?q=ai:silva.marco-a-n</uri> </author> <author> <name>&quot;Pedroso, Jo茫o Pedro&quot;</name> <uri>https://zbmath.org/authors/?q=ai:pedroso.joao-pedro</uri> </author> <author> <name>&quot;Viana, Ana&quot;</name> <uri>https://zbmath.org/authors/?q=ai:viana.ana</uri> </author> <author> <name>&quot;Klimentova, Xenia&quot;</name> <uri>https://zbmath.org/authors/?q=ai:klimentova.xenia</uri> </author> <content type="text">Summary: We study last-mile delivery with the option of crowd shipping, where a company makes use of occasional drivers to complement its vehicle's fleet in the activity of delivering products to its customers. We model it as a data-driven distributionally robust optimization approach to the capacitated vehicle routing problem. We assume the marginals of the defined uncertainty vector are known, but the joint distribution is difficult to estimate. The presence of customers and available occasional drivers can be random. We adopt a strategic planning perspective, where an optimal a priori solution is calculated before the uncertainty is revealed. Therefore, without the need for online resolution performance, we can experiment with exact solutions. Solving the problem defined above is challenging: not only the first-stage problem is already NP-Hard, but also the uncertainty and potentially the second-stage decisions are binary of high dimension, leading to non-convex optimization formulations that are complex to solve. We propose a branch-price-and-cut algorithm taking into consideration measures that exploit the intrinsic characteristics of our problem and reduce the complexity to solve it. For the entire collection see [Zbl 1473.90002].</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">LP-based approximations for disjoint bilinear and two-stage adjustable robust optimization</title> <id>https://zbmath.org/1553.90048</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90048" /> <author> <name>&quot;El Housni, Omar&quot;</name> <uri>https://zbmath.org/authors/?q=ai:el-housni.omar</uri> </author> <author> <name>&quot;Foussoul, Ayoub&quot;</name> <uri>https://zbmath.org/authors/?q=ai:foussoul.ayoub</uri> </author> <author> <name>&quot;Goyal, Vineet&quot;</name> <uri>https://zbmath.org/authors/?q=ai:goyal.vineet</uri> </author> <content type="text">Summary: We consider the class of disjoint bilinear programs \(\max \, \{ \mathbf{x}^T \mathbf{y} \mid \mathbf{x} \in{\mathcal{X}}, \, \mathbf{y} \in{\mathcal{Y}}\}\) where \({\mathcal{X}}\) and \({\mathcal{Y}}\) are packing polytopes. We present an \(O(\frac{\log \log m_1}{\log m_1} \frac{\log \log m_2}{\log m_2})\)-approximation algorithm for this problem where \(m_1\) and \(m_2\) are the number of packing constraints in \({\mathcal{X}}\) and \({\mathcal{Y}}\) respectively. In particular, we show that there exists a near-optimal solution \((\tilde{{\mathbf{x}}}, \tilde{{\mathbf{y}}})\) such that \(\tilde{{\mathbf{x}}}\) and \(\tilde{{\mathbf{y}}}\) are ``near-integral''. We give an LP relaxation of the problem from which we obtain the near-optimal near-integral solution via randomized rounding. We show that our relaxation is tightly related to the widely used reformulation linearization technique. As an application of our techniques, we present a tight approximation for the two-stage adjustable robust optimization problem with covering constraints and right-hand side uncertainty where the separation problem is a bilinear optimization problem. In particular, based on the ideas above, we give an LP restriction of the two-stage problem that is an \(O(\frac{\log n}{\log \log n} \frac{\log L}{\log \log L})\)-approximation where \(L\) is the number of constraints in the uncertainty set. This significantly improves over state-of-the-art approximation bounds known for this problem. Furthermore, we show that our LP restriction gives a feasible affine policy for the two-stage robust problem with the same (or better) objective value. As a consequence, affine policies give an \(O(\frac{\log n}{\log \log n} \frac{\log L}{\log \log L})\)-approximation of the two-stage problem, significantly generalizing the previously known bounds on their performance.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">A random active set method for strictly convex quadratic problem with simple bounds</title> <id>https://zbmath.org/1553.90049</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90049" /> <author> <name>&quot;Gu, Ran&quot;</name> <uri>https://zbmath.org/authors/?q=ai:gu.ran</uri> </author> <author> <name>&quot;Gao, Bing&quot;</name> <uri>https://zbmath.org/authors/?q=ai:gao.bing</uri> </author> <content type="text">Summary: The active set method aims at finding the correct active set of the optimal solution and it is a powerful method for solving strictly convex quadratic problems with bound constraints. To guarantee the finite step convergence, existing active set methods all need strict conditions or some additional strategies, which can significantly impact the efficiency of the algorithm. In this paper, we propose a random active set method that introduces randomness in the active set's update process. We prove that the algorithm can converge in a finite number of iterations with probability one, without any extra conditions on the problem or any supplementary strategies. At last, numerical experiments show that the algorithm can obtain the correct active set within a few iterations, and it has better efficiency and robustness than the existing methods.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Trajectory generation for the unicycle model using semidefinite relaxations</title> <id>https://zbmath.org/1553.90050</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90050" /> <author> <name>&quot;H盲ring, Hannah&quot;</name> <uri>https://zbmath.org/authors/?q=ai:haring.hannah</uri> </author> <author> <name>&quot;Gramlich, Dennis&quot;</name> <uri>https://zbmath.org/authors/?q=ai:gramlich.dennis</uri> </author> <author> <name>&quot;Ebenbauer, Christian&quot;</name> <uri>https://zbmath.org/authors/?q=ai:ebenbauer.christian</uri> </author> <author> <name>&quot;Scherer, Carsten W.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:scherer.carsten-w</uri> </author> <content type="text">Summary: We develop a convex relaxation for the minimum energy control problem of the well-known unicycle model in the form of a semidefinite program. Through polynomialization techniques, the infinite-dimensional optimal control problem is first reformulated as a non-convex, infinite-dimensional quadratic program which can be viewed as a trajectory generation problem. This problem is then discretized to arrive at a finite-dimensional, albeit, non-convex quadratically constrained quadratic program. By applying the moment relaxation method to this quadratic program, we obtain a hierarchy of semidefinite relaxations. We construct an approximate solution for the infinite-dimensional trajectory generation problem by solving the first- or second-order moment relaxation. A comprehensive simulation study provided in this paper suggests that the second-order moment relaxation is lossless.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Linear semidefinite programming problems: regularisation and strong dual formulations</title> <id>https://zbmath.org/1553.90051</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90051" /> <author> <name>&quot;Kostyukova, Ol'ga Ivanovna.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:kostyukova.olga-ivanovna</uri> </author> <author> <name>&quot;Chemisova, Tat'yana Vladimirovna&quot;</name> <uri>https://zbmath.org/authors/?q=ai:chemisova.tatyana-vladimirovna</uri> </author> <content type="text">Summary: Regularisation consists in reducing a given optimisation problem to an equivalent form where certain regularity conditions, which guarantee the strong duality, are fulfilled. In this paper, for linear problems of semidefinite programming (SDP), we propose a regularisation procedure which is based on the concept of an immobile index set and its properties. This procedure is described in the form of a finite algorithm which converts any linear semidefinite problem to a form that satisfies the Slater condition. Using the properties of the immobile indices and the described regularization procedure, we obtained new dual SDP problems in implicit and explicit forms. It is proven that for the constructed dual problems and the original problem the strong duality property holds true.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Approximation hierarchies for copositive cone over symmetric cone and their comparison</title> <id>https://zbmath.org/1553.90052</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90052" /> <author> <name>&quot;Nishijima, Mitsuhiro&quot;</name> <uri>https://zbmath.org/authors/?q=ai:nishijima.mitsuhiro</uri> </author> <author> <name>&quot;Nakata, Kazuhide&quot;</name> <uri>https://zbmath.org/authors/?q=ai:nakata.kazuhide</uri> </author> <content type="text">This paper introduces approximation hierarchies for the copositivity cone (COP) over symmetric cones. Approximation hierarchies are families of cones \(\mathcal{K}_r\) so that as \(r\) increases the cone \(\mathcal{K}_r\) provides a tighter and tighter approximation to the COP cone over a symmetric cone. In the first part of the paper, an inner approximation hierarchy (meaning that the hierarchy approximates the cones from the inside) is constructed using sum-of-square constraints. Namely, a hierarchy of cones defined using a SOS constraint is developed to approximate the COP cone over the symmetric cone associated to a Euclidean Jordan algebra. In the second part, the COP cone over a symmetric cone is characterised using the usual COP cone, and this characterisation can then be used to exploit approximation hierarchies of the usual COP cone to approximate the COP cone over symmetric cones. The characterisation of the COP cone over the symmetric cone is obtained as the set of all symmetric tensors whose application on every Jordan frame is in an associated usual COP cone. The final section of the paper provides an overview of numerical experiments to show that the proposed hierarchies perform well. Reviewer: Julien Ugon (Burwood)</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Simple odd \(\beta \)-cycle inequalities for binary polynomial optimization</title> <id>https://zbmath.org/1553.90054</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90054" /> <author> <name>&quot;Del Pia, Alberto&quot;</name> <uri>https://zbmath.org/authors/?q=ai:del-pia.alberto</uri> </author> <author> <name>&quot;Walter, Matthias&quot;</name> <uri>https://zbmath.org/authors/?q=ai:walter.matthias</uri> </author> <content type="text">Summary: We consider the multilinear polytope which arises naturally in binary polynomial optimization. Del Pia and Di Gregorio introduced the class of odd \(\beta \)-cycle inequalities valid for this polytope, showed that these generally have Chv谩tal rank 2 with respect to the standard relaxation and that, together with flower inequalities, they yield a perfect formulation for cycle hypergraph instances. Moreover, they describe a separation algorithm in case the instance is a cycle hypergraph. We introduce a weaker version, called simple odd \(\beta \)-cycle inequalities, for which we establish a strongly polynomial-time separation algorithm for arbitrary instances. These inequalities still have Chv谩tal rank 2 in general and still suffice to describe the multilinear polytope for cycle hypergraphs. Finally, we report about computational results of our prototype implementation. The simple odd \(\beta \)-cycle inequalities sometimes help to close more of the integrality gap in the experiments; however, the preliminary implementation has substantial computational cost, suggesting room for improvement in the separation algorithm.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Non-ergodic linear convergence property of the delayed gradient descent under the strongly convexity and the Polyak-艁ojasiewicz condition</title> <id>https://zbmath.org/1553.90055</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90055" /> <author> <name>&quot;Choi, Hyung Jun&quot;</name> <uri>https://zbmath.org/authors/?q=ai:choi.hyungjun</uri> </author> <author> <name>&quot;Choi, Woocheol&quot;</name> <uri>https://zbmath.org/authors/?q=ai:choi.woocheol</uri> </author> <author> <name>&quot;Seok, Jinmyoung&quot;</name> <uri>https://zbmath.org/authors/?q=ai:seok.jinmyoung</uri> </author> <content type="text">Summary: In this work, we establish the linear convergence estimate for the gradient descent involving the delay \(\tau\in\mathbb{N}\) when the cost function is \(\mu \)-strongly convex and \(L\)-smooth. This result improves upon the well-known estimates in [\textit{Y. Arjevani} et al., ``A tight convergence analysis for stochastic gradient descent with delayed updates'', Preprint, \url{arXiv:1806.10188}; \textit{S. U. Stich} and \textit{S. P. Karimireddy}, ``The error-feedback framework: better rates for SGD with delayed gradients and compressed updates'', Preprint, \url{arXiv:1909.05350}] in the sense that it is non-ergodic and is still established in spite of weaker constraint of cost function. Also, the range of learning rate \(\eta\) can be extended from \(\eta\leq 1/(10L\tau)\) to \(\eta\leq 1/(4L\tau)\) for \(\tau=1\) and \(\eta\leq 3/(10L\tau)\) for \(\tau\geq 2\), where \(L&gt;0\) is the Lipschitz continuity constant of the gradient of cost function. In a further research, we show the linear convergence of cost function under the Polyak-艁ojasiewicz (PL) condition, for which the available choice of learning rate is further improved as \(\eta\leq 9/(10L\tau)\) for the large delay \(\tau\). The framework of the proof for this result is also extended to the stochastic gradient descent with time-varying delay under the PL condition. Finally, some numerical experiments are provided in order to confirm the reliability of the analyzed results.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Publisher correction to: ``Branch-and-bound performance estimation programming: a unified methodology for constructing optimal optimization methods''</title> <id>https://zbmath.org/1553.90056</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90056" /> <author> <name>&quot;Das Gupta, Shuvomoy&quot;</name> <uri>https://zbmath.org/authors/?q=ai:das-gupta.shuvomoy</uri> </author> <author> <name>&quot;Van Parys, Bart P. G.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:van-parys.bart-p-g</uri> </author> <author> <name>&quot;Ryu, Ernest K.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:ryu.ernest-k</uri> </author> <content type="text">An error of the original article is corrected. Reviewer: Yisheng Song (Chongqing)</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Difference of Convex programming in adversarial SVM</title> <id>https://zbmath.org/1553.90057</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90057" /> <author> <name>&quot;Astorino, Annabella&quot;</name> <uri>https://zbmath.org/authors/?q=ai:astorino.annabella</uri> </author> <author> <name>&quot;Gaudioso, Manlio&quot;</name> <uri>https://zbmath.org/authors/?q=ai:gaudioso.manlio</uri> </author> <author> <name>&quot;Gorgone, Enrico&quot;</name> <uri>https://zbmath.org/authors/?q=ai:gorgone.enrico</uri> </author> <author> <name>&quot;Manca, Benedetto&quot;</name> <uri>https://zbmath.org/authors/?q=ai:manca.benedetto</uri> </author> <content type="text">Summary: We present two models in adversarial machine learning, focussing on the Support Vector Machine framework. In particular, we consider both an evasion and a poisoning problem. The first model is aimed at constructing effective \textit{sparse} perturbation of the dataset samples, while the objective of the second is to induce a substantial \textit{rotation} of the hyperplane defining the classifier. The two models are formulated as Difference of Convex nonsmooth optimization problems. Numerical results on both synthetic and real life datasets are reported.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">An efficient regularized PR splitting type algorithm for two-block nonconvex linear constrained programs in \(\ell_{1 / 2}\) regularized compressed sensing problems</title> <id>https://zbmath.org/1553.90058</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90058" /> <author> <name>&quot;Chao, Miantao&quot;</name> <uri>https://zbmath.org/authors/?q=ai:chao.miantao</uri> </author> <author> <name>&quot;Lu, Yongzi&quot;</name> <uri>https://zbmath.org/authors/?q=ai:lu.yongzi</uri> </author> <author> <name>&quot;Jian, Jinbao&quot;</name> <uri>https://zbmath.org/authors/?q=ai:jian.jinbao</uri> </author> <author> <name>&quot;Xu, Xiao&quot;</name> <uri>https://zbmath.org/authors/?q=ai:xu.xiao.1</uri> </author> <content type="text">Summary: In this paper, we study the resolution of two-block nonconvex linear constrained optimization problems. The objective function of this program combines a hypoconvex Lipschitz differentiable function and a proper l.s.c. function. We discuss a new regularized version of Peaceman-Rachford splitting method (RPRSM), where each subproblem at each iteration are regularized by a proximal point term. When the regularization term is chosen suitable and the penalty parameter is chosen above a computable threshold, we show that any cluster point of the sequence generated, if exists, will give a stationary point of the optimization problem. Furthermore, under the assumption that the associated function satisfied the Kurdyka-艁ojasiewicz property, we prove that the iterative sequence generated by RPRSM converges to a stationary point of the associated Lagrangian function. Finally, some preliminary numerical results are reported to support the efficiency of the proposed algorithm.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">A Nesterov type algorithm with double Tikhonov regularization: fast convergence of the function values and strong convergence to the minimal norm solution</title> <id>https://zbmath.org/1553.90059</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90059" /> <author> <name>&quot;Karapetyants, Mikhail&quot;</name> <uri>https://zbmath.org/authors/?q=ai:karapetyants.mikhail-a</uri> </author> <author> <name>&quot;L谩szl贸, Szil谩rd Csaba&quot;</name> <uri>https://zbmath.org/authors/?q=ai:laszlo.szilard</uri> </author> <content type="text">Summary: We investigate the strong convergence properties of a Nesterov type algorithm with two Tikhonov regularization terms in connection to the minimization problem of a smooth convex function \(f\). We show that the generated sequences converge strongly to the minimal norm element from \(\text{argmin}f\). We also show fast convergence for the potential energies \(f(x_n)-\min f\) and \(f(y_n)-\min f\), where \((x_n)\), \((y_n)\) are the sequences generated by our algorithm. Further we obtain fast convergence to zero of the discrete velocity and some estimates concerning the value of the gradient of the objective function in the generated sequences. Via some numerical experiments we show that we need both Tikhonov regularization terms in our algorithm in order to obtain the strong convergence of the generated sequences to the minimum norm minimizer of our objective function.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">A nonmonotone accelerated proximal gradient method with variable stepsize strategy for nonsmooth and nonconvex minimization problems</title> <id>https://zbmath.org/1553.90060</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90060" /> <author> <name>&quot;Liu, Hongwei&quot;</name> <uri>https://zbmath.org/authors/?q=ai:liu.hongwei</uri> </author> <author> <name>&quot;Wang, Ting&quot;</name> <uri>https://zbmath.org/authors/?q=ai:wang.ting.5</uri> </author> <author> <name>&quot;Liu, Zexian&quot;</name> <uri>https://zbmath.org/authors/?q=ai:liu.zexian</uri> </author> <content type="text">Summary: In this paper, we consider the problem that minimizing the sum of a nonsmooth function with a smooth one in the nonconvex setting, which arising in many contemporary applications such as machine learning, statistics, and signal/image processing. To solve this problem, we propose a new nonmonotone accelerated proximal gradient method with variable stepsize strategy. Note that incorporating inertial term into proximal gradient method is a simple and efficient acceleration technique, while the descent property of the proximal gradient algorithm will lost. In our algorithm, the iterates generated by inertial proximal gradient scheme are accepted when the objective function values decrease or increase appropriately; otherwise, the iteration point is generated by proximal gradient scheme, which makes the function values on a subset of iterates are decreasing. We also introduce a variable stepsize strategy, which does not need a line search or does not need to know the Lipschitz constant and makes the algorithm easy to implement. We show that the sequence of iterates generated by the algorithm converges to a critical point of the objective function. Further, under the assumption that the objective function satisfies the Kurdyka-艁ojasiewicz inequality, we prove the convergence rates of the objective function values and the iterates. Moreover, numerical results on both convex and nonconvex problems are reported to demonstrate the effectiveness and superiority of the proposed method and stepsize strategy.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">A new parameter-free continuously differentiable filled function algorithm for solving nonlinear equations and data fitting problems</title> <id>https://zbmath.org/1553.90061</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90061" /> <author> <name>&quot;Shang, Youlin&quot;</name> <uri>https://zbmath.org/authors/?q=ai:shang.youlin</uri> </author> <author> <name>&quot;Qu, Deqiang&quot;</name> <uri>https://zbmath.org/authors/?q=ai:qu.deqiang</uri> </author> <author> <name>&quot;Li, Junxiang&quot;</name> <uri>https://zbmath.org/authors/?q=ai:li.junxiang</uri> </author> <author> <name>&quot;Zhang, Roxin&quot;</name> <uri>https://zbmath.org/authors/?q=ai:zhang.roxin</uri> </author> <content type="text">Summary: Filled function method, as an efficient method for finding the global minimizer of multimodal functions. It uses alternately classical optimization methods to minimize the objective function and the filled function until the global minimizer of the objective function is obtained. However, many efficient optimization methods based on gradient information cannot be used to minimize the filled function, which is not continuously differentiable. In addition, filled functions often contain parameters that are difficult to adjust. In this paper, a parameter-free continuously differentiable filled function without exponential terms or logarithmic terms and the corresponding filled function algorithm are proposed to overcome these shortcomings. Theoretical analysis and numerical verification show that our algorithm is feasible and effective. Furthermore, the algorithm is applied to solve nonlinear equations and data fitting problems. The numerical results prove the effectiveness of our algorithm. Finally, the advantages and disadvantages of our algorithm are analyzed, and the further research direction is discussed.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Modification and improved implementation of the RPD method for computing state relaxations for global dynamic optimization</title> <id>https://zbmath.org/1553.90062</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90062" /> <author> <name>&quot;Ye, Jason&quot;</name> <uri>https://zbmath.org/authors/?q=ai:ye.jason</uri> </author> <author> <name>&quot;Scott, Joseph K.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:scott.joseph-kirk|scott.joseph-k</uri> </author> <content type="text">Summary: This paper presents an improved method for computing convex and concave relaxations of the parametric solutions of ordinary differential equations (ODEs). These are called state relaxations and are crucial for solving dynamic optimization problems to global optimality via branch-and-bound (B\&amp;B). The new method improves upon an existing approach known as relaxation preserving dynamics (RPD). RPD is generally considered to be among the best available methods for computing state relaxations in terms of both efficiency and accuracy. However, it requires the solution of a hybrid dynamical system, whereas other similar methods only require the solution of a simple system of ODEs. This is problematic in the context of branch-and-bound because it leads to higher cost and reduced reliability (i.e., invalid relaxations can result if hybrid mode switches are not detected numerically). Moreover, there is no known sensitivity theory for the RPD hybrid system. This makes it impossible to compute subgradients of the RPD relaxations, which are essential for efficiently solving the associated B\&amp;B lower bounding problems. To address these limitations, this paper presents a small but important modification of the RPD theory, and a corresponding modification of its numerical implementation, that crucially allows state relaxations to be computed by solving a system of ODEs rather than a hybrid system. This new RPD method is then compared to the original using two examples and shown to be more efficient, more robust, and of almost identical accuracy.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Stochastic variance-reduced prox-linear algorithms for nonconvex composite optimization</title> <id>https://zbmath.org/1553.90063</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90063" /> <author> <name>&quot;Zhang, Junyu&quot;</name> <uri>https://zbmath.org/authors/?q=ai:zhang.junyu</uri> </author> <author> <name>&quot;Xiao, Lin&quot;</name> <uri>https://zbmath.org/authors/?q=ai:xiao.lin</uri> </author> <content type="text">Summary: We consider the problem of minimizing composite functions of the form \(f(g(x))+h(x)\), where \(f\) and \(h\) are convex functions (which can be nonsmooth) and \(g\) is a smooth vector mapping. In addition, we assume that \(g\) is the average of finite number of component mappings or the expectation over a family of random component mappings. We propose a class of stochastic variance-reduced prox-linear algorithms for solving such problems and bound their sample complexities for finding an \(\epsilon \)-stationary point in terms of the total number of evaluations of the component mappings and their Jacobians. When \(g\) is a finite average of \(N\) components, we obtain sample complexity \({\mathcal{O}}(N+ N^{4/5}\epsilon^{-1})\) for both mapping and Jacobian evaluations. When \(g\) is a general expectation, we obtain sample complexities of \({\mathcal{O}}(\epsilon^{-5/2})\) and \({\mathcal{O}}(\epsilon^{-3/2})\) for component mappings and their Jacobians respectively. If in addition \(f\) is smooth, then improved sample complexities of \({\mathcal{O}}(N+N^{1/2}\epsilon^{-1})\) and \({\mathcal{O}}(\epsilon^{-3/2})\) are derived for \(g\) being a finite average and a general expectation respectively, for both component mapping and Jacobian evaluations.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Faster goal-oriented shortest path search for bulk and incremental detailed routing</title> <id>https://zbmath.org/1553.90064</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90064" /> <author> <name>&quot;Ahrens, Markus&quot;</name> <uri>https://zbmath.org/authors/?q=ai:ahrens.markus</uri> </author> <author> <name>&quot;Henke, Dorothee&quot;</name> <uri>https://zbmath.org/authors/?q=ai:henke.dorothee</uri> </author> <author> <name>&quot;Rabenstein, Stefan&quot;</name> <uri>https://zbmath.org/authors/?q=ai:rabenstein.stefan</uri> </author> <author> <name>&quot;Vygen, Jens&quot;</name> <uri>https://zbmath.org/authors/?q=ai:vygen.jens</uri> </author> <content type="text">Summary: We develop new algorithmic techniques for VLSI detailed routing. First, we improve the goal-oriented version of Dijkstra's algorithm to find shortest paths in huge incomplete grid graphs with edge costs depending on the direction and the layer, and possibly on rectangular regions. We devise estimates of the distance to the targets that offer better trade-offs between running time and quality than previously known methods, leading to an overall speed-up. Second, we combine the advantages of the two classical detailed routing approaches -- global shortest path search and track assignment with local corrections -- by treating input wires (such as the output of track assignment) as reservations that can be used at a discount by the respective net. We show how to implement this new approach efficiently.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">The simultaneous semi-random model for TSP</title> <id>https://zbmath.org/1553.90065</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90065" /> <author> <name>&quot;Balkanski, Eric&quot;</name> <uri>https://zbmath.org/authors/?q=ai:balkanski.eric</uri> </author> <author> <name>&quot;Faenza, Yuri&quot;</name> <uri>https://zbmath.org/authors/?q=ai:faenza.yuri</uri> </author> <author> <name>&quot;Kubik, Mathieu&quot;</name> <uri>https://zbmath.org/authors/?q=ai:kubik.mathieu</uri> </author> <content type="text">Summary: Worst-case analysis is a performance measure that is often too pessimistic to indicate which algorithms we should use in practice. A classical example is in the context of the Euclidean Traveling Salesman Problem (TSP) in the plane, where local search performs very well in practice even though it only achieves an \(\Omega (\frac{\log n}{\log \log n})\) worst-case approximation ratio. In such cases, a natural alternative approach to worst-case analysis is to analyze the performance of algorithms in semi-random models. In this paper, we propose and investigate a novel semi-random model for the Euclidean TSP. In this model, called the simultaneous semi-random model, an instance over \(n\) points consists of the union of an adversarial instance over \((1-\alpha )n\) points and a random instance over \(\alpha n\) points, for some \(\alpha \in [0, 1]\). As with smoothed analysis, the semi-random model interpolates between distributional (random) analysis when \(\alpha = 1\) and worst-case analysis when \(\alpha = 0\). In contrast to smoothed analysis, this model trades off allowing some completely random points in order to have other points that exhibit a fully arbitrary structure. We show that with only an \(\alpha = \frac{1}{\log n}\) fraction of the points being random, local search achieves an \(\mathcal{O}(\log \log n)\) approximation in the simultaneous semi-random model for Euclidean TSP in fixed dimensions. On the other hand, we show that at least a polynomial number of random points are required to obtain an asymptotic improvement in the approximation ratio of local search compared to its worst-case approximation, even in two dimensions.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Algorithm for solving the knapsack problem with certain properties of Pareto layers</title> <id>https://zbmath.org/1553.90066</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90066" /> <author> <name>&quot;Chebakov, Serge沫 Viktorovich&quot;</name> <uri>https://zbmath.org/authors/?q=ai:chebakov.sergei-viktorovich</uri> </author> <author> <name>&quot;Serebryanaya, Liya Valentinovna&quot;</name> <uri>https://zbmath.org/authors/?q=ai:serebryanaya.liya-valentinovna</uri> </author> <content type="text">Summary: An algorithm for solving the knapsack problem based on the proposed multicriteria model has been developed. The structure of admissible subsets is presented for the value of the non-dominance depth of the Pareto layer equal to zero. The sum of the resource of the elements of this layer is greater than or equal to the value of the volume of the knapsack. Based on the structure, the form of the optimal admissible subset with the maximum total value of the weight of its elements is determined. It is shown that at a certain stage the developed algorithm includes the solution of a number of knapsack subtasks. Their knapsack volumes are smaller than in the original problem with input data sets. The definition of the redundancy of the set of initial data and the condition for the existence of redundancy for a given value of the depth of non-dominance of the Pareto layer are introduced.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Fast map matching with vertex-monotone Fr茅chet distance</title> <id>https://zbmath.org/1553.90067</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90067" /> <author> <name>&quot;Chen, Daniel&quot;</name> <uri>https://zbmath.org/authors/?q=ai:chen.daniel-i-li|chen.daniel-c|chen.daniel-l|chen.daniel-t-n</uri> </author> <author> <name>&quot;Sommer, Christian&quot;</name> <uri>https://zbmath.org/authors/?q=ai:sommer.christian</uri> </author> <author> <name>&quot;Wolleb, Daniel&quot;</name> <uri>https://zbmath.org/authors/?q=ai:wolleb.daniel</uri> </author> <content type="text">Summary: We study a generalization for map matching algorithms that includes both geometric approaches such as the Fr茅chet distance and global weight approaches such as those typically used by Hidden Markov Models. Through this perspective, we discovered an efficient map matching algorithm with respect to the vertex-monotone Fr茅chet distance while using a heuristic tie-breaker inspired by global weight methods. While the classical Fr茅chet distance requires parameterizations to be monotone, the vertex-monotone Fr茅chet distance allows backtracking within edges. Our analysis and experimental evaluations show that relaxing the monotonicity constraint enables significantly faster algorithms without significantly altering the resulting map matched paths. For the entire collection see [Zbl 1473.90002].</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Optimal item pricing in online combinatorial auctions</title> <id>https://zbmath.org/1553.90068</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90068" /> <author> <name>&quot;Correa, Jos茅&quot;</name> <uri>https://zbmath.org/authors/?q=ai:correa.jose-r</uri> </author> <author> <name>&quot;Cristi, Andr茅s&quot;</name> <uri>https://zbmath.org/authors/?q=ai:cristi.andres</uri> </author> <author> <name>&quot;Fielbaum, Andr茅s&quot;</name> <uri>https://zbmath.org/authors/?q=ai:fielbaum.andres</uri> </author> <author> <name>&quot;Pollner, Tristan&quot;</name> <uri>https://zbmath.org/authors/?q=ai:pollner.tristan</uri> </author> <author> <name>&quot;Weinberg, S. Matthew&quot;</name> <uri>https://zbmath.org/authors/?q=ai:weinberg.seth-matthew</uri> </author> <content type="text">Summary: We consider a fundamental pricing problem in combinatorial auctions. We are given a set of indivisible items and a set of buyers with randomly drawn monotone valuations over subsets of items. A decision-maker sets item prices and then the buyers make sequential purchasing decisions, taking their favorite set among the remaining items. We parametrize an instance by \(d\), the size of the largest set a buyer may want. Our main result asserts that there exist prices such that the expected (over the random valuations) welfare of the allocation they induce is at least a factor \(1/(d+1)\) times the expected optimal welfare in hindsight. Moreover, we prove that this bound is tight. Thus, our result not only improves upon the \(1/(4d-2)\) bound of D眉tting et al., but also settles the approximation that can be achieved by using item prices. The existence of these prices follows from the existence of a fixed point of a related mapping, and therefore, it is non-constructive. However, we show how to compute such a fixed point in polynomial time, even if we only have sample access to the valuation distributions. We provide additional results for the special case when buyers' valuations are known (but a posted-price mechanism is still desired), and an improved impossibility result for the special case of prophet inequalities for bipartite matching.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Assignment based resource constrained path generation for railway rolling stock optimization</title> <id>https://zbmath.org/1553.90069</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90069" /> <author> <name>&quot;Grimm, Boris&quot;</name> <uri>https://zbmath.org/authors/?q=ai:grimm.boris</uri> </author> <author> <name>&quot;Bornd枚rfer, Ralf&quot;</name> <uri>https://zbmath.org/authors/?q=ai:borndorfer.ralf</uri> </author> <author> <name>&quot;Bushe, Julian&quot;</name> <uri>https://zbmath.org/authors/?q=ai:bushe.julian</uri> </author> <content type="text">Summary: The fundamental task of every passenger railway operator is to offer an attractive railway timetable to the passengers while operating it as cost efficiently as possible. The available rolling stock has to be assigned to trips so that all trips are operated, operational requirements are satisfied, and the operating costs are minimum. This so-called Rolling Stock Rotation Problem (RSRP) is well studied in the literature.\par In this paper we consider an acyclic version of the RSRP that includes vehicle maintenance. As the latter is an important aspect, maintenance services have to be planned simultaneously to ensure the rotation's feasibility in practice. Indeed, regular maintenance is important for the safety and reliability of the rolling stock as well as enforced by law in many countries. We present a new integer programming formulation that links a hyperflow to model vehicle compositions and their coupling decisions to a set of path variables that take care of the resource consumption of the individual vehicles. To solve the model we developed different column generation algorithms which are compared to each other as well as to the MILP flow formulation of [\textit{R. Bornd枚rfer} et al., Transp. Sci., 50, No. 3, 863--877 (2015; \url{doi:10.1287/trsc.2015.0633}] on a test set of real world instances. For the entire collection see [Zbl 1520.90003].</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Approximating sparse quadratic programs</title> <id>https://zbmath.org/1553.90070</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90070" /> <author> <name>&quot;Hermelin, Danny&quot;</name> <uri>https://zbmath.org/authors/?q=ai:hermelin.danny</uri> </author> <author> <name>&quot;Kellerhals, Leon&quot;</name> <uri>https://zbmath.org/authors/?q=ai:kellerhals.leon</uri> </author> <author> <name>&quot;Niedermeier, Rolf&quot;</name> <uri>https://zbmath.org/authors/?q=ai:niedermeier.rolf</uri> </author> <author> <name>&quot;Pugatch, Rami&quot;</name> <uri>https://zbmath.org/authors/?q=ai:pugatch.rami</uri> </author> <content type="text">Summary: Given a matrix \(A \in \mathbb{R}^{n \times n}\), we consider the problem of maximizing \(x^T Ax\) subject to the constraint \(x \in \{-1, 1\}^n\). This problem, called \textsc{MaxQP} by \textit{M. Charikar} and \textit{A. Wirth} [FOCS 2004, 54--60 (2004; \url{doi: 10.1109/FOCS.2004.39.}], generalizes \textsc{MaxCut} and has natural applications in data clustering and in the study of disordered magnetic phases of matter. Charikar and Wirth showed that the problem admits an \(\Omega(1 / \lg n)\) approximation via semidefinite programming, and \textit{N. Alon} et al. [in: Proceedings of the 37th annual ACM symposium on theory of computing, STOC'05. Baltimore, MD, USA, May 22--24, 2005. New York, NY: Association for Computing Machinery (ACM). 486--493 (2005; Zbl 1192.05168)] showed that the same approach yields an \(\Omega(1)\) approximation when \(A\) corresponds to a graph of bounded chromatic number. Both these results rely on solving the semidefinite relaxation of \textsc{MaxQP}, whose currently best running time is \(\tilde{O}(n^{1.5} \cdot \min \{N, n^{1.5}\})\), where \(N\) is the number of nonzero entries in \(A\) and \(\tilde{O}\) ignores polylogarithmic factors. In this sequel, we abandon the semidefinite approach and design purely combinatorial approximation algorithms for special cases of \textsc{MaxQP} where \(A\) is sparse (\textit{i.e.}, has \(O(n)\) nonzero entries). Our algorithms are superior to the semidefinite approach in terms of running time, yet are still competitive in terms of their approximation guarantees. More specifically, we show that: \begin{itemize} \item \textsc{MaxQP} admits a \((1/2\Delta)\)-approximation in \(O(n \lg n)\) time, where \(\Delta = O(1)\) is the maximum degree of the corresponding graph. \item \textsc{Unit MaxQP}, where \(A \in \{- 1, 0, 1\}^{n \times n}\), admits a \((1/2d)\)-approximation in \(O(n)\) time when the corresponding graph is \(d\)-degenerate, and a \((1/3\delta)\)-approximation in \(O(n^{1.5})\) time when the corresponding graph has \(\delta n\) edges for \(\delta = O(1)\). \item \textsc{MaxQP} admits a \((1 - \varepsilon)\)-approximation in \(O(n)\) time when the corresponding graph and each of its minors have bounded local treewidth. \item \textsc{Unit MaxQP} admits a \((1 - \varepsilon)\)-approximation in \(O(n^2)\) time for \(H\)-minor free graphs. \end{itemize}</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Limiting the search in brute force method for subsets detection</title> <id>https://zbmath.org/1553.90071</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90071" /> <author> <name>&quot;Kuprijanov, B. V.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:kupriyanov.b-v</uri> </author> <author> <name>&quot;Roschin, A. A.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:roschin.a-a</uri> </author> <content type="text">Summary: A set of methods for limiting the complete enumeration of the number of combinations \(C_n^k\) for \(1\le k\le n\) is proposed. The proposed methods can be used in combinatorial algorithms for calculating subsets of the original set. They are applicable if the calculation of subsets is carried out using a selection function with certain properties. An example of using an algorithm to calculate the set of minimal sections of a graph is considered. It is shown that these methods can be used to solve a number of different \textit{NP}-complete problems. The results of numerical experiments are presented. For the entire collection see [Zbl 1543.90002].</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">New approximation algorithms for the rooted budgeted cycle cover problem</title> <id>https://zbmath.org/1553.90073</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90073" /> <author> <name>&quot;Li, Jiangkun&quot;</name> <uri>https://zbmath.org/authors/?q=ai:li.jiangkun</uri> </author> <author> <name>&quot;Zhang, Peng&quot;</name> <uri>https://zbmath.org/authors/?q=ai:zhang.peng.4</uri> </author> <content type="text">Summary: The rooted \textsf{Budgeted Cycle Cover (BCC)} problem is a fundamental optimization problem arising in wireless sensor networks and vehicle routing. Given a metric space \((V, w)\) with vertex set \(V\) consisting of two parts \(D\) (containing depots) and \(V \setminus D\) (containing nodes), and a budget \(B \geq 0\), the rooted \textsf{BCC} problem asks to find a minimum number of cycles to cover all the nodes in \(V \setminus D\), satisfying that each cycle has length at most \(B\) and each cycle must contain a depot in \(D\). In this paper, we give new approximation algorithms for the rooted \textsf{BCC} problem. For the rooted \textsf{BCC} problem with single depot, we give an \(O(\log \frac{B}{\mu})\)-approximation algorithm, where \(\mu\) is the minimum difference of any two different distances between the vertices in \(V\) and the root. For the rooted \textsf{BCC} problem with multiple depots, we give an \(O(\log n)\)-approximation algorithm, where \(n\) is the number of vertices. We also test our algorithms on the randomly generated instances. The experimental results show that the algorithms have good performance in practice.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">An asymptotically optimal approximation algorithm for the travelling car renter problem</title> <id>https://zbmath.org/1553.90074</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90074" /> <author> <name>&quot;Pedrosa, Lehilton L. C.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:pedrosa.lehilton-lelis-chaves</uri> </author> <author> <name>&quot;Quesqu茅n, Greis Y. O.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:quesquen.greis-y-o</uri> </author> <author> <name>&quot;Schouery, Rafael C. S.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:schouery.rafael-c-s</uri> </author> <content type="text">Summary: In the classical Travelling Salesman Problem (TSP), one wants to find a route that visits a set of \(n\) cities, such that the total travelled distance is minimum. An often considered generalization is the Travelling Car Renter Problem (CaRS), in which the route is travelled by renting a set of cars and the cost to travel between two given cities depends on the car that is used. The car renter may choose to swap vehicles at any city, but must pay a fee to return the car to its pickup location. This problem appears in logistics and urban transportation when the vehicles can be provided by multiple companies, such as in the tourism sector.\par In this paper, we consider the case in which the return fee is some fixed number \(\ge 0\), which we call the Uniform CaRS (UCaRS). We show that, already for this version, there is no \(o(\log n)\)-approximation algorithm unless \(\text{P}=\text{NP}\). The main contribution is an \(O(\log n)\)-approximation algorithm for the problem, which is based on the randomized rounding of an exponentially large LP-relaxation. For the entire collection see [Zbl 1433.90007].</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Optimizing fairness over time with homogeneous workers (short paper)</title> <id>https://zbmath.org/1553.90075</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90075" /> <author> <name>&quot;van Rossum, Bart&quot;</name> <uri>https://zbmath.org/authors/?q=ai:van-rossum.bart</uri> </author> <author> <name>&quot;Chen, Rui&quot;</name> <uri>https://zbmath.org/authors/?q=ai:chen.rui</uri> </author> <author> <name>&quot;Lodi, Andrea&quot;</name> <uri>https://zbmath.org/authors/?q=ai:lodi.andrea</uri> </author> <content type="text">Summary: There is growing interest in including fairness in optimization models. In particular, the concept of fairness over time, or, long-term fairness, is gaining attention. In this paper, we focus on fairness over time in online optimization problems involving the assignment of work to multiple homogeneous workers. This encompasses many real-life problems, including variants of the vehicle routing problem and the crew scheduling problem. The online assignment problem with fairness over time is formally defined. We propose a simple and interpretable assignment policy with some desirable properties. In addition, we perform a case study on the capacitated vehicle routing problem. Empirically, we show that the most cost-efficient solution usually results in unfair assignments while much more fair solutions can be attained with minor efficiency loss using our policy. For the entire collection see [Zbl 1520.90003].</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">An experimental design for comparing interactive methods based on their desirable properties</title> <id>https://zbmath.org/1553.90076</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90076" /> <author> <name>&quot;Afsar, Bekir&quot;</name> <uri>https://zbmath.org/authors/?q=ai:afsar.bekir</uri> </author> <author> <name>&quot;Silvennoinen, Johanna&quot;</name> <uri>https://zbmath.org/authors/?q=ai:silvennoinen.johanna</uri> </author> <author> <name>&quot;Ruiz, Francisco&quot;</name> <uri>https://zbmath.org/authors/?q=ai:ruiz.francisco-javier</uri> </author> <author> <name>&quot;Ruiz, Ana B.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:ruiz.ana-belen</uri> </author> <author> <name>&quot;Misitano, Giovanni&quot;</name> <uri>https://zbmath.org/authors/?q=ai:misitano.giovanni</uri> </author> <author> <name>&quot;Miettinen, Kaisa&quot;</name> <uri>https://zbmath.org/authors/?q=ai:miettinen.kaisa-m</uri> </author> <content type="text">Summary: In multiobjective optimization problems, Pareto optimal solutions representing different tradeoffs cannot be ordered without incorporating preference information of a decision maker (DM). In interactive methods, the DM takes an active part in the solution process and provides preference information iteratively. Between iterations, the DM can learn how achievable the preferences are, learn about the tradeoffs, and adjust the preferences. Different interactive methods have been proposed in the literature, but the question of how to select the best-suited method for a problem to be solved remains partly open. We propose an experimental design for evaluating interactive methods according to several desirable properties related to the cognitive load experienced by the DM, the method's ability to capture preferences and its responsiveness to changes in the preferences, the DM's satisfaction in the overall solution process, and their confidence in the final solution. In the questionnaire designed, we connect each questionnaire item to be asked with a relevant research question characterizing these desirable properties of interactive methods. We also conduct a between-subjects experiment to compare three interactive methods and report interesting findings. In particular, we find out that trade-off-free methods may be more suitable for exploring the whole set of Pareto optimal solutions, while classification-based methods seem to work better for fine-tuning the preferences to find the final solution.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Convergence analysis of a norm minimization-based convex vector optimization algorithm</title> <id>https://zbmath.org/1553.90077</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90077" /> <author> <name>&quot;Ararat, 脟a臒in&quot;</name> <uri>https://zbmath.org/authors/?q=ai:ararat.cagin</uri> </author> <author> <name>&quot;Ulus, Firdevs&quot;</name> <uri>https://zbmath.org/authors/?q=ai:ulus.firdevs</uri> </author> <author> <name>&quot;Umer, Muhammad&quot;</name> <uri>https://zbmath.org/authors/?q=ai:umer.muhammad</uri> </author> <content type="text">Summary: In this work, we propose an outer approximation algorithm for solving bounded convex vector optimization problems (CVOPs). The scalarization model solved iteratively within the algorithm is a modification of the norm-minimizing scalarization proposed in [\textit{脟. Ararat} et al., J. Optim. Theory Appl. 194, No. 2, 681--712 (2022; Zbl 1495.90171)]. For a predetermined tolerance \(\epsilon&gt;0\), we prove that the algorithm terminates after finitely many iterations, and it returns a polyhedral outer approximation to the upper image of the CVOP such that the Hausdorff distance between the two is less than \(\epsilon\). We show that for an arbitrary norm used in the scalarization models, the approximation error after \(k\) iterations decreases by the order of \(\mathcal{O}(k^{1/(1-q)})\), where \(q\) is the dimension of the objective space. An improved convergence rate of \(\mathcal{O}(k^{2/(1-q)})\) is proved for the special case of using the Euclidean norm.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">New mean and median techniques to solve multiobjective linear fractional programming problem and comparison with other techniques</title> <id>https://zbmath.org/1553.90078</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90078" /> <author> <name>&quot;Fentaw, Getaye&quot;</name> <uri>https://zbmath.org/authors/?q=ai:fentaw.getaye</uri> </author> <author> <name>&quot;Akate, Adane&quot;</name> <uri>https://zbmath.org/authors/?q=ai:akate.adane</uri> </author> <content type="text">(no abstract)</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Hybrid response dynamic multi-objective optimization algorithm based on multi-arm bandit model</title> <id>https://zbmath.org/1553.90079</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90079" /> <author> <name>&quot;Hu, Xiaolin&quot;</name> <uri>https://zbmath.org/authors/?q=ai:hu.xiaolin</uri> </author> <author> <name>&quot;Wu, Lingyu&quot;</name> <uri>https://zbmath.org/authors/?q=ai:wu.lingyu</uri> </author> <author> <name>&quot;Han, Mingzhang&quot;</name> <uri>https://zbmath.org/authors/?q=ai:han.mingzhang</uri> </author> <author> <name>&quot;Zhao, Xinchao&quot;</name> <uri>https://zbmath.org/authors/?q=ai:zhao.xinchao</uri> </author> <author> <name>&quot;Sang, Xinzhu&quot;</name> <uri>https://zbmath.org/authors/?q=ai:sang.xinzhu</uri> </author> <content type="text">Summary: Dynamic multi-objective optimization is a relatively challenging problem within the field of multi-objective optimization. Nevertheless, these problems have significant real-world applications. The key to addressing dynamic multi-objective problems effectively is promptly tracking changes in the Pareto set (PS) and Pareto front (PF). Dynamic multi-objective optimization encompasses various types of problems, and a single-type response strategy proves effective for some specific scenarios. However, as problem complexity and diversity increase, a single-type response strategy often falls short in solving dynamic multi-objective optimization problems. To address this issue, this paper proposes a hybrid response dynamic multi-objective optimization algorithm. The suggested algorithm utilizes the multi-arm bandit model to adaptively adjust the proportion of different response strategies for each type of multi-objective optimization problem. Furthermore, it achieves rapid convergence through an enhanced two-stage MOEA/D. Experiments demonstrate the effectiveness of the strategies employed in the proposed algorithm and its competitiveness compared to other state-of-the-art algorithms.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">The generalized conditional gradient method for composite multiobjective optimization problems on Riemannian manifolds</title> <id>https://zbmath.org/1553.90080</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90080" /> <author> <name>&quot;Li, Xiaobo&quot;</name> <uri>https://zbmath.org/authors/?q=ai:li.xiaobo</uri> </author> <author> <name>&quot;Ge, Xiaochun&quot;</name> <uri>https://zbmath.org/authors/?q=ai:ge.xiaochun</uri> </author> <author> <name>&quot;Tu, Kai&quot;</name> <uri>https://zbmath.org/authors/?q=ai:tu.kai</uri> </author> <content type="text">In this paper, the authors study the composite multi-objective optimization problem defined on Riemannian manifolds, whith the objective function $F(x):=(f_1(x),\cdots,f_m(x))$ where $f_j(x):=g_j(x)+h_j(x)$, and $M$ is a Riemannian manifold, $g_j:M\to R$ is proper, convex, and lower semicontinuous, and $h_j:M\to R$ is continuous differentiable. The paper contains the design of the generalized conditional gradient method to solve composite multi-objective optimization problems with Armijo and non-monotone line search step sizes on Riemannian manifolds. Under some reasonable conditions, the authors establish the global convergence of the generalized gradient method for composite multi-objective optimization problems. The iteration-complexity bound on the objective function is also established. Since a Riemannian manifold, in general, does not have a linear structure, usual techniques in the Euclidean space cannot be applied and new techniques must be developed. The results are distinguished from the following aspects: first, it generalizes the generalized conditional gradient method from \(R^n\) to Riemannian manifolds; second, the results can be regarded as a generalization from smooth objective functions to non-smooth objective functions on Riemannian manifolds; third, exponential mappings and parallel transports are extended to retractions and isometric vector transports in this paper, respectively, which makes the method more efficient. Reviewer: Doina Carp (Bucure艧ti)</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Constraint qualifications and optimality criteria for nonsmooth multiobjective programming problems on Hadamard manifolds</title> <id>https://zbmath.org/1553.90081</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90081" /> <author> <name>&quot;Upadhyay, Balendu Bhooshan&quot;</name> <uri>https://zbmath.org/authors/?q=ai:upadhyay.balendu-bhooshan</uri> </author> <author> <name>&quot;Ghosh, Arnav&quot;</name> <uri>https://zbmath.org/authors/?q=ai:ghosh.arnav</uri> </author> <author> <name>&quot;Trean牛膬, Savin&quot;</name> <uri>https://zbmath.org/authors/?q=ai:treanta.savin</uri> </author> <content type="text">The authors consider a class of constrained nonsmooth multi-objective programming problems in the setting of Hadamard manifolds. The Guignard constraint qualification is introduced using the notion of Clarke subdifferentials. By making use of this constraint qualification and geodesic quasiconvexity assumption, Karush-Kuhn-Tucker-type necessary conditions of Pareto efficiency of the considered nonsmooth multi-objective programming problems are established. Some other constraint qualifications are introduced, and proved to be sufficient for satisfaction of the generalized Guignard constraint qualification. The same authors bring at the end numerical examples demonstrating significance of the theoretical results presented in the paper. Reviewer: Karel Zimmermann (Praha)</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">An efficient hybrid conjugate gradient method with an adaptive strategy and applications in image restoration problems</title> <id>https://zbmath.org/1553.90082</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90082" /> <author> <name>&quot;Chen, Zibo&quot;</name> <uri>https://zbmath.org/authors/?q=ai:chen.zibo</uri> </author> <author> <name>&quot;Shao, Hu&quot;</name> <uri>https://zbmath.org/authors/?q=ai:shao.hu</uri> </author> <author> <name>&quot;Liu, Pengjie&quot;</name> <uri>https://zbmath.org/authors/?q=ai:liu.pengjie</uri> </author> <author> <name>&quot;Li, Guoxin&quot;</name> <uri>https://zbmath.org/authors/?q=ai:li.guoxin</uri> </author> <author> <name>&quot;Rong, Xianglin&quot;</name> <uri>https://zbmath.org/authors/?q=ai:rong.xianglin</uri> </author> <content type="text">Summary: In this study, we introduce a novel hybrid conjugate gradient method with an adaptive strategy called asHCG method. The asHCG method exhibits the following characteristics. (i) Its search direction guarantees sufficient descent property without dependence on any line search. (ii) It possesses strong convergence for the uniformly convex function using a weak Wolfe line search, and under the same line search, it achieves global convergence for the general function. (iii) Employing the Armijo line search, it provides an approximate guarantee for worst-case complexity for the uniformly convex function. The numerical results demonstrate promising and encouraging performances in both unconstrained optimization problems and image restoration problems.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Convergence rate of gradient-concordant methods for smooth unconstrained optimization</title> <id>https://zbmath.org/1553.90083</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90083" /> <author> <name>&quot;Chernov, Alexey&quot;</name> <uri>https://zbmath.org/authors/?q=ai:chernov.alexey|chernov.alexey.1|chernov.aleksei-vyacheslavovich|chernov.alexey-a</uri> </author> <author> <name>&quot;Lisachenko, Anna&quot;</name> <uri>https://zbmath.org/authors/?q=ai:lisachenko.anna</uri> </author> <content type="text">Summary: The article discusses the class of gradient-concordant numerical methods for smooth unconstrained minimization where the descent direction is restricted to a subset of the descent cone. This class covers a wide range of well-known optimization methods, such as gradient descent, conjugate gradient method, and Newton's method. While previous research has demonstrated the linear convergence rate of gradient-concordant methods for strongly convex functions, many practical functions do not meet this criterion. Our research explores the convergence of gradient-concordant methods for a broader class of functions. We prove that the Polyak-艁ojasiewicz condition is sufficient for the linear convergence of the gradient-concordant method. Additionally, we show sublinear convergence for convex functions that are not necessarily strongly convex. For the entire collection see [Zbl 1543.90002].</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">A modified PRP conjugate gradient method for unconstrained optimization and nonlinear equations</title> <id>https://zbmath.org/1553.90084</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90084" /> <author> <name>&quot;Cui, Haijuan&quot;</name> <uri>https://zbmath.org/authors/?q=ai:cui.haijuan</uri> </author> <content type="text">Summary: A modified Polak Ribiere Polyak(PRP) conjugate gradient(CG) method is proposed for solving unconstrained optimization problems. The search direction generated by this method satisfies sufficient descent condition at each iteration and this method inherits one remarkable property of the standard PRP method. Under the standard Armijo line search, the global convergence and the linearly convergent rate of the presented method is established. Some numerical results are given to show the effectiveness of the proposed method by comparing with some existing CG methods.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Sequential optimality conditions for optimization problems with additional abstract set constraints</title> <id>https://zbmath.org/1553.90085</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90085" /> <author> <name>&quot;Fazzio, Nadia Soledad&quot;</name> <uri>https://zbmath.org/authors/?q=ai:fazzio.nadia-soledad</uri> </author> <author> <name>&quot;S谩nchez, Mar铆a Daniela&quot;</name> <uri>https://zbmath.org/authors/?q=ai:sanchez.maria-daniela</uri> </author> <author> <name>&quot;Schuverdt, Mar铆a Laura&quot;</name> <uri>https://zbmath.org/authors/?q=ai:schuverdt.maria-laura</uri> </author> <content type="text">Summary: The positive approximate Karush-Kuhn-Tucker sequential condition and the strict constraint qualification associated with this condition for general scalar problems with equality and inequality constraints have recently been introduced. In this paper, we extend them to optimization problems with additional abstract set constraints. We also present an extension of the approximate Karush-Kuhn-Tucker sequential condition and its related strict constraint qualification. Furthermore, we explore the relations between the new constraint qualification and other constraint qualifications known in the literature as Abadie, quasi-normality and the approximate Karush-Kuhn-Tucker regularity constraint qualification. Finally, we introduce an augmented Lagrangian method for solving the optimization problem with abstract set constraints and we show that it is possible to obtain global convergence under the new condition.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">An efficient iterative method for solving the graph regularization Q-weighted nonnegative matrix factorization problem in multi-view clustering</title> <id>https://zbmath.org/1553.90086</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90086" /> <author> <name>&quot;Li, Chunmei&quot;</name> <uri>https://zbmath.org/authors/?q=ai:li.chunmei</uri> </author> <author> <name>&quot;Tian, Dan&quot;</name> <uri>https://zbmath.org/authors/?q=ai:tian.dan</uri> </author> <author> <name>&quot;Duan, Xuefeng&quot;</name> <uri>https://zbmath.org/authors/?q=ai:duan.xuefeng</uri> </author> <author> <name>&quot;Yang, Naya&quot;</name> <uri>https://zbmath.org/authors/?q=ai:yang.naya</uri> </author> <content type="text">Summary: In this paper, we consider the graph regularization Q-weighted nonnegative matrix factorization problem in multi-view clustering. Based on the Q-weighted norm property, this problem is transformed into the minimization problem of the trace function. The necessary condition for the existence of a solution is given. The proximal alternating nonnegative least squares method and its acceleration method are designed to solve it. The convergence theorem is also given. The feasibility and effectiveness of the proposed methods are verified by numerical experiments.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">A double inertial Mann algorithm for split equilibrium problems application to breast cancer screening</title> <id>https://zbmath.org/1553.90087</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90087" /> <author> <name>&quot;Yajai, Watcharaporn&quot;</name> <uri>https://zbmath.org/authors/?q=ai:yajai.watcharaporn</uri> </author> <author> <name>&quot;Nabheerong, Pennipat&quot;</name> <uri>https://zbmath.org/authors/?q=ai:nabheerong.pennipat</uri> </author> <author> <name>&quot;Cholamjiak, Watcharaporn&quot;</name> <uri>https://zbmath.org/authors/?q=ai:cholamjiak.watcharaporn</uri> </author> <content type="text">Summary: We create an algorithm for solving the split equilibrium problems by modifying the double inertial technique with Mann's algorithm. Under some suitable conditions in Hilbert spaces, we prove a weak convergence theorem for the proposed method. Further, the discussions on the applications are also provided to demonstrate the effectiveness of the proposed algorithm by using data classification of two mammographic datasets: one dataset is a mammographic mass dataset on the UCI website, and another is a real dataset in Phayao hospital, Thailand. Experimental results show that the proposed algorithm's accuracy of breast cancer screening is 92.11\% of the UCI dataset, 86.05\% of the Phayao hospital dataset, and 87.88\% of Phayao Hospital with some few data from UCI. Moreover, the high accuracy of the three datasets shows that our algorithm has the highest performance, more than the exits algorithms.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Convergence properties of Newton' method for globally optimal free flight trajectory optimization (short paper)</title> <id>https://zbmath.org/1553.90088</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90088" /> <author> <name>&quot;Bornd枚rfer, Ralf&quot;</name> <uri>https://zbmath.org/authors/?q=ai:borndorfer.ralf</uri> </author> <author> <name>&quot;Danecker, Fabian&quot;</name> <uri>https://zbmath.org/authors/?q=ai:danecker.fabian</uri> </author> <author> <name>&quot;Weiser, Martin&quot;</name> <uri>https://zbmath.org/authors/?q=ai:weiser.martin</uri> </author> <content type="text">Summary: The algorithmic efficiency of Newton-based methods for Free Flight Trajectory Optimization is heavily influenced by the size of the domain of convergence. We provide numerical evidence that the convergence radius is much larger in practice than what the theoretical worst case bounds suggest. The algorithm can be further improved by a convergence-enhancing domain decomposition. For the entire collection see [Zbl 1520.90003].</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Customizable contraction hierarchies with turn costs</title> <id>https://zbmath.org/1553.90089</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90089" /> <author> <name>&quot;Buchhold, Valentin&quot;</name> <uri>https://zbmath.org/authors/?q=ai:buchhold.valentin</uri> </author> <author> <name>&quot;Wagner, Dorothea&quot;</name> <uri>https://zbmath.org/authors/?q=ai:wagner.dorothea</uri> </author> <author> <name>&quot;Zeitz, Tim&quot;</name> <uri>https://zbmath.org/authors/?q=ai:zeitz.tim</uri> </author> <author> <name>&quot;Z眉ndorf, Michael&quot;</name> <uri>https://zbmath.org/authors/?q=ai:zundorf.michael</uri> </author> <content type="text">Summary: We incorporate turn restrictions and turn costs into the route planning algorithm customizable contraction hierarchies (CCH). There are two common ways to represent turn costs and restrictions. The edge-based model expands the network so that road segments become vertices and allowed turns become edges. The compact model keeps intersections as vertices, but associates a turn table with each vertex. Although CCH can be used as is on the edge-based model, the performance of preprocessing and customization is severely affected. While the expanded network is only three times larger, both preprocessing and customization time increase by up to an order of magnitude. In this work, we carefully engineer CCH to exploit different properties of the expanded graph. We reduce the increase in customization time from up to an order of magnitude to a factor of about 3. The increase in preprocessing time is reduced even further.\par Moreover, we present a CCH variant that works on the compact model, and show that it performs worse than the variant on the edge-based model. Surprisingly, the variant on the edge-based model even uses less space than the one on the compact model, although the compact model was developed to keep the space requirement low. For the entire collection see [Zbl 1451.90004].</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} time</title> <id>https://zbmath.org/1553.90090</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90090" /> <author> <name>&quot;Cohen-Addad, Vincent&quot;</name> <uri>https://zbmath.org/authors/?q=ai:cohen-addad.vincent</uri> </author> <author> <name>&quot;M枚mke, Tobias&quot;</name> <uri>https://zbmath.org/authors/?q=ai:momke.tobias</uri> </author> <author> <name>&quot;Verdugo, Victor&quot;</name> <uri>https://zbmath.org/authors/?q=ai:verdugo.victor</uri> </author> <content type="text">Summary: In the non-uniform sparsest cut problem, we are given a supply graph \(G\) and a demand graph \(D\), both with the same set of nodes \(V\). The goal is to find a cut of \(V\) that minimizes the ratio of the total capacity on the edges of \(G\) crossing the cut over the total demand of the crossing edges of \(D\). In this work, we study the non-uniform sparsest cut problem for supply graphs with bounded treewidth \(k\). For this case, \textit{A. Gupta} et al. [in: Proceedings of the 45th annual ACM symposium on theory of computing, STOC '13. Palo Alto, CA, USA, June 1--4, 2013. New York, NY: Association for Computing Machinery (ACM). 281--290 (2013; Zbl 1293.05042)] obtained a 2-approximation with polynomial running time for fixed \(k\), and it remained open the question of whether there exists a \(c\)-approximation algorithm for a constant \(c\) independent of \(k\), that runs in \textsf{FPT} time. We answer this question in the affirmative. We design a 2-approximation algorithm for the non-uniform sparsest cut with bounded treewidth supply graphs that runs in \textsf{FPT} time, when parameterized by the treewidth. Our algorithm is based on rounding the optimal solution of a linear programming relaxation inspired by the Sherali-Adams hierarchy. In contrast to the classic Sherali-Adams approach, we construct a relaxation driven by a tree decomposition of the supply graph by including a carefully chosen set of lifting variables and constraints to encode information of subsets of nodes with super-constant size, and at the same time we have a sufficiently small linear program that can be solved in \textsf{FPT} time.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Shortest path reoptimization vs resolution from scratch: a computational comparison</title> <id>https://zbmath.org/1553.90091</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90091" /> <author> <name>&quot;Festa, Paola&quot;</name> <uri>https://zbmath.org/authors/?q=ai:festa.paola</uri> </author> <author> <name>&quot;Fugaro, Serena&quot;</name> <uri>https://zbmath.org/authors/?q=ai:fugaro.serena</uri> </author> <author> <name>&quot;Guerriero, Francesca&quot;</name> <uri>https://zbmath.org/authors/?q=ai:guerriero.francesca</uri> </author> <content type="text">Summary: The Shortest Path Problem (SPP) is among the most studied problems in Operations Research, for its theoretical aspects but also because it appears as sub-problem in many combinatorial optimization problems, e.g. Vehicle Routing and Maximum Flow-Minimum Cost problems. Given a sequence of SPPs, suppose that two subsequent instances solely differ by a slight change in the graph structure: that is the set of nodes, the set of arcs or both have changed; then, the goal of the reoptimization consists in solving the \(k^{th}\) SPP of the sequence by reusing valuable information gathered in the solution of the \((k-1)^{th}\) one. We focused on the most general scenario, i.e. multiple changes for any subset of arcs, for which, only the description of a dual-primal approach has been proposed so far [\textit{S. Pallottino} and \textit{M. G. Scutell脿}, Oper. Res. Lett. 31, No. 2, 149--160 (2003; Zbl 1041.90062)]. We implemented this framework exploiting efficient data structures, i.e. the Multi Level Bucket. In addition, we compare the performance of our proposal with the well-known Dijkstra's algorithm, applied for solving each modified problem from scratch. In this way, we draw the line -- in terms of cost, topology, and size -- among the instances where the reoptimization approach is efficient from those that should be solved from scratch.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Robustness generalizations of the shortest feasible path problem for electric vehicles</title> <id>https://zbmath.org/1553.90092</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90092" /> <author> <name>&quot;Rajan, Payas&quot;</name> <uri>https://zbmath.org/authors/?q=ai:rajan.payas</uri> </author> <author> <name>&quot;Baum, Moritz&quot;</name> <uri>https://zbmath.org/authors/?q=ai:baum.moritz</uri> </author> <author> <name>&quot;Wegner, Michael&quot;</name> <uri>https://zbmath.org/authors/?q=ai:wegner.michael</uri> </author> <author> <name>&quot;Z眉ndorf, Tobias&quot;</name> <uri>https://zbmath.org/authors/?q=ai:zundorf.tobias</uri> </author> <author> <name>&quot;West, Christian J.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:west.christian-j</uri> </author> <author> <name>&quot;Schieferdecker, Dennis&quot;</name> <uri>https://zbmath.org/authors/?q=ai:schieferdecker.dennis</uri> </author> <author> <name>&quot;Delling, Daniel&quot;</name> <uri>https://zbmath.org/authors/?q=ai:delling.daniel</uri> </author> <content type="text">Summary: Electric Vehicle routing is often modeled as a Shortest Feasible Path Problem (SFPP), which minimizes total travel time while maintaining a non-zero State of Charge (SoC) along the route. However, the problem assumes perfect information about energy consumption and charging stations, which are difficult to even estimate in practice. Further, drivers might have varying risk tolerances for different trips. To overcome these limitations, we propose two generalizations to the SFPP; they compute the shortest feasible path for any initial SoC and, respectively, for every possible minimum SoC threshold. We present algorithmic solutions for each problem, and provide two constructs: Starting Charge Maps and Buffer Maps, which represent the tradeoffs between robustness of feasible routes and their travel times.\par The two constructs are useful in many ways, including presenting alternate routes or providing charging prompts to users. We evaluate the performance of our algorithms on realistic input instances. For the entire collection see [Zbl 1473.90002].</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Subproblem separation in logic-based Benders' decomposition for the vehicle routing problem with local congestion</title> <id>https://zbmath.org/1553.90093</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90093" /> <author> <name>&quot;Saken, Aigerim&quot;</name> <uri>https://zbmath.org/authors/?q=ai:saken.aigerim</uri> </author> <author> <name>&quot;Maher, Stephen J.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:maher.stephen-j</uri> </author> <content type="text">Summary: Subproblem separation is a common strategy for the acceleration of the logic-based Benders' decomposition (LBBD). However, it has only been applied to problems with an inherently separable subproblem structure. This paper proposes a new method to separate the subproblem using the connected components algorithm. The subproblem separation is applied to the vehicle routing problem with local congestion (VRPLC). Accordingly, new Benders' cuts are derived for the new subproblem formulation. The computational experiments evaluate the effectiveness of subproblem separation for different methods applying new cuts. It is shown that subproblem separation significantly benefits the LBBD scheme. For the entire collection see [Zbl 1520.90003].</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Enhanced non-dominated sorting genetic algorithms for uncertain multi-objective shortest path problem: application to fire prevention services</title> <id>https://zbmath.org/1553.90094</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90094" /> <author> <name>&quot;Todkar, Aniket S.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:todkar.aniket-s</uri> </author> <author> <name>&quot;Dhodiya, Jayesh M.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:dhodiya.jayesh-m</uri> </author> <content type="text">Summary: This paper examines a multi-objective shortest path problem (MOSPP) under an uncertain environment for a directed graph. The zigzag uncertain variables are used to represent the uncertain parameters. The expected and optimistic value models of uncertain MOSPP (UMOSPP) have been formulated, and their correlated deterministic transformation is also provided. Moreover, using three existing multi-objective genetic algorithms (MOGAs) and two proposed aspiration level (AL) based algorithms: AL-based non-dominated sorting genetic algorithm (NSGA)-II, and AL-based NSGA-III, the deterministic models are solved. As an application, a mock fire drill problem has been considered in the context of UMOSPP. A comparison is presented between the proposed methods and several MOGAs. A sensitivity analysis of objective functions has also been carried out regarding the shape parameter and aspiration level. Finally, to show the effectiveness of the proposed methods, the performance measure coverage is calculated.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">An improved transformer model with multi-head attention and attention to attention for low-carbon multi-depot vehicle routing problem</title> <id>https://zbmath.org/1553.90095</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90095" /> <author> <name>&quot;Zou, Yang&quot;</name> <uri>https://zbmath.org/authors/?q=ai:zou.yang</uri> </author> <author> <name>&quot;Wu, Hecheng&quot;</name> <uri>https://zbmath.org/authors/?q=ai:wu.hecheng</uri> </author> <author> <name>&quot;Yin, Yunqiang&quot;</name> <uri>https://zbmath.org/authors/?q=ai:yin.yunqiang</uri> </author> <author> <name>&quot;Dhamotharan, Lalitha&quot;</name> <uri>https://zbmath.org/authors/?q=ai:dhamotharan.lalitha</uri> </author> <author> <name>&quot;Chen, Daqiang&quot;</name> <uri>https://zbmath.org/authors/?q=ai:chen.daqiang</uri> </author> <author> <name>&quot;Tiwari, Aviral Kumar&quot;</name> <uri>https://zbmath.org/authors/?q=ai:tiwari.aviral-kumar</uri> </author> <content type="text">Summary: Low-carbon logistics is an emerging and sustainable development industry in the era of a low-carbon economy. The end-to-end deep reinforcement learning (DRL) method with an encoder-decoder framework has been proven effective for solving logistics problems. However, in most cases, the recurrent neural networks (RNN) and attention mechanisms are used in encoders and decoders, which may result in the long-distance dependence problem and the neglect of the correlation between query vectors. To surround this problem, we propose an improved transformer model (TAOA) with both multi-head attention mechanism (MHA) and attention to attention mechanism (AOA), and apply it to solve the low-carbon multi-depot vehicle routing problem (MDVRP). In this model, the MHA and AOA are implemented to solve the probability of route nodes in the encoder and decoder. The MHA is used to process different parts of the input sequence, which can be calculated in parallel, and the AOA is used to deal with the deficiency problem of correlation between query results and query vectors in the MHA. The actor-critic framework based on strategy gradient is constructed to train model parameters. The 2opt operator is further used to optimize the resulting routes. Finally, extensive numerical studies are carried out to verify the effectiveness and operation efficiency of the proposed TAOA, and the results show that the proposed TAOA performs better in solving the MDVRP than the traditional transformer model (Kools), genetic algorithm (GA), and Google OR-Tools (Ortools).</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Continuous-time mean field Markov decision models</title> <id>https://zbmath.org/1553.90096</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90096" /> <author> <name>&quot;B盲uerle, Nicole&quot;</name> <uri>https://zbmath.org/authors/?q=ai:bauerle.nicole</uri> </author> <author> <name>&quot;H枚fer, Sebastian&quot;</name> <uri>https://zbmath.org/authors/?q=ai:hofer.sebastian-g</uri> </author> <content type="text">Summary: We consider a finite number of \(N\) statistically equal agents, each moving on a finite set of states according to a continuous-time Markov Decision Process (MDP). Transition intensities of the agents and generated rewards depend not only on the state and action of the agent itself, but also on the states of the other agents as well as the chosen action. Interactions like this are typical for a wide range of models in e.g. biology, epidemics, finance, social science and queueing systems among others. The aim is to maximize the expected discounted reward of the system, i.e. the agents have to cooperate as a team. Computationally this is a difficult task when \(N\) is large. Thus, we consider the limit for \(N\rightarrow \infty\). In contrast to other papers we treat this problem from an MDP perspective. This has the advantage that we need less regularity assumptions in order to construct asymptotically optimal strategies than using viscosity solutions of HJB equations. The convergence rate is \(1/\sqrt{N} \). We show how to apply our results using two examples: a machine replacement problem and a problem from epidemics. We also show that optimal feedback policies from the limiting problem are not necessarily asymptotically optimal.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Finding algorithm of optimal subset structure based on the Pareto layers in the knapsack problem</title> <id>https://zbmath.org/1553.90097</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90097" /> <author> <name>&quot;Chebakov, Serge沫 Viktorovich&quot;</name> <uri>https://zbmath.org/authors/?q=ai:chebakov.sergei-viktorovich</uri> </author> <author> <name>&quot;Serebryanaya, Liya Valentinovna&quot;</name> <uri>https://zbmath.org/authors/?q=ai:serebryanaya.liya-valentinovna</uri> </author> <content type="text">Summary: An algorithm is developed for finding the structure of the optimal subset in the knapsack problem based on the proposed multicriteria optimization model. A two-criteria relation of preference between elements of the set of initial data is introduced. This set has been split into separate Pareto layers. The depth concept of the elements dominance of an individual Pareto layer is formulated. Based on it, conditions are determined under which the solution to the knapsack problem includes the first Pareto layers. They are defined on a given set of initial data. The structure of the optimal subset is presented, which includes individual Pareto layers. Pareto layers are built in the introduced preference space. This does not require algorithms for enumerating the elements of the initial set. Such algorithms are used when finding only some part of the optimal subset. This reduces the number of operations required to solve the considered combinatorial problem. The method for determining the found Pareto layers shows that the number of operations depends on the volume of the knapsack and the structure of the Pareto layers, into which the set of initial data in the entered two-criteria space is divided.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">The maximum 2D subarray polytope: facet-inducing inequalities and polyhedral computations</title> <id>https://zbmath.org/1553.90098</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90098" /> <author> <name>&quot;Koch, Ivo&quot;</name> <uri>https://zbmath.org/authors/?q=ai:koch.ivo</uri> </author> <author> <name>&quot;Marenco, Javier&quot;</name> <uri>https://zbmath.org/authors/?q=ai:marenco.javier-l</uri> </author> <content type="text">Summary: Given a matrix with real-valued entries, the \textit{maximum 2D subarray problem} consists in finding a rectangular submatrix with consecutive rows and columns maximizing the sum of its entries. In this work we start a polyhedral study of an integer programming formulation for this problem. We thus define the \textit{2D subarray polytope}, explore conditions ensuring the validity of linear inequalities, and provide several families of facet-inducing inequalities. We also report computational experiments assessing the reduction of the dual bound for the linear relaxation achieved by these families of inequalities.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Research on the hybrid chaos-coud salp swarm algorithm</title> <id>https://zbmath.org/1553.90099</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90099" /> <author> <name>&quot;Dai, Junfeng&quot;</name> <uri>https://zbmath.org/authors/?q=ai:dai.junfeng</uri> </author> <author> <name>&quot;Fu, Li-hui&quot;</name> <uri>https://zbmath.org/authors/?q=ai:fu.lihui</uri> </author> <content type="text">Summary: Salp swarm algorithm (SSA) is a new swarm intelligence optimization algorithm, which has the advantages of simple structure, almost no parameter setting. However, SSA also has the shortcomings of slow convergence speed in the early stage and low optimization accuracy in the later stage when searching for the optimal solution. To address the problems, this study proposes a hybrid chaos-cloud salp swarm algorithm (CC-SSA). First, to accelerate the convergence speed, a positive normal cloud generator is used to perform local search on the superior salp individuals. Second, to enhance the diversity of CC-SSA and avoid it from falling into local optimum, the chaotic map is used to perform global search on the inferior salp individuals by adding global perturbation. Third, to control the execution ratio of global and local search, the mixed control parameter \((\mathrm{ML}_{\mathrm{MS}})\) and population allocation coefficient \((r)\) are introduced to organically combine three algorithms, SSA, chaotic map, and cloud model. Finally, to evaluate the performance of the proposed algorithm, it is compared with other 9 conventional algorithms on 12 classic functions. The experimental results show that CC-SSA has an average accuracy rate of 92.92\%, which ranks first. In addition, the average iteration of CC-SSA scores the third. Therefore, compared to conventional optimization algorithms, CC-SSA has better performance in terms of execution time and optimize accuracy.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">An integrated production planning and inventory management problem for a perishable product: optimization and Monte Carlo simulation as a tool for planning in scenarios with uncertain demands</title> <id>https://zbmath.org/1553.90100</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.90100" /> <author> <name>&quot;da Cruz, Jeferson Auto&quot;</name> <uri>https://zbmath.org/authors/?q=ai:da-cruz.jeferson-auto</uri> </author> <author> <name>&quot;de Salles-Neto, Luiz Leduino&quot;</name> <uri>https://zbmath.org/authors/?q=ai:de-salles-neto.luiz-leduino</uri> </author> <author> <name>&quot;Schenekemberg, Cleder Marcos&quot;</name> <uri>https://zbmath.org/authors/?q=ai:schenekemberg.cleder-marcos</uri> </author> <content type="text">Summary: This paper addresses a novel problem inspired by a practical situation faced by a Brazilian dairy company, which presents the integration of production and a two-level storage inventory control. In the supply chain (SC) analyzed, multiple production plants, warehouses, and distribution centers are considered. The problem also involves a set of constraints related to logistical capabilities and conditions of material flow throughout the SC. We developed a mathematical model and a Monte Carlo Simulation routine that aims to assist managers in establishing a production and inventory management plan for a perishable product, considering a stochastic and non-stationary demand. A numerical illustration of the results obtained by the mathematical model and a case study are carried out on the consideration of a First-Expired, First-Out inventory management policy. Results demonstrate that the proposed method allows the analysis of safety stock and the achievement of desired service levels while promoting a reduced rate of food waste over the considered planning horizon.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Truthful mechanism design for cooperative cost sharing and congestion games</title> <id>https://zbmath.org/1553.91006</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.91006" /> <author> <name>&quot;Brenner, Janina&quot;</name> <uri>https://zbmath.org/authors/?q=ai:brenner.janina-a</uri> </author> <content type="text">Summary: As the world is growing closer together, more and more infrastructures are installed and used jointly by several participants. The area of algorithmic game theory develops and analyzes models to describe and control the behavior of selfish and strategic individuals in such situations. This thesis studies two game theoretic models whose instances are based on combinatorial optimization problems such as the cost minimal installation of an energy network or routing of goods or information from one point to another. Our first model studies mechanisms for distributing the cost of a newly installed infrastructure among its users. Every potential user is asked to submit a bid corresponding to her private valuation of and thus her willingness to pay for using the infrastructure. Based on these bids, the cost sharing mechanism chooses a global outcome for a subset of the bidders and determines an individual payment for every user. We are interested in truthful mechanisms that guarantee that no bidder can benefit from misreporting her valuation. Additionally, we aim at minimizing the social cost of the solution. We develop such cost sharing mechanisms for several combinatorial optimization problems from the areas of network design and scheduling. This is done under two different assumptions regarding the degree of cooperation under which players form strategies to manipulate the outcome. We prove general inapproximability results for the stronger cooperation model, which yield strong lower bounds especially for scheduling problems. We then overcome these lower bounds surprisingly well in the second, slightly weaker cooperation model. Further, we develop the first general online model for cooperative cost sharing and characterize truthful mechanisms in this model. In the last part of the thesis, we present a new model which allows to incorporate the disutility caused by congestion on shared resources. This is an important extension of the standard mechanism design approach, as congestion effects occur in many applications. We base our model on congestion games, which have so far mainly been studied in the context of Nash equilibria. We develop a generic mechanism that approximates social welfare in general, while producing optimal solutions in the case of single commodity network congestion games.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Life is random, time is not: Markov decision processes with window objectives</title> <id>https://zbmath.org/1553.91030</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.91030" /> <author> <name>&quot;Brihaye, Thomas&quot;</name> <uri>https://zbmath.org/authors/?q=ai:brihaye.thomas</uri> </author> <author> <name>&quot;Delgrange, Florent&quot;</name> <uri>https://zbmath.org/authors/?q=ai:delgrange.florent</uri> </author> <author> <name>&quot;Oualhadj, Youssouf&quot;</name> <uri>https://zbmath.org/authors/?q=ai:oualhadj.youssouf</uri> </author> <author> <name>&quot;Randour, Mickael&quot;</name> <uri>https://zbmath.org/authors/?q=ai:randour.mickael</uri> </author> <content type="text">Summary: The window mechanism was introduced by \textit{K. Chatterjee} et al. [Inf. Comput. 242, 25--52 (2015; Zbl 1317.68065)] to strengthen classical game objectives with time bounds. It permits to synthesize system controllers that exhibit acceptable behaviors within a configurable time frame, all along their infinite execution, in contrast to the traditional objectives that only require correctness of behaviors in the limit. The window concept has proved its interest in a variety of two-player zero-sum games, thanks to the ability to reason about such time bounds in system specifications, but also the increased tractability that it usually yields. In this work, we extend the window framework to stochastic environments by considering the fundamental threshold probability problem in Markov decision processes for window objectives. That is, given such an objective, we want to synthesize strategies that guarantee satisfying runs with a given probability. We solve this problem for the usual variants of window objectives, where either the time frame is set as a parameter, or we ask if such a time frame exists. We develop a generic approach for window-based objectives and instantiate it for the classical mean-payoff and parity objectives, already considered in games. Our work paves the way to a wide use of the window mechanism in stochastic models. For the entire collection see [Zbl 1423.68023].</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Symmetric Nash equilibrium arrivals to queuing system</title> <id>https://zbmath.org/1553.91036</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.91036" /> <author> <name>&quot;Chirkova, Julia V.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:chirkova.julia-v</uri> </author> <content type="text">Summary: We consider a game-theoretic setting for the queuing system models where input process of arrivals is strategic. This paper generalizes a methodology for the symmetric Nash equilibrium exploring in queuing system with loss. We assume that the system admits customer requests at the time interval \([0,T]\). Each of customers chooses the moment to send his request into the system maximizing his payoff. Several models of certain systems are presented as examples demonstrating a result of the methodology application. For the entire collection see [Zbl 1544.91007].</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Dependent retailers' demand in game theoretic model of supply chain</title> <id>https://zbmath.org/1553.91037</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.91037" /> <author> <name>&quot;Kumacheva, Suriya Sh.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:kumacheva.suriya-sh</uri> </author> <author> <name>&quot;Zakharov, Victor V.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:zakharov.victor-v</uri> </author> <content type="text">Summary: Supply chain management is one of the intensively developing areas of applied research. One of the main tools for studying the problems of this area is game theory. This study is based on a two-level supply chain model mathematically described using a hierarchical Stackelberg game. The top player in the hierarchy is the manufacturer and the bottom players are two retailers interacting according to the Cournot game scheme. Unlike previous models, this one assumes that their demands are dependent and jointly distributed. Next, the focus shifts to the study of the interaction pattern of retailers when trading substitute goods. A special case of joint distribution of demand is considered. For the entire collection see [Zbl 1544.91007].</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Multiattribute decision making based on nonlinear programming methodology, score function of interval-valued intuitionistic fuzzy values, and the dispersion degree of score values</title> <id>https://zbmath.org/1553.91041</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.91041" /> <author> <name>&quot;Chen, Shyi-Ming&quot;</name> <uri>https://zbmath.org/authors/?q=ai:chen.shyiming</uri> </author> <author> <name>&quot;Huang, Shao-En&quot;</name> <uri>https://zbmath.org/authors/?q=ai:huang.shao-en</uri> </author> <content type="text">Summary: In this paper, we propose a new multiattribute decision making (MADM) method based on the proposed nonlinear programming (NLP) model, the proposed score function (SF) of interval-valued intuitionistic fuzzy values (IVIFVs), and the dispersion degree of the score values appeared in each column of the score matrix (SMX). Firstly, we propose a new SF of IVIFVs to construct the SMX. The proposed SF of IVIFVs can overcome the drawbacks of the existing SFs of IVIFVs. Then, we calculate the dispersion degree of the score values appeared at each column of the SMX. Then, we construct a NLP model to get the optimal weight (OW) of each attribute based on the obtained SMX, the dispersion degree of the score values appeared at each column of the SMX, and the interval-valued intuitionistic fuzzy weights of the attributes given by the decision maker. Then, we calculate the weighted score (WS) of each alternative based on the obtained SMX and the obtained OWs of the attributes. Finally, we get the preference order (PFO) of the alternatives based on the obtained WSs of the alternatives. The proposed MADM method can overcome the drawbacks of some existing MADM methods in an interval-valued intuitionistic fuzzy setting.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Retraction notice to: ``Multiple attribute decision making based on MAIRCA, standard deviation-based method, and Pythagorean fuzzy sets''</title> <id>https://zbmath.org/1553.91045</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.91045" /> <author> <name>&quot;Rani, Pratibha&quot;</name> <uri>https://zbmath.org/authors/?q=ai:rani.pratibha</uri> </author> <author> <name>&quot;Chen, Shyi-Ming&quot;</name> <uri>https://zbmath.org/authors/?q=ai:chen.shyiming</uri> </author> <author> <name>&quot;Raj Mishra, Arunodaya&quot;</name> <uri>https://zbmath.org/authors/?q=ai:mishra.arunodaya-raj</uri> </author> <content type="text">Retraction notice to the authors' paper [ibid. 644, Article ID 119274, 15~p. (2023; Zbl 1536.91129)]. The article was retracted because of its similarity with six other published papers and because of irregularities in the reference selection process.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Score function-based effective ranking of interval-valued Fermatean fuzzy sets and its applications to multi-criteria decision making problem</title> <id>https://zbmath.org/1553.91046</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.91046" /> <author> <name>&quot;Sahoo, Laxminarayan&quot;</name> <uri>https://zbmath.org/authors/?q=ai:sahoo.laxminarayan</uri> </author> <author> <name>&quot;Rana, Akul&quot;</name> <uri>https://zbmath.org/authors/?q=ai:rana.akul</uri> </author> <author> <name>&quot;Senapati, Tapan&quot;</name> <uri>https://zbmath.org/authors/?q=ai:senapati.tapan</uri> </author> <author> <name>&quot;Yager, Ronald R.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:yager.ronald-r</uri> </author> <content type="text">Summary: Fermatean fuzzy sets (FFSs), an orthopair fuzzy set proposed by \textit{T. Senapati} and \textit{R. R. Yager} [``Fermatean fuzzy sets'', J. Ambient Intell. Humanized Comput. 11, No. 2, 663--674 (2020; \url{doi:10.1007/s12652-019-01377-0})], can handle the situation with ambiguous and incomplete information in a more effective manner than the Pythagorean fuzzy sets presented by \textit{R. R. Yager} [``Pythagorean fuzzy subsets'', NAFIPS 2013, 57--61 (2013; \url{doi:10.1109/IFSA-NAFIPS.2013.6608375})] and the intuitionistic fuzzy sets presented by \textit{K. T. Atanassov} [Fuzzy Sets Syst. 20, 87--96 (1986; Zbl 0631.03040)]. \textit{D. Sergi} et al. [``Extension of capital budgeting techniques using interval-valued Fermatean fuzzy sets'', J. Intell. Fuzzy Syst. 42, No. 1, 365--376 (2022; \url{doi:10.3233/JIFS-219196})] initiated interval-valued Fermatean fuzzy sets (IVFFSs) and established IVFFS ordering, as well as some mathematical operations. In addition, \textit{S. Jeevraj} [``Ordering of interval-valued Fermatean fuzzy sets and its applications'', Expert Syst. Appl. 185, Article ID 115613, 20 p. (2021; \url{doi:10.1016/j.eswa.2021.115613})] introduced the concept of a score and accuracy function for IVFFSs. The main objective of this chapter is to suggest some score functions for acceptable ranking of IVFFSs, as well as the interval-valued Fermatean fuzzy TOPSIS method for solving multi-criteria decision making problems. Here, we have proposed six new variants of score functions for effective ranking of interval-valued Fermatean fuzzy sets. Depending on various types of score functions, we have used a TOPSIS-based multi-criteria decision making (MCDM) problem in which decision makers' (DMs') preference knowledge is summarized in the pattern of interval-valued Fermatean fuzzy sets. To illustrate the usefulness of the proposed method, a computational paradigm has been considered. Finally, concluding remarks and future scope of research have been mentioned. For the entire collection see [Zbl 1532.91004].</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Search with Dirichlet priors: estimation and implications for consumer demand</title> <id>https://zbmath.org/1553.91072</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.91072" /> <author> <name>&quot;Koulayev, Sergei&quot;</name> <uri>https://zbmath.org/authors/?q=ai:koulayev.sergei</uri> </author> <content type="text">(no abstract)</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Collaborative working capital optimization for combined supply network</title> <id>https://zbmath.org/1553.91208</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.91208" /> <author> <name>&quot;Lukinskii, Daniil V.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:lukinskii.daniil-v</uri> </author> <author> <name>&quot;Zenkevich, Nikolay A.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:zenkevich.nikolay-a</uri> </author> <content type="text">Summary: This study introduces an enhanced theoretical model aimed at minimizing the total costs of working capital within supply chains by leveraging reverse factoring and inventory financing. A comprehensive model was then developed for financial costs in supply chains with a combined topology. This model was not only stated but also transformed into a practical tool for professionals. To validate its applicability, the model was implemented in real-world business scenarios. Further, this paper offers guidelines for future deployments of the developed tool. For the entire collection see [Zbl 1544.91007].</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Towards optimal spatio-temporal decomposition of control-related sum-of-squares programs</title> <id>https://zbmath.org/1553.93095</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.93095" /> <author> <name>&quot;Cibulka, V铆t&quot;</name> <uri>https://zbmath.org/authors/?q=ai:cibulka.vit</uri> </author> <author> <name>&quot;Korda, Milan&quot;</name> <uri>https://zbmath.org/authors/?q=ai:korda.milan</uri> </author> <author> <name>&quot;Hani拧, Tom谩拧&quot;</name> <uri>https://zbmath.org/authors/?q=ai:hanis.tomas</uri> </author> <content type="text">Summary: This paper presents a method for calculating the region of attraction (ROA) of nonlinear dynamical systems, both with and without control. The ROA is determined by solving a hierarchy of semidefinite programs (SDPs) defined on a splitting of the time and state space. Previous works demonstrated that this splitting could significantly enhance approximation accuracy, although the improvement was highly dependent on the ad-hoc selection of split locations. In this work, we eliminate the need for this ad-hoc selection by introducing an optimization-based method that performs the splits through conic differentiation of the underlying semidefinite programming problem. We provide the differentiability conditions for the split ROA problem, prove the absence of a duality gap, and demonstrate the effectiveness of our method through numerical examples. {\copyright} 2024 The Author(s). \textit{International Journal of Robust and Nonlinear Control} published by John Wiley \&amp; Sons Ltd.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">A dual scale spatio-temporal control for complex distributed parameter systems</title> <id>https://zbmath.org/1553.93104</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.93104" /> <author> <name>&quot;Zhao, Yaru&quot;</name> <uri>https://zbmath.org/authors/?q=ai:zhao.yaru</uri> </author> <author> <name>&quot;Li, Han-Xiong&quot;</name> <uri>https://zbmath.org/authors/?q=ai:li.hanxiong</uri> </author> <content type="text">Summary: It is very difficult to control the distributed parameter system (DPS) for consistent spatial performance. In this paper, a dual scale spatio-temporal control is designed for the DPS to achieve a consistent performance across the entire workspace under unknown exogenous disturbances. First, the generalized ``spatial observer'' should be designed under spectral decomposition/synthesis, to act as the nominal model of the DPS, through which the spatial mismatch between the model and the process could be estimated. Then a distributed disturbance compensator can be constructed to suppress all the undesirable spatial disturbance through the inner loop, and the compensated system will become closer to the nominal model and easier to control. Third, a dual controller will be designed in the outer loop for the final consistent spatial performance. Since the spatial performance is mainly affected by the dominant dynamics on the slow scale, a convex optimization algorithm can be effectively established in terms of nonlinear matrix inequalities for the dual controller. In this way, the nonlinear optimization problem is solved by converting it into the problem of a linear matrix inequalities with constraints. Besides, the spatio-temporal state variable of the controlled plant is demonstrated to converge in Hilbert space. The feasibility and effectiveness of the proposed control method are verified by temperature control of a catalytic rod, a benchmark in chemical reactors. {\copyright} 2024 John Wiley \&amp; Sons Ltd.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Optimal control of linear cost networks</title> <id>https://zbmath.org/1553.93114</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.93114" /> <author> <name>&quot;Ohlin, David&quot;</name> <uri>https://zbmath.org/authors/?q=ai:ohlin.david</uri> </author> <author> <name>&quot;Tegling, Emma&quot;</name> <uri>https://zbmath.org/authors/?q=ai:tegling.emma</uri> </author> <author> <name>&quot;Rantzer, Anders&quot;</name> <uri>https://zbmath.org/authors/?q=ai:rantzer.anders</uri> </author> <content type="text">Summary: We present a method for optimal control with respect to a linear cost function for positive linear systems with coupled input constraints. We show that the Bellman equation giving the optimal cost function and resulting sparse state feedback for these systems can be stated explicitly, with the solution given by a linear program. Our framework admits a range of network routing problems with underlying linear dynamics. These dynamics can be used to model traditional graph-theoretical problems like shortest path as a special case, but can also capture more complex behaviors. We provide an asynchronous and distributed value iteration algorithm for obtaining the optimal cost function and control law.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">A stabilizing reinforcement learning approach for sampled systems with partially unknown models</title> <id>https://zbmath.org/1553.93121</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.93121" /> <author> <name>&quot;Beckenbach, Lukas&quot;</name> <uri>https://zbmath.org/authors/?q=ai:beckenbach.lukas</uri> </author> <author> <name>&quot;Osinenko, Pavel&quot;</name> <uri>https://zbmath.org/authors/?q=ai:osinenko.pavel</uri> </author> <author> <name>&quot;Streif, Stefan&quot;</name> <uri>https://zbmath.org/authors/?q=ai:streif.stefan</uri> </author> <content type="text">Summary: Reinforcement learning is commonly associated with training of reward-maximizing (or cost-minimizing) agents, in other words, controllers. It can be applied in model-free or model-based fashion, using a priori or online collected system data to train involved parametric architectures. In general, online reinforcement learning does not guarantee closed loop stability unless special measures are taken, for instance, through learning constraints or tailored training rules. Particularly promising are hybrids of reinforcement learning with classical control approaches. In this work, we suggest a method to guarantee practical stability of the system-controller closed loop in a purely online learning setting, in other words, without offline training. Moreover, we assume only partial knowledge of the system model. To achieve the claimed results, we employ techniques of classical adaptive control. The implementation of the overall control scheme is provided explicitly in a digital, sampled setting. That is, the controller receives the state of the system and computes the control action at discrete, specifically, equidistant moments in time. The method is tested in adaptive traction control and cruise control where it proved to significantly reduce the cost. {\copyright} 2024 John Wiley \&amp; Sons Ltd.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">An advanced robust integral reinforcement learning scheme with the fuzzy inference system</title> <id>https://zbmath.org/1553.93129</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.93129" /> <author> <name>&quot;Liu, Ao&quot;</name> <uri>https://zbmath.org/authors/?q=ai:liu.ao</uri> </author> <author> <name>&quot;Wang, Ding&quot;</name> <uri>https://zbmath.org/authors/?q=ai:wang.ding</uri> </author> <author> <name>&quot;Qiao, Junfei&quot;</name> <uri>https://zbmath.org/authors/?q=ai:qiao.junfei</uri> </author> <content type="text">Summary: In this paper, the model-free robust control problem is investigated for nonlinear systems with a relaxed condition of initial admissible control. An advanced integral reinforcement learning method is developed, which merges the adaptive network-based fuzzy inference system (ANFIS) and pre-training of the initial weights. To loose the condition for choosing the initial control law, pre-training of initial weights is established by utilizing the ANFIS to provide the information corresponding to the system model, which is applicable to the model-free issue. Based on the actor-critic structure, the approximate optimal control law is obtained by employing adaptive dynamic programming. Redesigning the obtained control law, the robust controller can be derived to stabilize the system with the uncertain term. Eventually, two examples are utilized to verify the effectiveness of the constructed algorithm. {\copyright} 2024 John Wiley \&amp; Sons Ltd.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Firefly optimized neural network-based trajectory tracking control of partially unknown multiplayer nonlinear systems</title> <id>https://zbmath.org/1553.93145</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.93145" /> <author> <name>&quot;Wu, Qiuye&quot;</name> <uri>https://zbmath.org/authors/?q=ai:wu.qiuye</uri> </author> <author> <name>&quot;Zhao, Bo&quot;</name> <uri>https://zbmath.org/authors/?q=ai:zhao.bo</uri> </author> <author> <name>&quot;Liu, Derong&quot;</name> <uri>https://zbmath.org/authors/?q=ai:liu.derong</uri> </author> <content type="text">Summary: In this paper, we develop an integral reinforcement learning (IRL)-based trajectory tracking control (TTC) scheme via firefly optimized neural networks for partially unknown multiplayer nonlinear systems. Under the developed TTC scheme, IRL is proved to be equivalent to the classical policy iteration, which guarantees the convergence of the IRL algorithm. By implementing the IRL method, the requirement of the drift dynamics is obviated. The TTC policy for each player is obtained by solving the coupled Hamilton-Jacobi equation with a critic neural network, whose weight vector is tuned by the firefly algorithm. The tracking error of the closed-loop system is guaranteed to be stable via the Lyapunov's direct method. Simulation results illustrate the effectiveness and superiority of the present IRL-based TTC scheme, and show that the success rate of system operation is increased by introducing the firefly algorithm. {\copyright} 2024 John Wiley \&amp; Sons Ltd.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Layers update of neural network control via event-triggering mechanism</title> <id>https://zbmath.org/1553.93178</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.93178" /> <author> <name>&quot;Tarbouriech, Sophie&quot;</name> <uri>https://zbmath.org/authors/?q=ai:tarbouriech.sophie</uri> </author> <author> <name>&quot;De Souza, Carla&quot;</name> <uri>https://zbmath.org/authors/?q=ai:de-souza.carla</uri> </author> <author> <name>&quot;Girard, Antoine&quot;</name> <uri>https://zbmath.org/authors/?q=ai:girard.antoine</uri> </author> <content type="text">Summary: The chapter deals with the design of event-triggering mechanisms (ETM) for discrete-time linear systems stabilized by neural network controllers. The proposed event-triggering mechanism is based on the use of local sector conditions related to the activation functions, to reduce the computational cost associated with the neural network evaluation. Such a mechanism avoids redundant computations by updating only a portion of the layers instead of evaluating periodically the complete neural network. Sufficient matrix inequality conditions are provided to design the parameters of the event-triggering mechanism and compute an inner-approximation of the region of attraction for the feedback system. The theoretical conditions are obtained by using a quadratic Lyapunov function and an adequate abstraction of the activation functions via generalised sector condition to decide whether the outputs of the layers should be transmitted through the network or not. Convex optimisation procedures can be associated to the theoretical conditions in order to maximise the approximation of the region of attraction or to minimise the number of updates. The advantages and the drawbacks of our approach are illustrated in an example borrowed from the literature, namely the nonlinear inverted pendulum system stabilized by a trained neural network. For the entire collection see [Zbl 1537.93005].</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Asynchronous nonfragile guaranteed performance control for singular switched positive systems: an event-triggered mechanism</title> <id>https://zbmath.org/1553.93181</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.93181" /> <author> <name>&quot;Wang, Jinling&quot;</name> <uri>https://zbmath.org/authors/?q=ai:wang.jinling</uri> </author> <author> <name>&quot;Li, Qiang&quot;</name> <uri>https://zbmath.org/authors/?q=ai:li.qiang.3</uri> </author> <author> <name>&quot;Li, Shuo&quot;</name> <uri>https://zbmath.org/authors/?q=ai:li.shuo</uri> </author> <author> <name>&quot;Zhang, Linzhong&quot;</name> <uri>https://zbmath.org/authors/?q=ai:zhang.linzhong</uri> </author> <content type="text">Summary: This paper addresses the guaranteed performance control problem for a class of singular switched positive systems, where the switching signal is subject to a state-dependent process. Firstly, the causality, regularity, positivity, and asymptotical stability of the considered systems are discussed. In order to prevent the occurrence of data collisions and reduce the consumption of communication resources, the event-triggered (E-T) mechanism is applied. This is one of the initial attempts to introduce the E-T scheme for such special systems. Besides, an asynchronous nonfragile controller under the E-T scheduling scheme is designed to make certain that the resulting closed-loop systems are causal, regular, positive, asymptotically stable, and have a guaranteed performance value \(J^{\ast}\). Through the application of the co-positive Lyapunov function method and the min-projection strategy, the corresponding sufficient conditions are given in the form of linear programming (LP). Finally, the effectiveness of the controller proposed in this paper is verified via two simulation examples. {\copyright} 2024 John Wiley \&amp; Sons Ltd.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Distributed online constrained convex optimization with event-triggered communication</title> <id>https://zbmath.org/1553.93189</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.93189" /> <author> <name>&quot;Zhang, Kunpeng&quot;</name> <uri>https://zbmath.org/authors/?q=ai:zhang.kunpeng</uri> </author> <author> <name>&quot;Yi, Xinlei&quot;</name> <uri>https://zbmath.org/authors/?q=ai:yi.xinlei</uri> </author> <author> <name>&quot;Li, Yuzhe&quot;</name> <uri>https://zbmath.org/authors/?q=ai:li.yuzhe</uri> </author> <author> <name>&quot;Cao, Ming&quot;</name> <uri>https://zbmath.org/authors/?q=ai:cao.ming</uri> </author> <author> <name>&quot;Chai, Tianyou&quot;</name> <uri>https://zbmath.org/authors/?q=ai:chai.tianyou</uri> </author> <author> <name>&quot;Yang, Tao&quot;</name> <uri>https://zbmath.org/authors/?q=ai:yang.tao</uri> </author> <content type="text">Summary: This paper focuses on the distributed online convex optimization problem with time-varying inequality constraints over a network of agents, where each agent collaborates with its neighboring agents to minimize the cumulative network-wide loss over time. To reduce communication overhead between the agents, we propose a distributed event-triggered online primal-dual algorithm over a time-varying directed graph. With several classes of appropriately chose decreasing parameter sequences and non-increasing event-triggered threshold sequences, we establish dynamic network regret and network cumulative constraint violation bounds. Finally, a numerical simulation example is provided to verify the theoretical results.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Data-driven stabilization of nonlinear systems via Taylor's expansion</title> <id>https://zbmath.org/1553.93210</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.93210" /> <author> <name>&quot;Guo, Meichen&quot;</name> <uri>https://zbmath.org/authors/?q=ai:guo.meichen</uri> </author> <author> <name>&quot;De Persis, Claudio&quot;</name> <uri>https://zbmath.org/authors/?q=ai:de-persis.claudio</uri> </author> <author> <name>&quot;Tesi, Pietro&quot;</name> <uri>https://zbmath.org/authors/?q=ai:tesi.pietro</uri> </author> <content type="text">Summary: Lyapunov's indirect method is one of the oldest and most popular approaches to model-based controller design for nonlinear systems. When the explicit model of the nonlinear system is unavailable for designing such a linear controller, finite-length off-line data is used to obtain a data-based representation of the closed-loop system, and a data-driven linear control law is designed to render the considered equilibrium locally asymptotically stable. This work presents a systematic approach for data-driven linear stabilizer design for continuous-time and discrete-time general nonlinear systems. Moreover, under mild conditions on the nonlinear dynamics, we show that the region of attraction of the resulting locally asymptotically stable closed-loop system can be estimated using data. For the entire collection see [Zbl 1537.93005].</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Research on the control of thrust vectoring turbojet aircraft with uncertainties and input saturation based on fixed-time control</title> <id>https://zbmath.org/1553.93227</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.93227" /> <author> <name>&quot;Liu, Benshan&quot;</name> <uri>https://zbmath.org/authors/?q=ai:liu.benshan</uri> </author> <author> <name>&quot;Gao, Yongsheng&quot;</name> <uri>https://zbmath.org/authors/?q=ai:gao.yongsheng</uri> </author> <author> <name>&quot;Gao, Liang&quot;</name> <uri>https://zbmath.org/authors/?q=ai:gao.liang</uri> </author> <author> <name>&quot;Zhang, Junming&quot;</name> <uri>https://zbmath.org/authors/?q=ai:zhang.junming</uri> </author> <author> <name>&quot;Zhu, Yanhe&quot;</name> <uri>https://zbmath.org/authors/?q=ai:zhu.yanhe</uri> </author> <author> <name>&quot;Zhao, Jie&quot;</name> <uri>https://zbmath.org/authors/?q=ai:zhao.jie.1</uri> </author> <content type="text">Summary: One-dimensional thrust vectoring turbojet vertical takeoff and landing (VTOL) aircraft have attracted research attention due to their high thrust-to-weight ratios and their solution for the slow speed response of turbojet engines. However, there are some uncertainties and physical limitations in their systems, such as external disturbances, unknown parameters and input saturation. To improve the accuracy and convergence speed of trajectory tracking, a fixed-time control method that is robust to saturation is proposed. The system dynamics are established, and an auxiliary system is built within a fixed time control framework to address the influence of input saturation and increase the error convergence rate. Nonsingular fast terminal sliding mode technology is combined with a few adaptive laws to ensure the robustness of the closed-loop system against dynamic uncertainties and improve the precision of steady-state control. The stability of the control system is proven based on Lyapunov, and the controller parameters are optimized based on particle swarm optimization (PSO). The proposed method based on fixed-time stability guarantees that the states of the closed-loop system can reach the residual set around zero within the designed time, and an expression for the upper bound on the convergence time is given. Finally, numerical simulations demonstrate the superiority of the proposed method based on the error integral criterion. {\copyright} 2024 John Wiley \&amp; Sons Ltd.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Stochastic control with distributionally robust constraints for cyber-physical systems vulnerable to attacks</title> <id>https://zbmath.org/1553.93251</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.93251" /> <author> <name>&quot;Venkatesh, Nishanth&quot;</name> <uri>https://zbmath.org/authors/?q=ai:venkatesh.nishanth</uri> </author> <author> <name>&quot;Dave, Aditya&quot;</name> <uri>https://zbmath.org/authors/?q=ai:dave.aditya</uri> </author> <author> <name>&quot;Faros, Ioannis&quot;</name> <uri>https://zbmath.org/authors/?q=ai:faros.ioannis</uri> </author> <author> <name>&quot;Malikopoulos, Andreas A.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:malikopoulos.andreas-a</uri> </author> <content type="text">Summary: In this paper, we investigate the control of a cyber-physical system (CPS) while accounting for its vulnerability to external attacks. We formulate a constrained stochastic problem with a robust constraint to ensure robust operation against potential attacks. We seek to minimize the expected cost subject to a constraint limiting the worst-case expected damage an attacker can impose on the CPS. We present a dynamic programming decomposition to compute the optimal control strategy in this robust-constrained formulation and prove its recursive feasibility. We also illustrate the utility of our results by applying them to a numerical simulation.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Two improved generalized extended stochastic gradient algorithms for CARARMA systems</title> <id>https://zbmath.org/1553.93253</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.93253" /> <author> <name>&quot;Lv, Lingling&quot;</name> <uri>https://zbmath.org/authors/?q=ai:lv.lingling</uri> </author> <author> <name>&quot;Zhang, Yulin&quot;</name> <uri>https://zbmath.org/authors/?q=ai:zhang.yulin.1|zhang.yulin.2|zhang.yulin</uri> </author> <author> <name>&quot;Huang, Quanzhen&quot;</name> <uri>https://zbmath.org/authors/?q=ai:huang.quanzhen</uri> </author> <author> <name>&quot;Wu, Yu&quot;</name> <uri>https://zbmath.org/authors/?q=ai:wu.yu</uri> </author> <content type="text">Summary: The paper innovatively proposes two improved generalized extended stochastic gradient (GESG) algorithms for the controlled autoregressive autoregressive moving average (CARARMA) system with autoregressive moving average (ARMA) model noise. Firstly, we propose a latest estimation based weighted generalized extended stochastic gradient (LE-WGESG) algorithm, which introduces multiple momentary corrections in the traditional parameter estimation process. By carefully adjusting the weighting coefficients of the correction quantities at different moments, the algorithm has a rapid and greater efficient convergence property. More importantly, utilizing the theory of moving data window, this paper also proposes a multi-innovation based latest estimated weighted generalized extended stochastic gradient (MI-LE-WGESG) algorithm, which can better capture the interactions among multiple correction terms and further improve the predictive ability of the model.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Peak estimation of rational systems using convex optimization</title> <id>https://zbmath.org/1553.93255</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.93255" /> <author> <name>&quot;Miller, Jared&quot;</name> <uri>https://zbmath.org/authors/?q=ai:miller.jared|miller.jared-t</uri> </author> <author> <name>&quot;Smith, Roy S.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:smith.roy-s</uri> </author> <content type="text">Summary: This paper presents algorithms that upper-bound the peak value of a state function along trajectories of a continuous-time system with rational dynamics. The finite-dimensional but nonconvex peak estimation problem is cast as a convex infinite-dimensional linear program in occupation measures. This infinite-dimensional program is then truncated into finite-dimensions using the moment-sum-of-squares (SOS) hierarchy of semidefinite programs. Prior work on treating rational dynamics using the moment-SOS approach involves clearing dynamics to common denominators or adding lifting variables to handle reciprocal terms under new equality constraints. Our solution method uses a sum-of-rational method based on absolute continuity of measures. The moment-SOS truncations of our program possess lower computational complexity and (empirically demonstrated) higher accuracy of upper bounds on example systems as compared to prior approaches.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Denoising of sphere- and SO(3)-valued data by relaxed Tikhonov regularization</title> <id>https://zbmath.org/1553.94003</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.94003" /> <author> <name>&quot;Beinert, Robert&quot;</name> <uri>https://zbmath.org/authors/?q=ai:beinert.robert</uri> </author> <author> <name>&quot;Bresch, Jonas&quot;</name> <uri>https://zbmath.org/authors/?q=ai:bresch.jonas</uri> </author> <author> <name>&quot;Steidl, Gabriele&quot;</name> <uri>https://zbmath.org/authors/?q=ai:steidl.gabriele</uri> </author> <content type="text">Summary: Manifold-valued signal- and image processing has received attention due to modern image acquisition techniques. Recently, a convex relaxation of the otherwise non-convex Tikhonov-regularization for denoising circle-valued data has been proposed by \textit{L. Condat} [IEEE Trans. Signal Process. 70, 2775--2782 (2022; Zbl 1548.94147)]. The circle constraints were encoded in a series of low-dimensional, positive semi-definite matrices. Using Schur complement arguments, we showed that the resulting variational model can be simplified while leading to the same solution. The simplified model can be generalized to higher dimensional spheres and to the special orthogonal group SO(3), where we relied on the quaternion representation of the latter. Standard algorithms from convex analysis can be applied to solve the resulting convex minimization problem. As proof-of-the-concept, we used the alternating direction method of multipliers to demonstrate the denoising behavior of the proposed method. In a series of experiments, we demonstrated the numerical convergence of the signal- or image values to the underlying manifold.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">Fully-connected tensor network decomposition and group sparsity for multitemporal images cloud removal</title> <id>https://zbmath.org/1553.94004</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.94004" /> <author> <name>&quot;Tu, Zhihui&quot;</name> <uri>https://zbmath.org/authors/?q=ai:tu.zhihui</uri> </author> <author> <name>&quot;Lu, Jian&quot;</name> <uri>https://zbmath.org/authors/?q=ai:lu.jian.1</uri> </author> <author> <name>&quot;Zhu, Hong&quot;</name> <uri>https://zbmath.org/authors/?q=ai:zhu.hong.4</uri> </author> <author> <name>&quot;Hu, Wenyu&quot;</name> <uri>https://zbmath.org/authors/?q=ai:hu.wenyu</uri> </author> <author> <name>&quot;Jiang, Qingtang&quot;</name> <uri>https://zbmath.org/authors/?q=ai:jiang.qingtang</uri> </author> <author> <name>&quot;Ng, Michael K.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:ng.michael-k</uri> </author> <content type="text">Summary: Existing nonblinded cloud removal approaches in multitemporal images depend on the accuracy of the mask used. However, masks are typically detected via manual labeling or cloud detection methods, which do not guarantee accuracy and thus may affect cloud removal. In this paper, we present a cloud/shadow removal method that does not require masks: fully-connected tensor network decomposition and group sparsity (FCTNGS). To capture multitemporal information, we use fully-connected tensor network decomposition to explore the global correlation of multitemporal images and weighted group sparsity to describe cloud sparsity. To develop the proposed model, we propose an efficient algorithm that is based on the proximal alternating minimization (PAM) method. Experiments with both simulated and real datasets demonstrate the effectiveness and robustness of the proposed cloud/shadow removal method.</content> </entry> <entry xml:base="https://zbmath.org/atom/cc/90"> <title type="text">A method for optimal value measurement of some parameters of fault attacks on cryptographic algorithms</title> <id>https://zbmath.org/1553.94090</id> <updated>2025-04-04T17:10:03.436181Z</updated> <link href="https://zbmath.org/1553.94090" /> <author> <name>&quot;Zuev, Yu. A.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:zuev.yu-a</uri> </author> <author> <name>&quot;Klyuchar毛v, P. G.&quot;</name> <uri>https://zbmath.org/authors/?q=ai:klyucharev.p-g</uri> </author> <content type="text">Summary: This paper is devoted to the construction of a time-optimal method for measuring the maximum permissible (critical) value of the supply voltage (as well as other parameters) of the device on which the cryptographic algorithm is performed. Knowledge of these values is necessary for successful conduct of error injection, as part of a fault attack. The method is based on dynamic programming.</content> </entry> </feed>