Recent zbMATH articles in MSC 90https://zbmath.org/atom/cc/902022-11-17T18:59:28.764376ZUnknown authorWerkzeugPrefacehttps://zbmath.org/1496.000632022-11-17T18:59:28.764376ZFrom the text: This special issue of Optimization is dedicated to Professor Wataru Takahashi on the occasion of his 75th birthday.On the local structure of oriented graphs -- a case study in flag algebrashttps://zbmath.org/1496.050862022-11-17T18:59:28.764376Z"Gilboa, Shoni"https://zbmath.org/authors/?q=ai:gilboa.shoni"Glebov, Roman"https://zbmath.org/authors/?q=ai:glebov.roman"Hefetz, Dan"https://zbmath.org/authors/?q=ai:hefetz.dan"Linial, Nati"https://zbmath.org/authors/?q=ai:linial.nathan"Morgenstern, Avraham"https://zbmath.org/authors/?q=ai:morgenstern.avrahamSummary: Let \(G\) be an \(n\)-vertex oriented graph. Let \(t(G)\) (respectively \(i(G))\) be the probability that a random set of \(3\) vertices of \(G\) spans a transitive triangle (respectively an independent set). We prove that \(t(G) + i(G) \geqslant \frac{1}{9}-o_n(1)\). Our proof uses the method of flag algebras that we supplement with several steps that make it more easily comprehensible. We also prove a stability result and an exact result. Namely, we describe an extremal construction, prove that it is essentially unique, and prove that if \(H\) is sufficiently far from that construction, then \(t(H) + i(H)\) is significantly larger than \(\frac{1}{9}\).
We go to greater technical detail than is usually done in papers that rely on flag algebras. Our hope is that as a result this text can serve others as a useful introduction to this powerful and beautiful method.On dominating set of some subclasses of string graphshttps://zbmath.org/1496.051232022-11-17T18:59:28.764376Z"Chakraborty, Dibyayan"https://zbmath.org/authors/?q=ai:chakraborty.dibyayan"Das, Sandip"https://zbmath.org/authors/?q=ai:das.sandip-kr|das.sandip-kumar"Mukherjee, Joydeep"https://zbmath.org/authors/?q=ai:mukherjee.joydeepAn intersection representation \(\mathcal{R}\) of a graph \( G = (V , E)\) is a family of \(\{\mathcal{R}_u\}\) \(u\in V\) sets such that \(uv \in E\) if and only if \({\mathcal{R}_u}\bigcap{\mathcal{R}_v}\neq \emptyset\). When \(\mathcal{R}\) is a collection of geometric objects, it is said to be a geometric intersection representation of \(G\). When \(\mathcal{R}\) is a collection of simple unbounded curves on the plane, it is called a string representation. A graph \(G\) is a string graph if \(G\) has a string representation. String graphs are important as it contains all intersection graphs of connected sets in \(\mathcal{R}^2\). String graphs have been intensively studied both for practical applications and theoretical interest. \textit{S. Benzer} [``On the topology of the genetic fine structure'', Proc. Natl. Acad. Sci. 45, No. 11, 1607--1620 (1959; \url{doi:10.1073/pnas.45.11.1607})] introduced string graphs while exploring the topology of genetic structures. \textit{F. W. Sinden} [Bell Syst. Tech. J. 45, 1639--1662 (1966; Zbl 0144.45601)] considered the same constructs at Bell Labs. In 1976, Graham introduced string graphs to the mathematics community at the open problem session of a conference in Keszthely. Since then, many researchers have been carrying out extensive research on string graphs.
The graph classes like planar graphs, chordal graphs, cocomparability graph, disk graphs, rectangle intersection graphs, segment graphs, and circular arc graphs are subclasses of string graphs. Any intersection graph of arc-connected sets on the plane is a string graph. However, not all graphs are string graphs and this is the reason why people study the computational complexities of various optimisation problems in string graphs and their subclasses.
\par In this paper, the authors propose constant factor approximation algorithms for the Minimum Dominating Set (MDS) problem on string graphs.
A dominating set of a graph \(G = (V , E)\) is a subset \(D\) of vertices \(V\) such that each vertex in \(V\backslash D\) is adjacent to some vertex in \(D\). The Minimum Dominating Set (MDS) problem is to find a minimum cardinality dominating set of a graph \(G\).
The readers can read the paper by \textit{M. Chlebík} and \textit{J. Chlebíková} [Inf. Comput. 206, No. 11, 1264--1275 (2008; Zbl 1169.68037)] to see that it is not possible to approximate the MDS problem on string graphs.
Thus, researchers are compelled to develop approximation algorithms for the MDS problem on various subclasses of string graphs. Planar graphs, chordal graphs, disk graphs, unit disk graphs, rectangle intersection graphs, intersection graphs of homothets of convex objects, etc. are examples. \textit{M. de Berg} et al. [Theor. Comput. Sci. 769, 18--31 (2019; Zbl 1421.68071)] studied the fixed-parameter tractability of the MDS problem on various classes of geometric intersection graphs. \textit{T. Erlebach} and \textit{E. J. van Leeuwen} [Lect. Notes Comput. Sci. 4957, 747--758 (2008; Zbl 1136.68568)] gave constant-factor approximation algorithms for intersection graphs of \(r\)-regular polygons, where \(r\) is an arbitrary constant, for pairwise homothetic triangles, and rectangles with bounded aspect ratio.
\textit{A. Asinowski} et al. [J. Graph Algorithms Appl. 16, No. 2, 129--150 (2012; Zbl 1254.68184)] introduced the concept of \(B_k\)-VPG graphs to initiate a systematic study of string graphs and its subclasses in the year. A path is a simple rectilinear curve made of axis-parallel line segments, and a \(k\)-bend path is a path having \(k\) bends. The \(B_k\)-VPG graphs are intersection graphs of \(k\)-bend paths. Asinowski et al. have shown that any string graph has a \(B_k\)-VPG representation for some \(k\). \textit{M. J. Katz} et al. [Comput. Geom. 30, No. 2, 197--205 (2005; Zbl 1162.68751)] proved the NP-hardness of the MDS problem on \(B_0\)-VPG graphs. An interesting fact is that a sublogarithmic approximation algorithm for the MDS problem on \(B_0\)-VPG graphs is still unknown. It is to be noted that intersection graphs of orthogonal segments having unit length, i.e. unit \(B_0\)-VPG graphs is a subclass of \(B_0\)-VPG graphs.
In this paper, the authors show that the MDS problem is NP-hard on unit \(B_0\)-VPG graphs. This result strengthens a result of Katz et al. [loc. cit.]. They also propose the first constant-factor approximation algorithm for the MDS problem on unit \(B_0\)-VPG graphs. Specifically, the authors prove the following theorems.
Theorem 1.
It is NP-Hard to solve the MDS problem on unit \(B_k\)-VPG graphs with \(k \geq 0\).
Theorem 2.
Given a unit \(B_0\)-VPG representation of a graph \(G\) with \(n\) vertices, there is an \(O(n^5)\)-time 18-approximation algorithm to solve the MDS problem on \(G\).
Theorem 3.
Given a unit \(B_k\)-VPG representation of a graph \(G\) with \(n\) vertices, there is an \(O(k^2n^5)\)-time \(O(k^4)\)-approximation algorithm to solve the MDS problem on \(G\).
Theorem 4.
Given a vertically-stabbed L-representation of a graph \(G\) with \(n\) vertices, there is an \(O(n^5)\)-time 8-approximation algorithm to solve the MDS problem on \(G\).
Theorem 5.
Assuming the Unique Games Conjecture to be true, it is not possible to have a polynomial time \((2 -\epsilon)\)-approximation algorithm for the MDS problem on rectangle overlap graphs for any \(\epsilon > 0\).
Theorem 6.
Given a stabbed rectangle overlap representation of a graph \(G\) with \(n\) vertices, there is an \(O(n^5)\)-time 656-approximation algorithm for the MDS problem on \(G\).
The interval overlap graphs and intersection graphs of diagonally anchored rectangles are strict subclasses of
stabbed rectangle overlap graphs.
Note that approximation algorithms for optimization problems like Maximum Independent Set and Minimum Hitting Set on intersection graphs of ``stabbed'' geometric objects have been studied by different authors.
Proofs of Theorem 2, 3, 4, and 6 use two crucial lemmas. The first one is about the stabbing segment with rays SSR
problem and the second one is about the stabbing rays with segment SRS problem, both introduced by Katz et al. [loc. cit.].
The definitions of both SSR and SRS problems are given below.
Stabbing segments with rays SSR.
Input: A set R of disjoint leftward-directed horizontal semi-infinite rays and a set of disjoint vertical segments.
Output: A minimum cardinality subset of \(R\) that intersect all segments in \(V\).
Stabbing rays with segments SRS.
Input: A set \(R\) of disjoint leftward-directed horizontal semi-infinite rays and a set of disjoint vertical segments.
Output: A minimum cardinality subset of \(V\) that intersect all rays in \(R\).
Let \(\mathrm{SSR}(R, V)\) (resp. \(\mathrm{SRS}(R,V)\)) denote an SSR instance (resp. an SRS instance) where \(R\) is a given set of disjoint leftward-directed horizontal semi-infinite rays and \(V\) is a given set of disjoint vertical segments. Katz et al. [loc. cit.] gave
dynamic programming-based polynomial time algorithms for both the SSR problem and the SRS problem. Here the authors, to prove Theorems 2, 3, 4, and 6, have developed an upper bound on the ratio of the cardinality of the optimal solution of an SSR
instance (and SRS instance) with the optimal cost of the corresponding relaxed LP formulation(s).
Therefore, they have proved the following lemmas.
Lemma 1.
Let \(C\) be an ILP formulation of an \(\mathrm{SSR}(R,V)\) instance. There is an \(O((n +m) \log(n +m))\)-time algorithm to compute a set \(D\subseteq R\) which gives a feasible solution of \(C\) and \(|D|\leq 2\cdot \mathrm{OPT}(C_1)\) where \(n = |R|, m- |V |\) and \(C_1\) is the relaxed LP formulation of \(C\).
Lemma 2.
Let \(C\) be an ILP formulation of an SRS(R,V) instance. There is an \(O(n \log n)\) time algorithm to compute a set \(D \subsetneq V\) which gives a feasible solution of \(C\) and
\(|D|\leq 2\cdot \mathrm{OPT}(C_l)\) where \(n = |V |\) and \(C_l\) is the relaxed LP formulation of \(C\).
To prove both the above lemma, the authors have not explicitly solved the LP(s). Moreover, since \(\mathrm{OPT}(C_l) \leq \mathrm{OPT}(C)\), the algorithm of Lemma 1 provides an approximate solution to the \(\mathrm{SSR}(R,V)\) instance with approximation ratio 2. So, it is argued that Theorem 7 is a consequence of Lemma 1.
Theorem 7.
There is an \(O((n +m) \log(n +m))\)-time 2-approximation algorithm for SSR problem where \(n\) and \(m\) are the number of rays and segments, respectively.
In Section 2.1 and Section 2.2, the authors have proved the hardness results (Theorem 1 and Theorem 5). In Section 3 and Section 4, they have proved Lemma 1 and Lemma 4, respectively. In Section 5, they have applied both Lemma 1 and Lemma 2 to prove Theorem 4.
Then in Sections 6, 7, and 8, they have proved Theorem 2, Theorem 3, and Theorem 6, respectively.
The authors end the paper with the following four questions.
Question 1. What are the integrality gaps of the SSR and the SRS problems?
Question 2. Is there a \(c\)-approximation algorithm for the MDS problem on unit \(B_0\)-VPG graphs with \(c < 18\)?
Question 3. Is there a constant-factor approximation algorithm for the MDS problem on \(B_0\)-VPG graphs? Is there an
\(O(\log k)\)-approximation algorithm for the MDS problem on \(B_k\)-VPG graphs?
Question 4. Is there a \(c\)-approximation algorithm for the MDS problem on stabbed rectangle overlap graphs with \(c < 656\)?
We see in this paper an amalgamation of areas such as linear programming, algorithms, NP-hardness and graph theory. It has an exhaustive list of bibliography with 49 papers and all of these papers are used in the writing of this paper. The standard of the paper is high. The researchers will learn a lot by reading this paper. There are four questions for which the researchers can break their heads and find answers. Overall the paper is classic and it contains a lot of treasure in it.
Reviewer: A. Lourdusamy (Palayamkottai)A weighted perfect matching with constraints on weights of its partshttps://zbmath.org/1496.051412022-11-17T18:59:28.764376Z"Duginov, Oleg Ivanovich"https://zbmath.org/authors/?q=ai:duginov.oleg-ivanovichSummary: We consider the following strongly NP-hard problem. Given an edge-weighted balanced complete bipartite graph with a partition of its part into non-empty and pairwise disjoint subsets, the problem is to find a perfect matching of this graph such that maximum sum of weights of edges from the matching incident to vertices of a subset of the partition is minimum. We present a characterization of solutions of a special case of this problem, in which weights of graph edges take values from the set \(\{0, 1, \Delta\},\) where \(\Delta\) is an integer that is greater than the number of edges of the unit weight and there is a perfect matching of the graph that consists of edges with weights 0 and 1. Besides, we identify polynomially solvable and strongly NP-hard special cases of this problem. Finally, we show that if the number of subsets forming the partition is fixed then the considered problem is equivalent to the problem of finding a perfect matching of a given weight in an edge-weighted bipartite graph.Dynamics of a nonlinear differential advertising model with single parameter sales promotion strategyhttps://zbmath.org/1496.340852022-11-17T18:59:28.764376Z"Ma, Junhai"https://zbmath.org/authors/?q=ai:ma.junhai"Jiang, Hui"https://zbmath.org/authors/?q=ai:jiang.huiSummary: Advertising and sales promotion are two important specific marketing communications tools. In this paper, nonlinear differential equation and single parameter sales promotion strategy are introduced into an advertising model and investigated quantitatively. The existence and stability of period-\(nT\) (\(n = 1, 2, 4, 8\)) solutions are investigated. Interestingly, both period doubling bifurcation and inverse flip bifurcation occur at different parameter values in the same advertising model. The results show that the system enters into chaos from stable state through flip bifurcation and enters into stable state from chaos through inverse flip bifurcation. An effective control strategy, which suppresses flip bifurcation and promotes inverse flip bifurcation, is proposed to eliminate chaos. These results have some significant theoretical and practical value in related markets.Optimal shapes for tree rootshttps://zbmath.org/1496.354072022-11-17T18:59:28.764376Z"Bressan, Alberto"https://zbmath.org/authors/?q=ai:bressan.alberto"Galtung, Sondre T."https://zbmath.org/authors/?q=ai:galtung.sondre-tesdal"Sun, Qing"https://zbmath.org/authors/?q=ai:sun.qingA note on cores and quasi relative interiors in partially finite convex programminghttps://zbmath.org/1496.460772022-11-17T18:59:28.764376Z"Lindstrom, Scott B."https://zbmath.org/authors/?q=ai:lindstrom.scott-bSummary: The problem of minimizing an entropy functional subject to linear constraints is a useful example of partially finite convex programming. In the 1990s, Borwein and Lewis provided broad and easy-to-verify conditions that guarantee strong duality for such problems. Their approach is to construct a function in the quasi-relative interior of the relevant infinite-dimensional set, which assures the existence of a point in the core of the relevant finite-dimensional set. We revisit this problem, and provide an alternative proof by directly appealing to the definition of the core, rather than by relying on any properties of the quasi-relative interior. Our approach admits a minor relaxation of the linear independence requirements in Borwein and Lewis' framework, which allows us to work with certain piecewise-defined moment functions precluded by their conditions. We provide such a computed example that illustrates how this relaxation may be used to tame observed Gibbs phenomenon when the underlying data is discontinuous. The relaxation illustrates the understanding we may gain by tackling partially-finite problems from both the finite-dimensional and infinite-dimensional sides. The comparison of these two approaches is informative, as both proofs are constructive.Conditions for discreteness of the spectrum to Schrödinger operator via non-increasing rearrangement, Lagrangian relaxation and perturbationshttps://zbmath.org/1496.470722022-11-17T18:59:28.764376Z"Zelenko, Leonid"https://zbmath.org/authors/?q=ai:zelenko.leonidConsider the Schrödinger operator \(H=-\Delta +V(x)\) on \(L_2(\mathbb{R}^d)\) with \(d\ge3\). This paper investigates sufficient conditions for which \(H\) has discrete spectrum. Unlike its related results in other literature, the author intends to obtain practical conditions for having discrete spectrum that can be easily verified in practice. In his previous work, the author presented sufficient conditions for discrete spectrum in terms of non-increasing rearrangement of the potential \(V(x)\). In this paper, the author continues to look for further sufficient conditions for the same matter. The method of Lagrangian relaxation for optimization is applied to formulate a new result in terms of expectation and deviation of \(V(x)\). The paper also includes some results on perturbations of \(V(x)\) that preserve discreteness of the spectrum of \(H\).
Reviewer: Miyeon Kwon (Platteville)Some remarks on regularized nonconvex variational inequalitieshttps://zbmath.org/1496.470892022-11-17T18:59:28.764376Z"Balooee, Javad"https://zbmath.org/authors/?q=ai:balooee.javad"Kim, Jong Kyu"https://zbmath.org/authors/?q=ai:kim.jong-kyuSummary: In this paper, we investigate and analyze the nonconvex variational inequalities introduced by \textit{M. A. Noor} in [Optim. Lett. 3, No. 3, 411--418 (2009; Zbl 1171.58307)] and [Comput. Math. Model. 21, No. 1, 97--108 (2010; Zbl 1201.65114)] and prove that the algorithms and results in the above mentioned papers are not valid. To overcome the problems in the above cited papers, we introduce and consider a new class of variational inequalities, named regularized nonconvex variational inequalities, instead of the class of nonconvex variational inequalities introduced in the above mentioned papers. We also consider a class of nonconvex Wiener-Hopf equations and establish the equivalence between the regularized nonconvex variational inequalities and the fixed point problems as well as the nonconvex Wiener-Hopf equations. By using the obtained equivalence formulations, we prove the existence of a unique solution for the regularized nonconvex variational inequalities and propose some projection iterative schemes for solving the regularized nonconvex variational inequalities. We also study the convergence analysis of the suggested iterative schemes under some certain conditions.Set-valued mixed quasi-equilibrium problems with operator solutionshttps://zbmath.org/1496.470902022-11-17T18:59:28.764376Z"Ram, Tirth"https://zbmath.org/authors/?q=ai:ram.tirth"Khanna, Anu Kumari"https://zbmath.org/authors/?q=ai:khanna.anu-kumari"Kour, Ravdeep"https://zbmath.org/authors/?q=ai:kour.ravdeepSummary: In this paper, we introduce and study generalized mixed operator quasi-equilibrium problems (GMQOEP) in Hausdorff topological vector spaces and prove the existence results for the solution of (GMQOEP) in compact and noncompact settings by employing 1-person game theorems. Moreover, using coercive condition, hemicontinuity of the functions and KKM theorem, we prove new results on the existence of solution for the particular case of (GMQOEP), that is, generalized mixed operator equilibrium problem (GMOEP).A Tseng extragradient method for solving variational inequality problems in Banach spaceshttps://zbmath.org/1496.471012022-11-17T18:59:28.764376Z"Oyewole, O. K."https://zbmath.org/authors/?q=ai:oyewole.olawale-kazeem|oyewole.olalwale-k"Abass, H. A."https://zbmath.org/authors/?q=ai:abass.hammad-anuoluwapo|abass.hammed-anuoluwapo"Mebawondu, A. A."https://zbmath.org/authors/?q=ai:mebawondu.akindele-adebayo"Aremu, K. O."https://zbmath.org/authors/?q=ai:aremu.kazeem-olalekanSummary: This paper presents an inertial Tseng extragradient method for approximating a solution of the variational inequality problem. The proposed method uses a single projection onto a half space which can be easily evaluated. The method considered in this paper does not require the knowledge of the Lipschitz constant as it uses variable stepsizes from step to step which are updated over each iteration by a simple calculation. We prove a strong convergence theorem of the sequence generated by this method to a solution of the variational inequality problem in the framework of a 2-uniformly convex Banach space which is also uniformly smooth. Furthermore, we report some numerical experiments to illustrate the performance of this method. Our result extends and unifies corresponding results in this direction in the literature.Equilibrium problems with complementarity constraints in Banach spaces: stationarity concepts, applications and algorithmshttps://zbmath.org/1496.490012022-11-17T18:59:28.764376Z"Becker, Jan"https://zbmath.org/authors/?q=ai:becker.jan-dirk|becker.jan-michael|becker.jan-steffenSummary: In mathematics, the field of non-cooperative game theory models the competition between several parties, which are called players. Therein, each player tries to reach an individual goal, which is described by an optimization problem. However and in contrast to classical nonlinear programming, there exists a dependency between the players, i.e. the choice of a suitable strategy influences the behavior and the reward of the player's opponents and vice versa. For this reason, a popular solution concept is given by Nash equilibria, which were introduced by John Forbes Nash in his Ph.D. thesis in 1950. In order to prove the existence of a Nash equilibrium, the convexity of the underlying optimization problem is a central requirement. However, this assumption does not hold in general. This thesis is devoted to special equilibrium problems in Banach spaces, which can be described by equilibrium problems with equilibrium/complementarity constraints (EPEC/EPCC). Due to the structure of the underlying feasible set, those games are nonconvex. Motivated by known results with respect to mathematical programs with complementarity constraints, we focus on weaker Nash equilibrium concepts, which can at least be seen as necessary conditions for a Nash equilibrium under suitable assumptions. In the first part of this work, we concentrate on multi-leader multi-follower games, where the participating players are divided hierarchically into leaders and followers, which compete on their particular level with each other. Under suitable assumptions, the solution of the lower level is described by its necessary and sufficient first-order optimality system and can be written as an EPCC. In this context, we first analyze the latter problem in abstract Banach spaces and afterwards, consider the special case of a multi-leader single-follower game (MLFG), where the lower level is given by a quadratic problem in a Hilbert space. For the latter one, we show on the basis of two known penalization techniques that there exist sequences of auxiliary equilibrium problems, which approximate the corresponding EPCC. In the following application that extends known contributions on an optimal control framework of the obstacle problem, we use these auxiliary games and show that both generate sequences, which converge at least to an ϵ-almost C-stationary Nash equilibrium of the original MLFG. The results are analyzed numerically on the basis of a Gauß-Seideltype algorithm and are tested with respect to two examples. The second part is motivated by the work ``A generalized Nash equilibrium approach for optimal control problems of autonomous cars'' by \textit{A. Dreves} and \textit{M. Gerdts} [Optim. Control Appl. Methods 39, No. 1, 326--342 (2018; Zbl 1390.49046)], where a traffic scenario between several intelligent cars is modeled by a dynamic equilibrium problem. Due to the collision avoidance constraint, this game is non-convex. However, we show that it can be written as a generalized Nash equilibrium problem with mixed-integer variables (MINEP), which again is equivalent to an EPCC. In contrast to the first application, we now concentrate on problems in Lebesgue spaces. In the following, we compare known results from abstract Banach spaces and the corresponding ones in Lebesgue spaces. In particular, we show that for general MINEPs all weak Nash equilibrium concepts coincide. Based on these observations, we apply the results to the traffic scenario. In this context, we again use a penalization technique and deduce by the generated sequence of Nash equilibrium problems that we find a sequence of equilibrium points, which converge to an S-stationary Nash equilibrium of MINEP. We end up with a numerical analysis and test the results with two hypothetical traffic scenarios.On the applications of a minimax theoremhttps://zbmath.org/1496.490052022-11-17T18:59:28.764376Z"Ricceri, Biagio"https://zbmath.org/authors/?q=ai:ricceri.biagioIn this paper, a minimax theorem is presented and four applications are given: uniquely remotal sets in normed spaces; multiple global minima for the integral functional of the Calculus of Variations; multiple periodic solutions for Lagrangian systems of relativistic oscillators; variational inequalities in balls of Hilbert spaces. A related challenging open problem is also pointed out.
Reviewer: Yang Yang (Wuxi)Inertial methods for solving system of quasi variational inequalitieshttps://zbmath.org/1496.490082022-11-17T18:59:28.764376Z"Jabeen, Saudia"https://zbmath.org/authors/?q=ai:jabeen.saudia"Noor, Muhammad Aslam"https://zbmath.org/authors/?q=ai:noor.muhammad-aslam"Noor, Khalida Inayat"https://zbmath.org/authors/?q=ai:noor.khalida-inayatSummary: In this paper, we consider a system of quasi variational inequalities involving two arbitrary mappings. It is shown that the system of quasi variational inequalities is equivalent to the fixed point problem using the projection method. We use this alternative formulation to suggest some new inertial projection methods. The convergence criteria of the new methods is analyzed under some appropriate conditions. Several special cases are discussed as applications of the results. It is interesting problem to consider the implementation of the proposed methods with other similar techniques. The concept of this paper may inspire future research in this area. Results obtained in this paper can be viewed as refinement and improvement of previously known results.Optimal control for uncertain random singular systems with multiple time-delayshttps://zbmath.org/1496.490152022-11-17T18:59:28.764376Z"Chen, Xin"https://zbmath.org/authors/?q=ai:chen.xin|chen.xin.1"Zhu, Yuanguo"https://zbmath.org/authors/?q=ai:zhu.yuanguoSummary: Chance theory provides us a useful tool to solve an optimal control problem with indeterminacy composing of both uncertainty and randomness. Based on chance theory, this paper studies an optimal control for uncertain random singular systems with multiple time-delays. First, an uncertain random singular system with multiple time-delays is introduced, and then the corresponding optimal control problem is established. The equivalent relationship between this problem and the optimal control problem for standard uncertain random systems is derived. Then the appropriate recurrence equations are proposed according to the dynamic programming method. Furthermore, two kinds of optimal control problems are discussed. The optimal control inputs and respective optimal values of the problems are provided via the solvability of the obtained equations. Finally, a numerical example is presented to show the effectiveness of our theoretical results.A suboptimal control of linear time-delay problems via dynamic programminghttps://zbmath.org/1496.490182022-11-17T18:59:28.764376Z"Gooran Orimi, Atefeh"https://zbmath.org/authors/?q=ai:gooran-orimi.atefeh"Effati, Sohrab"https://zbmath.org/authors/?q=ai:effati.sohrab"Farahi, Mohammad Hadi"https://zbmath.org/authors/?q=ai:farahi.mohammad-hadiSummary: We study a class of infinite horizon optimal control problems with a state delay, and investigate the dynamic programming approach which leverages the sufficient optimality conditions and provides a closed-loop solution. Importantly, the well-known Lyapunov-Krasovskii functional is applied to relate the solution of the problem to the solution of a set of three Riccati-type matrix differential equations. We then present an analytic-based approach to solve the resultant equations and subsequently provide a suboptimal closed-loop solution for the considered problem. We prove the uniform convergence of the proposed approach and show that the presented closed-loop system is asymptotically stable in the Lyapunov sense. Furthermore, the observability of the linear time-delay system is discussed and proved. Finally, numerical examples illustrate the efficiency of the proposed method.Approximation and mean field control of systems of large populationshttps://zbmath.org/1496.490202022-11-17T18:59:28.764376Z"Higuera-Chan, Carmen G."https://zbmath.org/authors/?q=ai:higuera-chan.carmen-gSummary: We deal with a class of discrete-time stochastic controlled systems composed by a large population of \(N\) interacting individuals. Given that \(N\) is large and the cost function is possibly unbounded, the problem is studied by means of a limit model \(\mathcal{M}\), known as the mean field model, which is obtained as limit as \(N \rightarrow \infty\) of the model \(\mathcal{M}_N\) corresponding to the system of \(N\) individuals in combination with an approximate algorithm for the cost function.
For the entire collection see [Zbl 1478.60006].On lattice width of lattice-free polyhedra and height of Hilbert baseshttps://zbmath.org/1496.520152022-11-17T18:59:28.764376Z"Henk, Martin"https://zbmath.org/authors/?q=ai:henk.martin"Kuhlmann, Stefan"https://zbmath.org/authors/?q=ai:kuhlmann.stefan"Weismantel, Robert"https://zbmath.org/authors/?q=ai:weismantel.robertStationary distributions and ergodicity of reflection-type Markov chainshttps://zbmath.org/1496.600852022-11-17T18:59:28.764376Z"Liu, Yujie"https://zbmath.org/authors/?q=ai:liu.yujie"Niu, Minwen"https://zbmath.org/authors/?q=ai:niu.minwen"Yao, Dacheng"https://zbmath.org/authors/?q=ai:yao.dacheng"Zhang, Hanqin"https://zbmath.org/authors/?q=ai:zhang.hanqinThe paper considers a so-called reflection-type Markov chain (RTMC). This RTMC is usually used to characterize some process features in stochastic control and operations management.
Regarding that this RTMC is the Feller chain, the existence of its stationary distributions is proved. Also, ergodicity of this RTMC is obtained by constructing the small set. Moreover, for the non-ergodic case, the system dynamics are completely described.
Reviewer: Anatoliy Swishchuk (Calgary)A two-server bulk service queuing model with a permanent server and a temporary server on holdhttps://zbmath.org/1496.601102022-11-17T18:59:28.764376Z"Bakuli, Kuntal"https://zbmath.org/authors/?q=ai:bakuli.kuntal"Pal, Manisha"https://zbmath.org/authors/?q=ai:pal.manishaSummary: In this paper, we consider a bulk service queuing model with a fixed bulk size and a single permanent server. An additional server is kept on hold and is allowed to serve when the queue length exceeds certain threshold value. The model is analyzed using embedded Markov chain. A comparison of the performance of the model with the following models have also been made -- (i) two-server bulk service model, (ii) bulk service model with two independent queues corresponding to two servers and (iii) a single-server bulk service model with double service capacity of the server.Efficient steady-state simulation of high-dimensional stochastic networkshttps://zbmath.org/1496.601112022-11-17T18:59:28.764376Z"Blanchet, Jose"https://zbmath.org/authors/?q=ai:blanchet.jose-h"Chen, Xinyun"https://zbmath.org/authors/?q=ai:chen.xinyun"Si, Nian"https://zbmath.org/authors/?q=ai:si.nian"Glynn, Peter W."https://zbmath.org/authors/?q=ai:glynn.peter-wSummary: We propose and study an asymptotically optimal Monte Carlo estimator for steady-state expectations of a \(d\)-dimensional reflected Brownian motion (RBM). Our estimator is asymptotically optimal in the sense that it requires \(\tilde{O}(d)\) (up to logarithmic factors in \(d)\) independent and identically distributed scalar Gaussian random variables in order to output an estimate with a controlled error. Our construction is based on the analysis of a suitable multilevel Monte Carlo strategy which, we believe, can be applied widely. This is the first algorithm with linear complexity (under suitable regularity conditions) for a steady-state estimation of RBM as the dimension increases.The prelimit generator comparison approach of Stein's methodhttps://zbmath.org/1496.601122022-11-17T18:59:28.764376Z"Braverman, Anton"https://zbmath.org/authors/?q=ai:braverman.antonSummary: This paper uses the generator comparison approach of Stein's method to analyze the gap between steady-state distributions of Markov chains and diffusion processes. The ``standard'' generator comparison approach starts with the Poisson equation for the diffusion, and the main technical difficulty is to obtain bounds on the derivatives of the solution to the Poisson equation, also known as Stein factor bounds. In this paper we propose starting with the Poisson equation of the Markov chain; we term this the \textit{prelimit approach}. Although one still needs Stein factor bounds, they now correspond to finite differences of the Markov chain Poisson equation solution rather than the derivatives of the solution to the diffusion Poisson equation. In certain cases, the former are easier to obtain. We use the \(M / M / 1\) model as a simple working example to illustrate our approach.Approximations and optimal control for state-dependent limited processor sharing queueshttps://zbmath.org/1496.601132022-11-17T18:59:28.764376Z"Gupta, Varun"https://zbmath.org/authors/?q=ai:gupta.varun|gupta.varun.1|gupta.varun.2"Zhang, Jiheng"https://zbmath.org/authors/?q=ai:zhang.jihengAuthors' abstract: The paper studies approximations and control of a processor sharing (PS) server where the service rate depends on the number of jobs occupying the server. The control of such a system is implemented by imposing a limit on the number of jobs that can share the server concurrently, with the rest of the jobs waiting in a first-in-first-out (FIFO) buffer. A desirable control scheme should strike the right balance between efficiency (operating at a high service rate) and parallelism (preventing small jobs from getting stuck behind large ones). We use the framework of heavy-traffic diffusion analysis to devise near optimal control heuristics for such a queueing system. However, although the literature on diffusion control of state-dependent queueing systems begins with a sequence of systems and an exogenously defined drift function, we begin with a finite discrete PS server and propose an axiomatic recipe to explicitly construct a sequence of state-dependent PS servers that then yields a drift function. We establish diffusion approximations and use them to obtain insightful and closed-form approximations for the original system under a static concurrency limit control policy. We extend our study to control policies that dynamically adjust the concurrency limit. We provide two novel numerical algorithms to solve the associated diffusion control problem. Our algorithms can be viewed as ``average cost'' iteration: The first algorithm uses binary-search on the average cost, while the second faster algorithm uses Newton-Raphson method for root finding. Numerical experiments demonstrate the accuracy of our approximation for choosing optimal or near-optimal static and dynamic concurrency control heuristics.
Reviewer: Vyacheslav Abramov (Melbourne)Queueing models for cognitive wireless networks with sensing time of secondary usershttps://zbmath.org/1496.601142022-11-17T18:59:28.764376Z"Phung-Duc, Tuan"https://zbmath.org/authors/?q=ai:phung-duc.tuan"Akutsu, Kohei"https://zbmath.org/authors/?q=ai:akutsu.kohei"Kawanishi, Ken'ichi"https://zbmath.org/authors/?q=ai:kawanishi.kenichi"Salameh, Osama"https://zbmath.org/authors/?q=ai:salameh.osama"Wittevrongel, Sabine"https://zbmath.org/authors/?q=ai:wittevrongel.sabineSummary: This paper considers queueing models for cognitive radio networks that account for the sensing time of secondary users (SUs). In cognitive radio networks, secondary users are allowed to opportunistically use idle channels originally allocated to primary users (PUs). To this end, SUs must sense the state of the channels before transmission. After sensing, if an idle channel is available, the SU can start transmission immediately; otherwise, the SU must carry out another channel sensing. In this paper, we study two retrial queueing models with an unlimited number of sensing SUs, where PUs have preemptive priority over SUs. The two models differ in whether or not an arriving PU can interrupt a SU transmission also in case there are still idle channels available. We show that both models have the same stability condition and that the model without interruptions in case of available idle channels has a slightly lower number of sensing SUs than the model with interruptions.On some properties of \(\alpha\)-mixtureshttps://zbmath.org/1496.621082022-11-17T18:59:28.764376Z"Shojaee, Omid"https://zbmath.org/authors/?q=ai:shojaee.omid"Asadi, Majid"https://zbmath.org/authors/?q=ai:asadi.majid"Finkelstein, Maxim"https://zbmath.org/authors/?q=ai:finkelstein.maximThe paper studies several properties of \(\alpha\)-mixtures for survival functions. The theoretical demonstrations refer to the ageing properties for additive and multiplicative hazards, the partial stochastic and hazard rate orderings of the finite \(\alpha\)-mixtures and the extension of bending properties to this type of mixtures.
Reviewer: Catalin Stoean (Craiova)Batch sequential adaptive designs for global optimizationhttps://zbmath.org/1496.621352022-11-17T18:59:28.764376Z"Xiao, Yao"https://zbmath.org/authors/?q=ai:xiao.yao"Ning, Jianhui"https://zbmath.org/authors/?q=ai:ning.jianhui"Xiong, Zikang"https://zbmath.org/authors/?q=ai:xiong.zikang"Qin, Hong"https://zbmath.org/authors/?q=ai:qin.hong.2|qin.hong.1|qin.hongSummary: Efficient global optimization (EGO) is one of the most popular sequential adaptive design (SAD) methods for expensive black-box optimization problems. A well-recognized weakness of the original EGO in complex computer experiments is that it is serial, and hence the modern parallel computing techniques cannot be utilized to speed up the running of simulator experiments. For those multiple points EGO methods, the heavy computation and points clustering are the obstacles. In this work, a novel batch SAD method, named ``Accelerated EGO'', is forwarded by using a refined sampling/importance resampling (SIR) method to search the points with large expected improvement (EI) values. The computation burden of the new method is much lighter, and the points clustering is also avoided. The efficiency of the proposed batch SAD is validated by nine classic test functions with dimension from 2 to 12. The empirical results show that the proposed algorithm indeed can parallelize original EGO, and gain much improvement compared against the other parallel EGO algorithm especially under high-dimensional case. Additionally, the new method is applied to the hyper-parameter tuning of support vector machine (SVM) and XGBoost models in machine learning. Accelerated EGO obtains comparable cross validation accuracy with other methods and the CPU time can be reduced a lot due to the parallel computation and sampling method.A Markov chain theory approach to characterizing the minimax optimality of stochastic gradient descent (for least squares)https://zbmath.org/1496.621402022-11-17T18:59:28.764376Z"Jain, Prateek"https://zbmath.org/authors/?q=ai:jain.prateek"Kakade, Sham M."https://zbmath.org/authors/?q=ai:kakade.sham-m"Kidambi, Rahul"https://zbmath.org/authors/?q=ai:kidambi.rahul"Netrapalli, Praneeth"https://zbmath.org/authors/?q=ai:netrapalli.praneeth"Pillutla, Venkata Krishna"https://zbmath.org/authors/?q=ai:pillutla.venkata-krishna"Sidford, Aaron"https://zbmath.org/authors/?q=ai:sidford.aaronSummary: This work provides a simplified proof of the statistical minimax optimality of (iterate averaged) stochastic gradient descent (SGD), for the special case of least squares. This result is obtained by analyzing SGD as a stochastic process and by sharply characterizing the stationary covariance matrix of this process. The finite rate optimality characterization captures the constant factors and addresses model mis-specification.
For the entire collection see [Zbl 1388.68010].Multivariate deep learning model with ensemble pruning for time series forecastinghttps://zbmath.org/1496.621612022-11-17T18:59:28.764376Z"Kosuri, Mohit"https://zbmath.org/authors/?q=ai:kosuri.mohit"Tandu, Cherry"https://zbmath.org/authors/?q=ai:tandu.cherry"Sarkar, Sobhan"https://zbmath.org/authors/?q=ai:sarkar.sobhan"Maiti, J."https://zbmath.org/authors/?q=ai:maiti.jyotirmoySummary: To predict future events using historical data, Time Series Forecasting (TSF) should be used to get precise and accurate predictions. It has been a challenging issue to deal with the errors and value loss while predicting the future; hence, a dynamic error correction is proposed to overcome the errors. Additionally, it is important to find out a fast optimization technique to avoid this difficulty. Therefore, it is proposed in this study to use an improved stacking-based ensemble pruning method, namely Genetic Algorithm (GA)-II to produce high accuracy and strong stability in time series forecasting. A meta predictor known as Kernel Ridge Regression (KRR) is proposed for stacking ensemble models for its improved forecasting performance. The main goal of this study is to attain reliable and precise time-series forecasting. In the process of extracting various types of data features, particular types of Deep Neural networks are effective. Therefore, these types of models combine and increase the use of Deep Learning and Ensemble Learning techniques. It is better to use different Deep Neural Networks as Deep Learning models and use boosting and stacking techniques as neural networks take more time by using these types of methods, and the results would be better with low calculations. In time-series data, the value changes dynamically which may increase or decrease the accuracy of the prediction, so to overcome this type of problem, some error correction methods like Dynamic Error Correction (DEC) and a technique like Non-Dominated Sorting Genetic Algorithm (NSGA) and Multi-Populated Non-Dominated Sorting Genetic Algorithm-II (GA-II) to get optimal solutions in terms of accuracy are used.
For the entire collection see [Zbl 1491.65006].A two-fold multi-objective multi-verse optimization-based time series forecastinghttps://zbmath.org/1496.621622022-11-17T18:59:28.764376Z"Tandu, Cherry"https://zbmath.org/authors/?q=ai:tandu.cherry"Kosuri, Mohit"https://zbmath.org/authors/?q=ai:kosuri.mohit"Sarkar, Sobhan"https://zbmath.org/authors/?q=ai:sarkar.sobhan"Maiti, J."https://zbmath.org/authors/?q=ai:maiti.jyotirmoySummary: In this study, to overcome error due to high-dimensional data and to get the best forecasting prediction for time series data, we employ a feature selection method to obtain the best exploitation and exploratory performance. Due to a large number of irrelevant factors within data, it is imperative to classify the tasks by using a feature selection method. Therefore, a two-fold multi-objective multi-verse optimization as a feature selection optimization method has been proposed to obtain a trade-off between minimization loss and minimization of the number of features selected. The Convolution Neural Network (CNN) has been used as a basic predictor. A dynamic error correction is also proposed to reduce the error further to the deep learning models to get the best time series forecasting. However, many Multi-Objective Optimization techniques have been used to deal with high-dimensional data, the proposed method showed the best trade-off for feature selection.
For the entire collection see [Zbl 1491.65006].Some conditional reliability properties of \(k\)-out-of-\(n\) system composed of different types of components with discrete independent lifetimeshttps://zbmath.org/1496.621732022-11-17T18:59:28.764376Z"Jasiński, Krzysztof"https://zbmath.org/authors/?q=ai:jasinski.krzysztofA technical system is said to have a \(k\)-out-of-\(n\) structure if it works when at least \(k\) of the \(n\) components operate. The author of this paper considers reliability properties of a \(k\)-out-of-\(n\) system consisting of \(l\) (\(1 \leq l\leq n\)) different types of components with discrete, independent lifetimes. Some conditional survival functions of the lifetime of a used system are obtained, which are used to calculate two conditional failure probabilities for \(k\)-out-of-\(n\) systems. Under some conditions, it is shown that they are equal to the unconditional failure probability of a \(k\)-out-of-\((n-r)\) system for \(r < n-k+1\).
Reviewer: Yuehua Wu (Toronto)Distributed quasi-Newton derivative-free optimization method for optimization problems with multiple local optimahttps://zbmath.org/1496.650692022-11-17T18:59:28.764376Z"Gao, Guohua"https://zbmath.org/authors/?q=ai:gao.guohua"Wang, Yixuan"https://zbmath.org/authors/?q=ai:wang.yixuan"Vink, Jeroen C."https://zbmath.org/authors/?q=ai:vink.jeroen-c"Wells, Terence J."https://zbmath.org/authors/?q=ai:wells.terence-j"Saaf, Fredrik J. F. E."https://zbmath.org/authors/?q=ai:saaf.fredrik-j-f-eSummary: The distributed Gauss-Newton (DGN) optimization method performs quite efficiently and robustly for history-matching problems with multiple best matches. However, this method is not applicable for generic optimization problems, e.g., life-cycle production optimization or well location optimization. This paper introduces a generalized form of the objective functions \(F(\boldsymbol{x}, \boldsymbol{y}(\boldsymbol{x})) = f(\boldsymbol{x})\) with both explicit variables \(\boldsymbol{x}\) and implicit variables (or simulated responses), \(\boldsymbol{y}(\boldsymbol{x})\). The split in explicit and implicit variables is such that partial derivatives of \(F(\boldsymbol{x}, \boldsymbol{y})\) with respect to both \(\boldsymbol{x}\) and \(\boldsymbol{y}\) can be computed analytically. An ensemble of quasi-Newton optimization threads is distributed among multiple high-performance-computing (HPC) cluster nodes. The simulation results generated from one optimization thread are shared with others by updating a common set of training data points, which records simulated responses of all simulation jobs. The sensitivity matrix at the current best solution of each optimization thread is approximated by the linear-interpolation method. The gradient of the objective function is then analytically computed using its partial derivatives with respect to \(\boldsymbol{x}\) and \(\boldsymbol{y}\) and the estimated sensitivities of \(\boldsymbol{y}\) with respect to \(\boldsymbol{x}\). The Hessian is updated using the quasi-Newton formulation. A new search point for each distributed optimization thread is generated by solving a quasi-Newton trust-region subproblem (TRS) for the next iteration. The proposed distributed quasi-Newton (DQN) method is first validated on a synthetic history matching problem and its performance is found to be comparable with the DGN optimizer. Then, the DQN method is tested on a variety of optimization problems. For all test problems, the DQN method can find multiple optima of the objective function with reasonably small numbers of iterations.Efficient regularized Newton-type algorithm for solving convex optimization problemhttps://zbmath.org/1496.650702022-11-17T18:59:28.764376Z"Javed, Shazia"https://zbmath.org/authors/?q=ai:javed.shazia"Khan, Areeba"https://zbmath.org/authors/?q=ai:khan.areebaSummary: In this paper, the subspace properties of trust-region methods are employed to develop a regularized Newton-type (RNT) algorithm for solving convex optimization problem. The proposed RNT algorithm is analyzed for quadratic convergence under the local error bound conditions and global convergence for unconstrained convex optimization problems which may have singular Hessian at the solutions. Afterwards numerical results are presented to show the efficiency and robustness of the proposed algorithm in producing an optimal solution for the given problem.Factual power loss reduction by meadow fritillary butterfly optimization algorithmhttps://zbmath.org/1496.650712022-11-17T18:59:28.764376Z"Kanagasabai, Lenin"https://zbmath.org/authors/?q=ai:kanagasabai.leninSummary: In this work, Improved Meadow Fritillary Butterfly (IMB) optimization algorithm is designed for power loss reduction. In the Meadow Fritillary Butterfly optimization algorithm, the exploration method has two properties of Meadow Fritillary butterflies; in that butterfly adjusting operator in preliminary iterations remarkably directs the exploration procedure in the direction of the present most outstanding solution. To trounce this deficit, firefly's algorithm exploration method has been incorporated into the standard Meadow Fritillary optimization algorithm. Meadow Fritillary Butterfly (IMB) optimization algorithm validated in IEEE 30 and 57 bus test systems and Decline in loss has been attained.
For the entire collection see [Zbl 1491.65006].Optimization and learning with nonlocal calculushttps://zbmath.org/1496.650722022-11-17T18:59:28.764376Z"Nagaraj, Sriram"https://zbmath.org/authors/?q=ai:nagaraj.sriramSummary: Nonlocal models have recently had a major impact in nonlinear continuum mechanics and are used to describe physical systems/processes which cannot be accurately described by classical, calculus based ``local'' approaches. In part, this is due to their multiscale nature that enables aggregation of micro-level behavior to obtain a macro-level description of singular/irregular phenomena such as peridynamics, crack propagation, anomalous diffusion and transport phenomena. At the core of these models are \textit{nonlocal} differential operators, including nonlocal analogs of the gradient/Hessian. This paper initiates the use of such nonlocal operators in the context of optimization and learning. We define and analyze the convergence properties of nonlocal analogs of (stochastic) gradient descent and Newton's method on Euclidean spaces. Our results indicate that as the nonlocal interactions become less noticeable, the optima corresponding to nonlocal optimization converge to the ``usual'' optima. At the same time, we argue that nonlocal learning is possible in situations where standard calculus fails. As a stylized numerical example of this, we consider the problem of non-differentiable parameter estimation on a non-smooth translation manifold and show that our \textit{nonlocal} gradient descent recovers the unknown translation parameter from a non-differentiable objective function.Convergence rate of the modified Levenberg-Marquardt method under Hölderian local error boundhttps://zbmath.org/1496.650732022-11-17T18:59:28.764376Z"Zheng, Lin"https://zbmath.org/authors/?q=ai:zheng.lin"Chen, Liang"https://zbmath.org/authors/?q=ai:chen.liang"Tang, Yangxin"https://zbmath.org/authors/?q=ai:tang.yangxinSummary: In this article, we analyze the convergence rate of the modified Levenberg-Marquardt (MLM) method under the Hölderian local error bound condition and the Hölderian continuity of the Jacobian, which are more general than the local error bound condition and the Lipschitz continuity of the Jacobian. Under special circumstances, the convergence rate of the MLM method coincides with the results presented by Fan. A globally convergent MLM algorithm by the trust region technique will also be given.WARPd: a linearly convergent first-order primal-dual algorithm for inverse problems with approximate sharpness conditionshttps://zbmath.org/1496.650742022-11-17T18:59:28.764376Z"Colbrook, Matthew J."https://zbmath.org/authors/?q=ai:colbrook.matthew-jThe selective projection method for convex feasibility and split feasibility problemshttps://zbmath.org/1496.650752022-11-17T18:59:28.764376Z"He, Songnian"https://zbmath.org/authors/?q=ai:he.songnian"Tian, Hanlin"https://zbmath.org/authors/?q=ai:tian.hanlin"Xu, Hong-Kun"https://zbmath.org/authors/?q=ai:xu.hong-kunSummary: A convex feasibility problem (CFP) is to find a point \(x^\ast\) with the property \(x^\ast\in\bigcap_{i=1}^mC^i \), where \(m\ge 1\) is an integer and \(\{C^i\}_{i=1}^m\) are closed convex subsets of a Hilbert space \(H\) with a common point. Projection methods are popular methods for solving CFP. Many projection algorithms in the existing literature have however to compute all the projections \(\{P_{C^i}\}_{i=1}^m\) in each iteration, which would be heavy computing workload and costly. It is therefore an interesting problem to invent new algorithms that can solve CFP efficiently and that compute as fewer projections as possible. In this paper we will introduce such new algorithms, which are called selective projection methods (SPM), for solving CFP in the case where each \(C^i\) is the level set of a convex function. In this case SPM computes only one projection in each iteration and also guarantees (weak) convergence. We also introduce relaxed SPM to project onto half-spaces to make SPM easily implementable. In addition we extend SPM to solve the multiple-sets split feasibility problems and the common fixed point problem of nonexpansive mappings.A spatial color compensation model using saturation-value total variationhttps://zbmath.org/1496.650772022-11-17T18:59:28.764376Z"Wang, Wei"https://zbmath.org/authors/?q=ai:wang.wei.39|wang.wei.15|wang.wei.36|wang.wei.41|wang.wei.12|wang.wei.23|wang.wei.24|wang.wei.16|wang.wei.9|wang.wei.38|wang.wei.30|wang.wei.21|wang.wei.20|wang.wei.25|wang.wei.46|wang.wei.27|wang.wei.13|wang.wei.45|wang.wei.47|wang.wei.8|wang.wei.28|wang.wei.3|wang.wei.2|wang.wei.34|wang.wei.50|wang.wei.49|wang.wei.1|wang.wei.40|wang.wei.19|wang.wei.31|wang.wei.32|wang.wei.29"Yang, Yuming"https://zbmath.org/authors/?q=ai:yang.yuming"Ng, Michael K."https://zbmath.org/authors/?q=ai:ng.michael-k|ng.michael-ka-shingThe global convergence of the BFGS method with a modified WWP line search for nonconvex functionshttps://zbmath.org/1496.650792022-11-17T18:59:28.764376Z"Yuan, Gonglin"https://zbmath.org/authors/?q=ai:yuan.gonglin"Li, Pengyuan"https://zbmath.org/authors/?q=ai:li.pengyuan"Lu, Junyu"https://zbmath.org/authors/?q=ai:lu.junyuSummary: The BFGS method, which has great numerical stability, is one of the quasi-Newton line search methods. However, the global convergence of the BFGS method with a Wolfe line search is still an open problem for general functions. Recently, \textit{G. Yuan} et al. [Appl. Math. Modelling 47, 811--825 (2017; Zbl 1446.65031)] presented a modified weak Wolfe-Powell (WWP) line search that globally converges for general functions; however, they only partially solved this open problem. In this paper, a further modified WWP line search is proposed, and the global convergence of the BFGS method is established under suitable conditions for general functions. The numerical results show that the new line search produces more interesting results than the normal line search. Moreover, a fact engineering problem is studied with the Muskingum model to show the performance of the presented algorithm.Adaptive three-term PRP algorithms without gradient Lipschitz continuity condition for nonconvex functionshttps://zbmath.org/1496.650802022-11-17T18:59:28.764376Z"Yuan, Gonglin"https://zbmath.org/authors/?q=ai:yuan.gonglin"Yang, Heshu"https://zbmath.org/authors/?q=ai:yang.heshu"Zhang, Mengxiang"https://zbmath.org/authors/?q=ai:zhang.mengxiangSummary: At present, many conjugate gradient methods with global convergence have been proposed in unconstrained optimization, such as MPRP algorithm proposed by \textit{L. Zhang} et al. [IMA J. Numer. Anal. 26, No. 4, 629--640 (2006; Zbl 1106.65056)]. Unfortunately, almost all of these methods require gradient Lipschitz continuity condition. As far as we know, how do the current conjugate gradient methods deal with gradient non-Lipschitz continuity problems is basically blank. For gradient non-Lipschitz continuity problems, Algorithm 1 and Algorithm 2 are proposed in this paper based on MPRP algorithm. The proposed algorithms have the following characteristics: (i) Algorithm 1 retains sufficient descent property independent of line search technology in MPRP algorithm; (ii) for nonconvex and gradient non-Lipschitz continuous functions, the global convergence of Algorithm 1 is obtained in combination with the trust region property and the weak Wolfe-Powell line search technique; (iii) based on Algorithm 1, Algorithm 2 is further improved which global convergence can be obtained independently of line search technique; (iv) according to numerical experiments, the proposed algorithms perform competitively with other similar algorithms.Control and numerical approximation of fractional diffusion equationshttps://zbmath.org/1496.651552022-11-17T18:59:28.764376Z"Biccari, Umberto"https://zbmath.org/authors/?q=ai:biccari.umberto"Warma, Mahamadi"https://zbmath.org/authors/?q=ai:warma.mahamadi"Zuazua, Enrique"https://zbmath.org/authors/?q=ai:zuazua.enriqueSummary: The aim of this chapter is to give a broad panorama of the control properties of fractional diffusive models from a numerical analysis and simulation perspective. We do this by surveying several research results we obtained in the last years, focusing in particular on the numerical computation of controls, though not forgetting to recall other relevant contributions which can be currently found in the literature of this prolific field. Our reference model will be a non-local diffusive dynamics driven by the fractional Laplacian on a bounded domain \(\Omega\). The starting point of our analysis will be a Finite Element approximation for the associated elliptic model in one and two space-dimensions, for which we also present error estimates and convergence rates in the \(L^2\) and energy norm. Secondly, we will address two specific control scenarios: firstly, we consider the standard interior control problem, in which the control is acting from a small subset \(\omega \subset \Omega\). Secondly, we move our attention to the exterior control problem, in which the control region \(\mathcal{O} \subset \Omega^c\) is located outside \(\Omega\). This exterior control notion extends boundary control to the fractional framework, in which the non-local nature of the models does not allow for controls supported on \(\partial \Omega\). We will conclude by discussing the interesting problem of simultaneous control, in which we consider families of parameter-dependent fractional heat equations and we aim at designing a unique control function capable of steering all the different realizations of the model to the same target configuration. In this framework, we will see how the employment of stochastic optimization techniques may help in alleviating the computational burden for the approximation of simultaneous controls. Our discussion is complemented by several open problems related with fractional models which are currently unsolved and may be of interest for future investigation.
For the entire collection see [Zbl 1492.49003].Competitive analysis of the online dial-a-ride problemhttps://zbmath.org/1496.680092022-11-17T18:59:28.764376Z"Birx, Alexander"https://zbmath.org/authors/?q=ai:birx.alexanderSummary: Online optimization, in contrast to classical optimization, deals with optimization problems whose input data is not immediately available, but instead is revealed piece by piece. An online algorithm has to make irrevocable optimization decisions based on the arriving pieces of data to compute a solution of the online problem. The quality of an online algorithm is measured by the competitive ratio, which is the quotient of the solution computed by the online algorithm and the optimum offline solution, i.e., the solution computed by an optimum algorithm that has knowledge about all data from the start.
In this thesis we examine the online optimization problem online Dial-a-Ride. This problem consists of a server starting at a distinct point of a metric space, called origin, and serving transportation requests that appear over time. The goal is to minimize the makespan, i.e., to complete serving all requests as fast as possible. We distinguish between a closed version, where the server is required to return to the origin, and an open version, where the server is allowed to stay at the destination of the last served request.
In this thesis, we provide new lower bounds for the competitive ratio of online Dial-a-Ride on the real line for both the open and the closed version by expanding upon the approach of Bjelde et al.'s work. In the case of the open version, the improved lower bound separates online Dial-a-Ride from its special case online TSP, where starting position and destination of requests coincide.
To produce improved upper bounds for the competitive ratio of online Dial-a-Ride, we generalize the design of the Ignore algorithm and the Smartstart algorithm into the class of schedule-based algorithms. We show lower bounds for the competitive ratios of algorithms of this class and then provide a thorough analysis of Ignore and Smartstart. Identifying and correcting a critical weakness of Smartstart gives us the improved Smarterstart algorithm. This schedule-based algorithm attains the best known upper bound for open online Dial-a-Ride on the real line as well as on arbitrary metric spaces.
Finally, we provide an analysis of the Replan algorithm improving several known bounds for the algorithm's competitive ratio.New perspectives on hybrid intelligent system design based on fuzzy logic, neural networks and metaheuristicshttps://zbmath.org/1496.680132022-11-17T18:59:28.764376ZPublisher's description: In this book, recent developments on fuzzy logic, neural networks and optimization algorithms, as well as their hybrid combinations, are presented. In addition, the above-mentioned methods are applied to areas such as, intelligent control and robotics, pattern recognition, medical diagnosis, time series prediction and optimization of complex problems. The book contains a collection of papers focused on hybrid intelligent systems based on soft computing techniques. There are some papers with the main theme of type-1 and type-2 fuzzy logic, which basically consists of papers that propose new concepts and algorithms based on type-1 and type-2 fuzzy logic and their applications. There also some papers that offer theoretical concepts and applications of meta-heuristics in different areas. Another group of papers describe diverse applications of fuzzy logic, neural networks and hybrid intelligent systems in medical problems. There are also some papers that present theory and practice of neural networks in different areas of application. In addition, there are papers that present theory and practice of optimization and evolutionary algorithms in different areas of application. Finally, there are some papers describing applications of fuzzy logic, neural networks and meta-heuristics in pattern recognition and classification problems.
The articles of mathematical interest will be reviewed individually.Approximation, randomization, and combinatorial optimization. Algorithms and techniques, APPROX/RANDOM 2022, University of Illinois, Urbana-Champaign, USA, virtual conference, September 19--21, 2022https://zbmath.org/1496.680142022-11-17T18:59:28.764376ZThe articles of this volume will be reviewed individually. For the preceding conferences see [Zbl 1473.68020].Modelling and development of intelligent systems. Proceedings of the fifth international conference, Sibiu, Romania, June 23--25, 2017https://zbmath.org/1496.680332022-11-17T18:59:28.764376ZThe articles of mathematical interest will be reviewed individually. For the preceding conference see [Zbl 1415.68047].
Indexed articles:
\textit{Ciurea, Stelian}, An imperialist competitive algorithm optimized to solve the traveling salesman problem, 20-28 [Zbl 1424.90225]
\textit{Sangeorzan, Livia; Enache-David, Nicoleta}, Theoretical and practical approaches for documents classification, 67-71 [Zbl 1410.68323]
\textit{Stoica, Florin; Bărbulescu, Alina; Stoica, Laura Florentina}, Tuning extreme learning machines with genetic algorithms, 72-81 [Zbl 1410.68324]
\textit{Tuba, Eva; Capor-Hrosik, Romana; Alihodzic, Adis; Beko, Marko; Jovanovic, Raka}, Moth search algorithm for bound constrained optimization problems, 82-89 [Zbl 1410.68344]Energy-efficient fast delivery by mobile agentshttps://zbmath.org/1496.680522022-11-17T18:59:28.764376Z"Bärtschi, Andreas"https://zbmath.org/authors/?q=ai:bartschi.andreas"Tschager, Thomas"https://zbmath.org/authors/?q=ai:tschager.thomasSummary: We consider the problem of collaboratively delivering a package from a specified source node \(s\) to a designated target node \(t\) in an undirected graph \(G=(V,E)\), using \(k\) mobile agents. Each agent \(i\) starts at time 0 at a node \(p_i\) and can move along edges subject to two parameters: its weight \(w_i\), which denotes the rate of energy consumption while travelling, and its velocity \(v_i\), which defines the speed with which agent \(i\) can travel.
We are interested in operating the agents such that we minimize the total energy consumption \(\mathcal {E}\) and the delivery time \(\mathcal {T}\) (time when the package arrives at \(t\)). Specifically, we are after a schedule of the agents that lexicographically minimizes the tuple \((\mathcal {E},\mathcal {T})\). We show that this problem can be solved in polynomial time \(\mathcal {O}(k|V|^2+\mathrm{APSP})\), where \(\mathcal {O}(\mathrm{APSP})\) denotes the running time of an all-pair shortest-paths algorithm. This completes previous research which shows that minimizing only \(\mathcal {E}\) or only \(\mathcal {T}\) is polynomial-time solvable
[the first author et al., LIPIcs -- Leibniz Int. Proc. Inform. 66, Article 10, 14 p. (2017; Zbl 1402.68178); LIPIcs -- Leibniz Int. Proc. Inform. 117, Article 56, 16 p. (2018; Zbl 07378373)],
while minimizing a convex combination of \(\mathcal {E}\) and \(\mathcal {T}\), or lexicographically minimizing the tuple \((\mathcal {T},\mathcal {E})\) are both \(\mathsf {NP}\)-hard
[Zbl 07378373].
For the entire collection see [Zbl 1369.68029].Incremental methods for optimizing partial instantiationhttps://zbmath.org/1496.680902022-11-17T18:59:28.764376Z"Ng, Raymond T."https://zbmath.org/authors/?q=ai:ng.raymond-t"Tian, Xiaomei"https://zbmath.org/authors/?q=ai:tian.xiaomeiSummary: It has been shown that mixed integer programming methods can effectively support minimal model, stable model and well-founded model semantics for ground deductive databases. Recently, a novel approach called partial instantiation has been developed which, when integrated with mixed integer programming methods, can handle non-ground logic programs. The goal of this paper is to explore how this integrated framework based on partial instantiation can be optimized. In particular, we develop an incremental algorithm that minimizes repetitive computations. We also develop optimization techniques to further enhance the efficiency of our incremental algorithm. Experimental results indicate that our algorithm and optimization techniques can bring about very significant improvement in run-time performance.
For the entire collection see [Zbl 0875.00116].Tableaux for policy synthesis for MDPs with PCTL* constraintshttps://zbmath.org/1496.681872022-11-17T18:59:28.764376Z"Baumgartner, Peter"https://zbmath.org/authors/?q=ai:baumgartner.peter"Thiébaux, Sylvie"https://zbmath.org/authors/?q=ai:thiebaux.sylvie"Trevizan, Felipe"https://zbmath.org/authors/?q=ai:trevizan.felipe-wSummary: Markov decision processes (MDPs) are the standard formalism for modelling sequential decision making in stochastic environments. Policy synthesis addresses the problem of how to control or limit the decisions an agent makes so that a given specification is met. In this paper we consider PCTL*, the probabilistic counterpart of CTL*, as the specification language. Because in general the policy synthesis problem for PCTL* is undecidable, we restrict to policies whose execution history memory is finitely bounded a priori. Surprisingly, no algorithm for policy synthesis for this natural and expressive framework has been developed so far. We close this gap and describe a tableau-based algorithm that, given an MDP and a PCTL* specification, derives in a non-deterministic way a system of (possibly nonlinear) equalities and inequalities. The solutions of this system, if any, describe the desired (stochastic) policies. Our main result in this paper is the correctness of our method, i.e., soundness, completeness and termination.
For the entire collection see [Zbl 1371.68015].The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problemshttps://zbmath.org/1496.682552022-11-17T18:59:28.764376Z"Brakensiek, Joshua"https://zbmath.org/authors/?q=ai:brakensiek.joshua"Guruswami, Venkatesan"https://zbmath.org/authors/?q=ai:guruswami.venkatesan"Wrochna, Marcin"https://zbmath.org/authors/?q=ai:wrochna.marcin"Živný, Stanislav"https://zbmath.org/authors/?q=ai:zivny.stanislavMinimum label \(s\)-\(t\) cut has large integrality gapshttps://zbmath.org/1496.682692022-11-17T18:59:28.764376Z"Zhang, Peng"https://zbmath.org/authors/?q=ai:zhang.peng|zhang.peng.1|zhang.peng.2"Tang, Linqing"https://zbmath.org/authors/?q=ai:tang.linqingSummary: The Min Label \(s\)-\(t\) Cut problem is a fundamental problem in combinatorial optimization. This problem comes from many applications in real world, for example, information security and computer networks. We study two linear programs for Min Label \(s\)-\(t\) Cut, proving that both of them have large integrality gaps, namely, \(\Omega(m)\) and \(\Omega(m^{1/3 - \epsilon})\) for the respective linear programs, where \(m\) is the number of edges in the input graph of the problem and \(\epsilon > 0\) is any arbitrarily small constant. As Min Label \(s\)-\(t\) Cut is NP-hard and the linear programming technique is a main approach to design approximation algorithms, our results give negative answer to the hope that designs can be found for better approximation algorithms for Min Label \(s\)-\(t\) Cut that purely rely on linear programming.Distributed block-diagonal approximation methods for regularized empirical risk minimizationhttps://zbmath.org/1496.682762022-11-17T18:59:28.764376Z"Lee, Ching-pei"https://zbmath.org/authors/?q=ai:lee.ching-pei"Chang, Kai-Wei"https://zbmath.org/authors/?q=ai:chang.kai-weiSummary: In recent years, there is a growing need to train machine learning models on a huge volume of data. Therefore, designing efficient distributed optimization algorithms for empirical risk minimization (ERM) has become an active and challenging research topic. In this paper, we propose a flexible framework for distributed ERM training through solving the dual problem, which provides a unified description and comparison of existing methods. Our approach requires only approximate solutions of the sub-problems involved in the optimization process, and is versatile to be applied on many large-scale machine learning problems including classification, regression, and structured prediction. We show that our framework enjoys global linear convergence for a broad class of non-strongly-convex problems, and some specific choices of the sub-problems can even achieve much faster convergence than existing approaches by a refined analysis. This improved convergence rate is also reflected in the superior empirical performance of our method.Discrete facility location in machine learninghttps://zbmath.org/1496.682822022-11-17T18:59:28.764376Z"Vasil'ev, Igor' Leonidovich"https://zbmath.org/authors/?q=ai:vasilev.igor-leonidovich"Ushakov, Anton Vladimirovich"https://zbmath.org/authors/?q=ai:ushakov.anton-vladimirovichSummary: Facility location problems form a wide class of optimization problems, extremely popular in combinatorial optimization and operations research. In any facility location problem, one must locate a set of facilities in order to satisfy the demands of customers so as a certain objective function is optimized. Besides numerous applications in public and private sectors, the problems are widely used in machine learning. For example, clustering can be viewed as a facility location problem where one needs to partition a set of customers into clusters assigned to open facilities. In this survey we briefly look at how ideas and approaches arisen in the field of facility location led to modern, popular machine learning algorithms supported by many data mining and machine learning software packages. We also review the state-of-the-art exact methods and heuristics, as well as some extensions of basic problems and algorithms arisen in applied machine learning tasks. Note that the main emphasis here lies on discrete facility location problems, which, for example, underlie many widely used clustering algorithms (PAM, affinity propagation, etc.). Since the high computational complexity of conventional facility location-based clustering algorithms hinders their application to modern large-scale real-life datasets, we also survey some modern approaches to implementation of the algorithms for such large data collections.MILP, pseudo-Boolean, and OMT solvers for optimal fault-tolerant placements of relay nodes in mission critical wireless networkshttps://zbmath.org/1496.683002022-11-17T18:59:28.764376Z"Chen, Qian Matteo"https://zbmath.org/authors/?q=ai:chen.qian-matteo"Finzi, Alberto"https://zbmath.org/authors/?q=ai:finzi.alberto"Mancini, Toni"https://zbmath.org/authors/?q=ai:mancini.toni"Melatti, Igor"https://zbmath.org/authors/?q=ai:melatti.igor"Tronci, Enrico"https://zbmath.org/authors/?q=ai:tronci.enricoSummary: In \textit{critical infrastructures} like airports, much care has to be devoted in protecting radio communication networks from external electromagnetic interference.
Protection of such \textit{mission-critical} radio communication networks is usually tackled by exploiting radiogoniometers: at least three suitably deployed radiogoniometers, and a gateway gathering information from them, permit to monitor and localise sources of electromagnetic emissions that are not supposed to be present in the monitored area. Typically, radiogoniometers are connected to the gateway through \textit{relay nodes}. As a result, some degree of fault-tolerance for the network of relay nodes is essential in order to offer a reliable monitoring. On the other hand, deployment of relay nodes is typically quite expensive. As a result, we have two conflicting requirements: minimise costs while guaranteeing a given fault-tolerance.
In this paper, we address the problem of computing a deployment for relay nodes that minimises the overall cost while at the same time guaranteeing proper working of the network even when some of the relay nodes (up to a given maximum number) become faulty (\textit{fault-tolerance}).
We show that, by means of a computation-intensive pre-processing on a HPC infrastructure, the above optimisation problem can be encoded as a 0/1 Linear Program, becoming suitable to be approached with standard Artificial Intelligence reasoners like MILP, PB-SAT, and SMT/OMT solvers. Our problem formulation enables us to present experimental results comparing the performance of these three solving technologies on a real case study of a relay node network deployment in areas of the Leonardo da Vinci Airport in Rome, Italy.Result diversification by multi-objective evolutionary algorithms with theoretical guaranteeshttps://zbmath.org/1496.683062022-11-17T18:59:28.764376Z"Qian, Chao"https://zbmath.org/authors/?q=ai:qian.chao"Liu, Dan-Xuan"https://zbmath.org/authors/?q=ai:liu.dan-xuan"Zhou, Zhi-Hua"https://zbmath.org/authors/?q=ai:zhou.zhihuaSummary: Given a ground set of items, the result diversification problem aims to select a subset with high ``quality'' and ``diversity'' while satisfying some constraints. It arises in various real-world artificial intelligence applications, such as web-based search, document summarization and feature selection, and also has applications in other areas, e.g., computational geometry, databases, finance and operations research. Previous algorithms are mainly based on greedy or local search. In this paper, we propose to reformulate the result diversification problem as a bi-objective maximization problem, and solve it by a multi-objective evolutionary algorithm (EA), i.e., the GSEMO. We theoretically prove that the GSEMO can achieve the (asymptotically) optimal theoretical guarantees under both static and dynamic environments. For cardinality constraints, the GSEMO can achieve the optimal polynomial-time approximation ratio, 1/2. For more general matroid constraints, the GSEMO can achieve an asymptotically optimal polynomial-time approximation ratio, \(1/2-\epsilon /(4 n)\), where \(\epsilon > 0\) and \(n\) is the size of the ground set of items. Furthermore, when the objective function (i.e., a linear combination of quality and diversity) changes dynamically, the GSEMO can maintain this approximation ratio in polynomial running time, addressing the open question proposed by
\textit{A. Borodin} et al. [ACM Trans. Algorithms 13, No. 3, Article No. 41, 25 p. (2017; Zbl 1452.68273)].
This also theoretically shows the superiority of EAs over local search for solving dynamic optimization problems for the first time, and discloses the robustness of the mutation operator of EAs against dynamic changes. Experiments on the applications of web-based search, multi-label feature selection and document summarization show the superior performance of the GSEMO over the state-of-the-art algorithms (i.e., the greedy algorithm and local search) under both static and dynamic environments.Introducing Pareto minimal correction subsetshttps://zbmath.org/1496.683072022-11-17T18:59:28.764376Z"Terra-Neves, Miguel"https://zbmath.org/authors/?q=ai:terra-neves.miguel"Lynce, Inês"https://zbmath.org/authors/?q=ai:lynce.ines"Manquinho, Vasco"https://zbmath.org/authors/?q=ai:manquinho.vasco-mSummary: A minimal correction subset (MCS) of an unsatisfiable constraint set is a minimal subset of constraints that, if removed, makes the constraint set satisfiable. MCSs enjoy a wide range of applications, one of them being approximate solutions to constrained optimization problems. However, existing work on applying MCS enumeration to optimization problems focuses on the single-objective case.
In this work, a first definition of Pareto minimal correction subsets (Pareto-MCSs) is proposed with the goal of approximating the Pareto-optimal solution set of multi-objective constrained optimization problems. We formalize and prove an equivalence relationship between Pareto-optimal solutions and Pareto-MCSs. Moreover, Pareto-MCSs and MCSs can be connected in such a way that existing state-of-the-art MCS enumeration algorithms can be used to enumerate Pareto-MCSs.
An experimental evaluation considers the multi-objective virtual machine consolidation problem. Results show that the proposed Pareto-MCS approach outperforms the state-of-the-art approaches.
For the entire collection see [Zbl 1368.68008].Automated non-monotonic reasoning in System \textbf{P}https://zbmath.org/1496.683412022-11-17T18:59:28.764376Z"Stojanović, Tatjana"https://zbmath.org/authors/?q=ai:stojanovic.tatjana"Ikodinović, Nebojša"https://zbmath.org/authors/?q=ai:ikodinovic.nebojsa"Davidović, Tatjana"https://zbmath.org/authors/?q=ai:davidovic.tatjana"Ognjanović, Zoran"https://zbmath.org/authors/?q=ai:ognjanovic.zoranSummary: This paper presents a novel approach to automated reasoning in System \textbf{P}. System \textbf{P} axiomatizes a set of core properties that describe reasoning with defeasible assertions (defaults) of the form: if \(\alpha\) then normally (usually or typically) \( \beta \). A logic with approximate conditional probabilities is used for modeling default rules. That representation enables reducing the satisfiability problem for default reasoning to the (non)linear programming problem. The complexity of the obtained instances requires the application of optimization approaches. The main heuristic that we use is the Bee Colony Optimization (BCO). As an alternative to BCO, we use Simplex method and Fourier-Motzkin Elimination method to solve linear programming problems. All approaches are tested on a set of default reasoning examples that can be found in literature. The general impression is that Fourier-Motzkin Elimination procedure is not suitable for practical use due to substantially high memory usage and time consuming execution, the Simplex method is able to provide useful results for some of the tested examples, while heuristic approach turns out to be the most appropriate in terms of both success rate and time needed for reaching conclusions. In addition, the BCO method was tested on a set of randomly generated examples of larger dimensions, illustrating its practical usability.SFCDecomp: multicriteria optimized tool path planning in 3D printing using space-filling curve based domain decompositionhttps://zbmath.org/1496.683532022-11-17T18:59:28.764376Z"Gupta, Prashant"https://zbmath.org/authors/?q=ai:gupta.prashant-k"Guo, Yiran"https://zbmath.org/authors/?q=ai:guo.yiran"Boddeti, Narasimha"https://zbmath.org/authors/?q=ai:boddeti.narasimha"Krishnamoorthy, Bala"https://zbmath.org/authors/?q=ai:krishnamoorthy.balaDeterministic approximation algorithm for submodular maximization subject to a matroid constrainthttps://zbmath.org/1496.683802022-11-17T18:59:28.764376Z"Sun, Xin"https://zbmath.org/authors/?q=ai:sun.xin|sun.xin.1"Xu, Dachuan"https://zbmath.org/authors/?q=ai:xu.dachuan"Guo, Longkun"https://zbmath.org/authors/?q=ai:guo.longkun"Li, Min"https://zbmath.org/authors/?q=ai:li.min.9|li.min.2|li.min.5|li.min.7|li.min.3|li.min.1|li.min.8|li.min|li.min.6|li.min.10|li.min.4The paper studies the generalized submodular maximization problem over a base set \(N\) with a non-negative monotone submodular set function \(f:2^N\rightarrow\mathbb{R}_{\ge 0}\) as the objective function and subject to a matroid constraint. The aim is to seek a subset \(S\) of \(N\), simultaneously satisfying the feasibility constraint of the matroid \(\mathcal{M}\) and maximizing the value of \(f\). The problem is generalized through the curvature parameter \(\alpha\in[0, 1]\) and we say that a submodular function \(f\) is with curvature \(\alpha\), if \(f(S\cup\{s\})-f(S)\ge(1-\alpha)f(\{s\})\) holds for any subset \(S\subset N\) and element \(s\in N\setminus S\).
The main result is a deterministic approximation algorithm for the above problem. The algorithm employs the deterministic algorithm devised by \textit{N. Buchbinder} et al. [in: Proceedings of the 30th annual ACM-SIAM symposium on discrete algorithms, SODA 2019. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 241--254 (2019; Zbl 1431.90125)] as a building block and it reaches the same ratio of 0.5008 when the curvature parameter \(\alpha = 1\), and approximation ratio 1 when \(\alpha = 0\). For a calibrating parameter \(y\in[0,1]\) the algorithm achieves the following approximation ratio:
\[
\frac{1 + h_\alpha(y) +\Delta\cdot[3 + \alpha-(2 + \alpha)y-(1 + \alpha)h_\alpha(y)]}{2 + \alpha + (1 + \alpha)(1-y)},
\]
where \(h_\alpha(y)\doteq\frac{1-(1-y)^{1+\alpha}}{1+\alpha}\).
Reviewer: Vladimír Lacko (Košice)An experimental comparison of algebraic crossover operators for permutation problemshttps://zbmath.org/1496.683832022-11-17T18:59:28.764376Z"Baioletti, Marco"https://zbmath.org/authors/?q=ai:baioletti.marco"Di Bari, Gabriele"https://zbmath.org/authors/?q=ai:di-bari.gabriele"Milani, Alfredo"https://zbmath.org/authors/?q=ai:milani.alfredo"Santucci, Valentino"https://zbmath.org/authors/?q=ai:santucci.valentinoSummary: Crossover operators are very important components in Evolutionary Computation. Here we are interested in crossovers for the permutation representation that find applications in combinatorial optimization problems such as the permutation flowshop scheduling and the traveling salesman problem. We introduce three families of permutation crossovers based on algebraic properties of the permutation space. In particular, we exploit the group and lattice structures of the space. A total of 34 new crossovers is provided. Algebraic and semantic properties of the operators are discussed, while their performances are investigated by experimentally comparing them with known permutation crossovers on standard benchmarks from four popular permutation problems. Three different experimental scenarios are considered and the results clearly validate our proposals.Algorithmization in structural optimizationhttps://zbmath.org/1496.741072022-11-17T18:59:28.764376Z"Nazirov, Sh. A."https://zbmath.org/authors/?q=ai:nazirov.shodmankula-abdirozikovich"Saidov, U. M."https://zbmath.org/authors/?q=ai:saidov.u-m(no abstract)Quantum speed limit and stability of coherent states in quantum gravityhttps://zbmath.org/1496.830162022-11-17T18:59:28.764376Z"Liegener, Klaus"https://zbmath.org/authors/?q=ai:liegener.klaus"Rudnicki, Łukasz"https://zbmath.org/authors/?q=ai:rudnicki.lukaszHandbook of combinatorial optimization. In 5 volumeshttps://zbmath.org/1496.900012022-11-17T18:59:28.764376ZPublisher's description: The second edition of this 5-volume handbook is intended to be a basic yet comprehensive reference work in combinatorial optimization that will benefit newcomers and researchers for years to come. This multi-volume work deals with several algorithmic approaches for discrete problems as well as with many combinatorial problems. The editors have brought together almost every aspect of this enormous field of combinatorial optimization, an area of research at the intersection of applied mathematics, computer science, and operations research and which overlaps with many other areas such as computation complexity, computational biology, VLSI design, communications networks, and management science. An international team of 30--40 experts in the field form the editorial board.
\begin{itemize}
\item this second edition features 30\% new additional content, additional chapters as well as updated content.
\item Editors-in-chief are renowned members of the operations research and mathematics communities.
\item subject spans much of applied mathematics, computer science and operations research as well as overlaps with many other fields such as computation complexity, computational biology, VLSI design, communications networks, and management science.
\end{itemize}
The Handbook of Combinatorial Optimization, second edition is addressed to all scientists who use combinatorial optimization methods to model and solve problems. Experts in the field as well as non-specialists will find the material stimulating and useful.
For the first edition see [Zbl 0903.90001; Zbl 0914.90001; Zbl 0914.90002; Zbl 1042.90002; Zbl 1058.90001].The GLOBAL optimization algorithm. Newly updated with Java implementation and parallelizationhttps://zbmath.org/1496.900022022-11-17T18:59:28.764376Z"Bánhelyi, Balázs"https://zbmath.org/authors/?q=ai:banhelyi.balazs"Csendes, Tibor"https://zbmath.org/authors/?q=ai:csendes.tibor"Lévai, Balázs"https://zbmath.org/authors/?q=ai:levai.balazs-l"Pál, László"https://zbmath.org/authors/?q=ai:pal.laszlo"Zombori, Dániel"https://zbmath.org/authors/?q=ai:zombori.danielPublisher's description: This book explores the updated version of the GLOBAL algorithm which contains improvements for a local search algorithm and new Java implementations. Efficiency comparisons to earlier versions and on the increased speed achieved by the parallelization, are detailed. Examples are provided for students as well as researchers and practitioners in optimization, operations research, and mathematics to compose their own scripts with ease. A GLOBAL manual is presented in the appendix to assist new users with modules and test functions.
GLOBAL is a successful stochastic multistart global optimization algorithm that has passed several computational tests, and is efficient and reliable for small to medium dimensional global optimization problems. The algorithm uses clustering to ensure efficiency and is modular in regard to the two local search methods it starts with, but it can also easily apply other local techniques. The strength of this algorithm lies in its reliability and adaptive algorithm parameters. The GLOBAL algorithm is free to download also in the earlier Fortran, C, and MATLAB implementations.Solution methods for multi-objective robust combinatorial optimizationhttps://zbmath.org/1496.900032022-11-17T18:59:28.764376Z"Thom, Lisa"https://zbmath.org/authors/?q=ai:thom.lisaSummary: This thesis addresses combinatorial optimization problems with several objectives containing uncertain parameters. A variety of robustness concepts for multi-objective optimization problems have been developed during the last years. This thesis provides methods to find so-called robust efficient solutions with respect to several of these concepts, assuming the uncertain parameters to be given via common uncertainty sets. Several solution approaches are presented, including extensions and combinations of algorithms from both robust and multi-objective optimization, using properties of particular uncertainty sets and robustness concepts. Beyond general combinatorial optimization problems, the shortest path problem is considered in particular. Solution algorithms are implemented and evaluated in numerical experiments.\texttt{Tenscalc}: a toolbox to generate fast code to solve nonlinear constrained minimizations and compute Nash equilibriahttps://zbmath.org/1496.900042022-11-17T18:59:28.764376Z"Hespanha, João P."https://zbmath.org/authors/?q=ai:hespanha.joao-pedroSummary: We describe the toolbox \texttt{Tenscalc} that generates specialized C-code to solve nonlinear constrained optimizations and to compute Nash equilibria. \texttt{Tenscalc} is aimed at scenarios where one needs to solve very fast a large number of optimizations that are structurally similar. This is common in applications where the optimizations depend on measured data and one wants to compute optima for large or evolving datasets, e.g., in robust estimation and classification, maximum likelihood estimation, model predictive control (MPC), moving horizon estimation (MHE), and combined MPC-MHE (which requires the computation of a saddle-point equilibria). \texttt{Tenscalc} is mostly aimed at generating solvers for optimizations with up to a few thousands of optimization variables/constraints and solve times up to a few milliseconds. The speed achieved by the solver arises from a combination of features: reuse of intermediate computations across and within iterations of the solver, detection and exploitation of matrix sparsity, avoidance of run-time memory allocation and garbage collection, and reliance on flat code that improves the efficiency of the microprocessor pipelining and caching. All these features have been automated and embedded into the code generation process. We include a few representative examples to illustrate how the speed and memory footprint of the solver scale with the size of the problem.Integer programming and combinatorial optimization. 21st international conference, IPCO 2020, London, UK, June 8--10, 2020, Proceedingshttps://zbmath.org/1496.900052022-11-17T18:59:28.764376ZThe articles of this volume will be reviewed individually. For the preceding conference see [Zbl 1418.90011].
Indexed articles:
\textit{Abdi, Ahmad; Cornuéjols, Gérard; Huynh, Tony; Lee, Dabeen}, Idealness of \(k\)-wise intersecting families, 1-12 [Zbl 07602115]
\textit{Adjiashvili, David; Hommelsheim, Felix; Mühlenthaler, Moritz}, Flexible graph connectivity, 13-26 [Zbl 07602116]
\textit{Aissi, Hassene; McCormick, S. Thomas; Queyranne, Maurice}, Faster algorithms for next breakpoint and max value for parametric global minimum cuts, 27-39 [Zbl 07602117]
\textit{Aliev, Iskander; Averkov, Gennadiy; De Loera, Jesús A.; Oertel, Timm}, Optimizing sparsity over lattices and semigroups, 40-51 [Zbl 07602118]
\textit{Anegg, Georg; Angelidakis, Haris; Kurpisz, Adam; Zenklusen, Rico}, A technique for obtaining true approximations for \(k\)-center with covering constraints, 52-65 [Zbl 07602119]
\textit{Barman, Siddharth; Fawzi, Omar; Ghoshal, Suprovat; Gürpınar, Emirhan}, Tight approximation bounds for maximum multi-coverage, 66-77 [Zbl 07602120]
\textit{Bonami, Pierre; Salvagnin, Domenico; Tramontani, Andrea}, Implementing automatic benders decomposition in a modern MIP solver, 78-90 [Zbl 07602121]
\textit{Bosman, Thomas; Olver, Neil}, Improved approximation algorithms for inventory problems, 91-103 [Zbl 07602122]
\textit{Conforti, Michele; Fiorini, Samuel; Huynh, Tony; Weltge, Stefan}, Extended formulations for stable set polytopes of graphs without two disjoint odd cycles, 104-116 [Zbl 07602123]
\textit{Dash, Sanjeeb; Günlük, Oktay; Lee, Dabeen}, On a generalization of the Chvátal-Gomory closure, 117-129 [Zbl 07602124]
\textit{Frascaria, Dario; Olver, Neil}, Algorithms for flows over time with scheduling costs, 130-143 [Zbl 07602125]
\textit{Garg, Naveen; Kumar, Nikhil; Sebő, András}, Integer plane multiflow maximisation: flow-cut gap and one-quarter-approximation, 144-157 [Zbl 07602126]
\textit{Gupta, Anupam; Kumar, Amit; Nagarajan, Viswanath; Shen, Xiangkun}, Stochastic makespan minimization in structured set systems (extended abstract), 158-170 [Zbl 07602127]
\textit{Hartmann, Tim A.; Lendl, Stefan; Woeginger, Gerhard J.}, Continuous facility location on graphs, 171-181 [Zbl 07602128]
\textit{Heo, Cheolwon; Guenin, Bertrand}, Recognizing even-cycle and even-cut matroids, 182-195 [Zbl 07602129]
\textit{Hirai, Hiroshi; Iwamasa, Yuni}, A combinatorial algorithm for computing the rank of a generic partitioned matrix with \(2 \times 2\) submatrices, 196-208 [Zbl 07602130]
\textit{Jia, Xinrui; Sheth, Kshiteej; Svensson, Ola}, Fair colorful \(k\)-center clustering, 209-222 [Zbl 07602131]
\textit{Kavitha, Telikepalli; Király, Tamás; Matuschke, Jannik; Schlotter, Ildikó; Schmidt-Kraepelin, Ulrike}, Popular branchings and their dual certificates, 223-237 [Zbl 07602132]
\textit{Király, Csaba; Mihálykó, András}, Sparse graphs and an augmentation problem, 238-251 [Zbl 07602133]
\textit{Klein, Kim-Manuel}, About the complexity of two-stage stochastic IPs, 252-265 [Zbl 07602134]
\textit{Klimm, Max; Pfetsch, Marc E.; Raber, Rico; Skutella, Martin}, Packing under convex quadratic constraints, 266-279 [Zbl 07602135]
\textit{Kobayashi, Yusuke}, Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles, 280-293 [Zbl 07602136]
\textit{Morell, Sarah; Skutella, Martin}, Single source unsplittable flows with arc-wise lower and upper bounds, 294-306 [Zbl 07602137]
\textit{Muñoz, Gonzalo; Serrano, Felipe}, Maximal quadratic-free sets, 307-321 [Zbl 07602138]
\textit{Müller, Benjamin; Muñoz, Gonzalo; Gasse, Maxime; Gleixner, Ambros; Lodi, Andrea; Serrano, Felipe}, On generalized surrogate duality in mixed-integer nonlinear programming, 322-337 [Zbl 07602139]
\textit{Paat, Joseph; Schlöter, Miriam; Weismantel, Robert}, The integrality number of an integer program, 338-350 [Zbl 07602140]
\textit{Rodríguez-Heck, Elisabeth; Stickler, Karl; Walter, Matthias; Weltge, Stefan}, Persistency of linear programming relaxations for the stable set problem, 351-363 [Zbl 07602141]
\textit{Paat, Joseph; Schlöter, Miriam; Speakman, Emily}, Constructing lattice-free gradient polyhedra in dimension two, 364-377 [Zbl 07602142]
\textit{Shi, Xueyu; Prokopyev, Oleg A.; Zeng, Bo}, Sequence independent lifting for the set of submodular maximization problem, 378-390 [Zbl 07602143]
\textit{Traub, Vera; Tröbst, Thorben}, A fast \((2 + 2/7)\)-approximation algorithm for capacitated cycle covering, 391-404 [Zbl 07602144]
\textit{van Hoeve, Willem-Jan}, Graph coloring lower bounds from decision diagrams, 405-418 [Zbl 07602145]
\textit{Wang, Alex L.; Kılınç-Karzan, Fatma}, On convex hulls of epigraphs of QCQPs, 419-432 [Zbl 07602146]
\textit{Wei, Linchuan; Gómez, Andrés; Küçükyavuz, Simge}, On the convexification of constrained quadratic optimization problems with indicator variables, 433-447 [Zbl 07602147]22nd symposium on algorithmic approaches for transportation modelling, optimization, and systems, ATMOS 2022, Potsdam, Germany, September 8--9, 2022https://zbmath.org/1496.900062022-11-17T18:59:28.764376ZThe articles of mathematical interest will be reviewed individually. For the preceding symposium see [Zbl 1473.90002].Advances in optimization and applications. 12th international conference, OPTIMA 2021, Petrovac, Montenegro, September 27 -- October 1, 2021. Revised selected papershttps://zbmath.org/1496.900072022-11-17T18:59:28.764376ZPublisher's description: This book constitutes the refereed proceedings of the 12th International Conference on Optimization and Applications, OPTIMA 2021, held in Petrovac, Montenegro, in September -- October 2021. Due to the COVID-19 pandemic the conference was partially held online.
The 19 revised full papers presented were carefully reviewed and selected from 38 submissions. The papers are organized in topical sections on mathematical programming; global optimization; stochastic optimization; optimal control; mathematical economics; optimization in data analysis; applications.
The articles of this volume will be reviewed individually. For the preceding conference see [Zbl 07347442].
Indexed articles:
\textit{Birjukov, A.; Chernov, A.}, On numerical estimates of errors in solving convex optimization problems, 3-18 [Zbl 07624786]
\textit{Kuruzov, Ilya A.; Stonyakin, Fedor S.}, Sequential subspace optimization for quasar-convex optimization problems with inexact gradient, 19-33 [Zbl 07624787]
\textit{Barkalov, Konstantin; Usova, Marina}, A search algorithm for the global extremum of a discontinuous function, 37-49 [Zbl 07624788]
\textit{Vedel, Yana; Semenov, Vladimir; Denisov, Sergey}, A novel algorithm with self-adaptive technique for solving variational inequalities in Banach spaces, 50-64 [Zbl 07624789]
\textit{Buldaev, Alexander; Kazmin, Ivan}, On one method of optimization of quantum systems based on the search for fixed points, 67-81 [Zbl 07624790]
\textit{Pasechnyuk, Dmitry; Dvurechensky, Pavel; Omelchenko, Sergey; Gasnikov, Alexander}, Stochastic optimization for dynamic pricing, 82-94 [Zbl 07624791]
\textit{Safin, Kamil; Dvurechensky, Pavel; Gasnikov, Alexander}, Adaptive gradient-free method for stochastic optimization, 95-108 [Zbl 07624792]
\textit{Aida-Zade, K. R.; Hashimov, V. A.}, Synthesis of power and movement control of heating sources of the rod, 111-122 [Zbl 07624793]
\textit{Konstantinov, Sergey; Diveev, Askhat}, Evolutionary algorithms for optimal control problem of mobile robots group interaction, 123-136 [Zbl 07624794]
\textit{Aizenberg, Natalia}, Model LSFE with conjectural variations for electricity forward market, 139-153 [Zbl 07624795]
\textit{Kolomeytsev, Yury}, Meta algorithms for portfolio optimization using reinforcement learning, 154-168 [Zbl 07624796]
\textit{Mikhailova, Liudmila}, Simultaneous detection and discrimination of the known number of non-linearly extended alphabet elements in a quasiperiodic sequence, 171-183 [Zbl 07624797]
\textit{Pasechnyuk, Dmitry; Raigorodskii, Andrei M.}, Network utility maximization by updating individual transmission rates, 184-198 [Zbl 07624798]
\textit{Erzin, Adil; Melidi, Georgii; Nazarenko, Stepan; Plotnikov, Roman}, A posteriori analysis of the algorithms for two-bar charts packing problem, 201-216 [Zbl 07624800]
\textit{Koledina, Kamila; Koledin, Sergey; Gubaydullin, Irek}, Pareto frontier in multicriteria optimization of chemical processes based on a kinetic model, 217-229 [Zbl 07624801]
\textit{Malyshev, Dmitry; Rybak, Larisa; Mohan, Santhakumar; Diveev, Askhat; Cherkasov, Vladislav; Pisarenko, Anton}, The method of optimal geometric parameters synthesis of two mechanisms in the rehabilitation system on account of relative position, 230-245 [Zbl 07624802]
\textit{Menshikova, Olga; Sedush, Anna; Polyudova, Daria; Yaminov, Rinat; Menshikov, Ivan}, Laboratory analysis of the social and psychophysiological aspects of the behaviour of participants in the lemons market game, 246-257 [Zbl 07624803]
\textit{Tormagov, Timofey; Rapoport, Lev}, Coverage path planning for 3D terrain with constraints on trajectory curvature based on second-order cone programming, 258-272 [Zbl 07624804]
\textit{Zasukhin, Sergey; Zasukhina, Elena}, Determination of hydrological model parameters by Newton method, 273-285 [Zbl 07624805]An inventory model to study the effect of the probabilistic rate of carbon emission on the profit earned by a supplierhttps://zbmath.org/1496.900082022-11-17T18:59:28.764376Z"Bhattacharjee, Nabajyoti"https://zbmath.org/authors/?q=ai:bhattacharjee.nabajyoti"Sen, Nabendu"https://zbmath.org/authors/?q=ai:sen.nabenduSummary: The inventory of suppliers providing raw materials to industries producing green products faces two challenging problems. The first one is that raw materials are usually deteriorating items and the second one is that they emit carbon-based gases during deterioration. Moreover, each item has its unique carbon emission rate and composition, called the pattern of carbon emission, which is a function of the rate of carbon emission. In this present research, we attempt to develop a stochastic inventory model with price, stock, and pattern of carbon emission-dependent demand to maximise the profit of a supplier selling a single product. The rate of deterioration is a function of the rate of carbon emission and effective investment in preservation. The cost of carbon emission is a function of green investment and the pattern of carbon emission. Holding costs and purchase costs are constant. We consider three patterns of carbon emission, and each pattern is defined by a negative exponential function. The rate of carbon emission is assumed to be probabilistic and follows one of the three probabilistic distributions: uniform, triangular, and beta. Numerical validation is provided together with sensitivity analysis of the parameters for managerial insights. Analysis of the effect of carbon emission on the profit earned is made and results are interpreted. Particle swarm optimisation (PSO) and genetic algorithm (GA) are applied to solve the model, while statistical analysis and sensitivity analysis of the parameters of the algorithm are provided along with the graphical representation of convergence.Analytical and simulation determination of order picking time in a low storage warehouse for shared storage systemshttps://zbmath.org/1496.900092022-11-17T18:59:28.764376Z"Dmytrów, Krzysztof"https://zbmath.org/authors/?q=ai:dmytrow.krzysztofSummary: The aim of the research is comparison between average order picking times obtained using the analytical model and simulation methods for shared storage systems. We also compare the results obtained with the results obtained for dedicated storage. We assume the random and ABC-class storage (with within and across aisle storage policies). We select the locations by means of the TOPSIS method for two take-out strategies: quantity adjustment (QA) and priority of partial units (PPU). We determine the route by using \(s\)-\textit{shape} and \textit{return} heuristics. In most cases, the simulated average order picking times are shorter than the analytical ones. It results from not considering the criteria' weights in calculation of the analytical order picking time. Also, the results for shared storage with QA strategy are in most cases better than for dedicated storage. This might imply an advantage of shared over dedicated storage, but needs further confirmation.A two-echelon supply chain model with deterioration and stock-dependent demand via forward and backward stocking policieshttps://zbmath.org/1496.900102022-11-17T18:59:28.764376Z"Kumar, M. Ganesh"https://zbmath.org/authors/?q=ai:kumar.mari-ganesh"Uthayakumar, R."https://zbmath.org/authors/?q=ai:uthayakumar.ramasamySummary: We have developed an integrated inventory model for deteriorating items in a two-echelon supply chain. In this model, we have assumed that the vendor produces a single product at a constant rate and transferred it in equal batches to buyer's warehouse. Some of the products are presented to the customer in the buyer display area and the demand is assumed to be positively dependent on the products displayed. Due to deterioration, the vendor incurs a warranty cost for each deteriorated item. We compared the total profit for both forward and backward stock policy, and we showed that the holding cost decreases as the stock moves downstream, the vendor has to adhere to the forward stock policy. The aim is to determine the number of deliveries needed to transfer, lot size such that the average profit of the system attains its maximum. Numerical examples are provided for illustrating the model.Determination of EOQ in terms of optimum degrees of horizontal and vertical cooperation at a node of supply chainhttps://zbmath.org/1496.900112022-11-17T18:59:28.764376Z"Mishra, Prem Prakash"https://zbmath.org/authors/?q=ai:mishra.prem-prakash"Zimik, Chipem"https://zbmath.org/authors/?q=ai:zimik.chipem"Borkotokey, Surajit"https://zbmath.org/authors/?q=ai:borkotokey.surajitSummary: In a complex supply chain network, the production nodes, seller nodes, and buyers are connected randomly. We assume a process of joining two random nodes leading to the bivariate Poisson probability mass function. There exist two types of links -- one is horizontal (H) and the other is vertical (V), which support the continuous flow of commodities through the supply chain. This induces competition among workers at a node to manage these two types of links within fixed constraints and creates bargaining to decide the optimal degree of both types of links at a node. We use the Nash security point to obtain the bargaining solution describing the optimal links. We reduce the carrying cost and ordering cost of inventory, which are contrary in their nature by introducing horizontal and vertical links, respectively. We modify the total cost function and establish a new economic order quantity (EOQ), optimal shortage quantity, and total optimal cost in terms of the optimal degree of H and V cooperation.A heuristic approach to optimizing the loading of homogeneous marine cargohttps://zbmath.org/1496.900122022-11-17T18:59:28.764376Z"Bernardelli, Michał"https://zbmath.org/authors/?q=ai:bernardelli.michalSummary: In this article, the optimal loading of homogeneous marine cargo is considered. A mathematical formulation in terms of a mixed-integer linear program can be given. Still, the level of complexity turns out to be too high to perform full-scale computations. On the one hand, the reasons for this are the multitude of variables and constraints. On the other hand, feasible solutions to such problems may often be economically unacceptable or simply empty. Therefore, a heuristic is presented, according to which the relaxation of the limiting conditions influencing the solution's feasibility and its economic profitability was parametrized. Under this heuristic, shifting the deadlines of selected orders is allowed. Also, the assignment of orders to vessels is separated from the allocation of vessels to piers in loading and unloading ports. The solution presented can be easily generalized by adding additional restrictions or features like indirect vessels, founding cost, or differentiation between materials.Optimal emergency evacuation with uncertaintyhttps://zbmath.org/1496.900132022-11-17T18:59:28.764376Z"Fargetta, Georgia"https://zbmath.org/authors/?q=ai:fargetta.georgia"Scrimali, Laura"https://zbmath.org/authors/?q=ai:scrimali.laura-rosa-mariaSummary: Emergency management after crises or natural disasters is a very important issue shared by many countries. In this chapter, we focus on evacuation planning which is a complex and challenging process able to predict or evaluate different disaster scenarios. In particular, we present an evacuation model where a population has to be evacuated from crisis areas to shelters and propose an optimization formulation for minimizing a combination of the transportation cost and the transportation time. In addition, we admit uncertainty in the size of the population to be evacuated and provide a two-stage stochastic programming model. In order to illustrate the modeling framework, we present a numerical example.
For the entire collection see [Zbl 1483.00042].Four-dimensional uncertain multi-objective multi-item transportation problemhttps://zbmath.org/1496.900142022-11-17T18:59:28.764376Z"Kakran, Vandana"https://zbmath.org/authors/?q=ai:kakran.vandana"Dhodiya, Jayesh"https://zbmath.org/authors/?q=ai:dhodiya.jayesh-mSummary: This paper considers a four-dimensional multi-objective multi-item transportation problem (4DMOMITP), where all the parameters are regarded as uncertain variables. In this paper, three mathematical models, namely expected value model (EVM), optimistic value model (OVM) and dependent optimistic-constrained model (DOCM), are discussed for the uncertain model of 4DMOMITP. These models are converted into their corresponding deterministic forms using different ranking criteria from uncertainty theory. These deterministic models are then solved by using the Lingo 18.0 software, utilizing three different classical approaches for obtaining a solution. A numerical example is given to illustrate the application of the model and the solution algorithm. A sensitivity analysis for the OVM and DOCM models has also been performed with respect to the confidence levels.Time strategy for setting direct and wholesale prices with intermediaries in dual-channel supply chain of seasonal agricultural productshttps://zbmath.org/1496.900152022-11-17T18:59:28.764376Z"Limjanon, Nattanan"https://zbmath.org/authors/?q=ai:limjanon.nattanan"Witayakiattilerd, Wichai"https://zbmath.org/authors/?q=ai:witayakiattilerd.wichaiSummary: This research studies the pricing and timing strategies of seasonal agricultural products in a dual-channel supply chain, which consists of two trading channels: direct channel and retail channel, by applying the conceptual principles of game theory and optimal value problems. The main purpose of this research is to determine when farmers should bring their products to the market in a direct channel and what the most suitable price for that product should be. To get the most benefit, a farmer has to set a direct price together with selling agricultural products to the intermediary. In terms of price, the direct price in front of the plantation should be set higher than the expected purchase price offered by the intermediary and lower than the retail price. That is because if the farmers set the direct price lower than the expected purchase price, it will make them lose their income from the direct channel. On the other hand, if the direct price is set higher than the retail price through the retail channel, it will result in a lack of incentives for consumers to purchase through direct channels. The results are presented as an equation. The values to be substituted can be based on historical statistics or a similar product. At the end of this paper, results show what would occur on the farmers' income when carrying out this pricing and timing strategy.Complexity analysis of production, fertilizer-saving level, and emission reduction efforts decisions in a two-parallel agricultural product supply chainhttps://zbmath.org/1496.900162022-11-17T18:59:28.764376Z"Xi, Xuan"https://zbmath.org/authors/?q=ai:xi.xuan"Zhang, Yulin"https://zbmath.org/authors/?q=ai:zhang.yulin|zhang.yulin.1Summary: This paper analyses the complexity of production, fertilizer-saving level, and emission reduction efforts decisions in a Cournot agricultural products supply chain system. A two-parallel agricultural products supply chain consisting of traditional agricultural producers and green agricultural producers was established. Based on bounded rationality, the decision competition model between the two supply chains was investigated in two scenarios: horizontal Nash (HN) game and long-term Stackelberg (LS) game with traditional agricultural producers as the leader. The Nash equilibrium points of the two models were obtained, and the impact of different decision-making adjustment speeds and critical parameters on the stability of the system and the expected profit of agricultural producers was discussed. The study found that production adjustments had a more significant impact on the stability of the system, decision variables, and expected profits than the adjustment of fertilizer-saving level and emission reduction efforts in the two scenarios. In the HN game, the impact of nitrogen tax or low nitrogen preference on traditional agricultural producers was opposite to that of green agrarian producers. Although the increase of these parameters was beneficial to green agricultural producers, the system's stability would decrease. In addition, the stability of the LS game model can be divided into two decision-making systems to judge, and the adjustment speed of traditional agricultural producers' decisions had a more significant impact on the whole system. Finally, the feedback control method was used to control the chaos of the system of the HN game.Robustness of scale-free networks with dynamical behavior against multi-node perturbationhttps://zbmath.org/1496.900172022-11-17T18:59:28.764376Z"Lv, Changchun"https://zbmath.org/authors/?q=ai:lv.changchun"Yuan, Ziwei"https://zbmath.org/authors/?q=ai:yuan.ziwei"Si, Shubin"https://zbmath.org/authors/?q=ai:si.shubin"Duan, Dongli"https://zbmath.org/authors/?q=ai:duan.dongliSummary: An issue which is increasingly attracting attention from scientists to engineers, is the robustness of networks which is the ability against perturbations. It is found that both the network topology and network dynamics affect the robustness of networks. In this article, we present the cascading failure model triggered by perturbing a fraction \(1- p\) of nodes on SF networks with three dynamics: the biochemical \((\mathcal{B})\), epidemic \((\mathcal{E})\) and regulatory \((\mathcal{R})\) dynamics. A mathematical method is developed to calculate the cascading failure size and the giant component to evaluate the robustness when a fraction \(1-p\) of nodes is perturbed on SF dynamical networks. We perform extensive numerical simulations to test and verify this formula and find that the theoretical results are in good agreement with simulations. The results show that the network is more robust as the tolerance coefficient \(\delta\) increases, and the size of network has little influence on the robustness, especially for \(\mathcal{B}\) and \(\mathcal{R}\). Remarkably, the heterogeneity of networks is positive on the robustness. Moreover, the different characteristics that as the parameter \(B\) increases or the parameter \(R\) decreases the network with \(\mathcal{B}\) is more robust, and as the parameter \(R\) increases or the parameter \(B\) decreases the network with \(\mathcal{E}\) and \(\mathcal{R}\) is more robust are found. These findings may be useful for engineers to improve the robustness of the network or design robust networks with dynamics.An algorithm for ranking the nodes of multiplex networks with data based on the PageRank concepthttps://zbmath.org/1496.900182022-11-17T18:59:28.764376Z"Tortosa, Leandro"https://zbmath.org/authors/?q=ai:tortosa.leandro"Vicent, Jose F."https://zbmath.org/authors/?q=ai:vicent.jose-francisco"Yeghikyan, Gevorg"https://zbmath.org/authors/?q=ai:yeghikyan.gevorgSummary: A new algorithm for attributed multiplex networks is proposed and analysed with the main objective to compute the centrality of the nodes based on the original PageRank model used to establish a ranking in the Web pages network. Taking as a basis the Adapted PageRank Algorithm for monoplex networks with data and the two-layer PageRank approach, an algorithm for biplex networks is designed with two main characteristics. First, it solves the drawback of the existence of isolated nodes in any of the layers. Second, the algorithm allows us to choose the value of the parameter \(\alpha\) controlling the importance assigned to the network topology and the data associated to the nodes in the Adapted PageRank Algorithm, respectively. The proposed algorithm inherits this ability to determine the importance of node attribute data in the calculation of the centrality; yet, going further, it allows to choose different \(\alpha\) values for each of the two layers. The biplex algorithm is then generalised to the case of multiple layers, that is, for multiplex networks. Its possibilities and characteristics are demonstrated using a dataset of aggregate origin-destination flows of private cars in Rome. This dataset is augmented with attribute data describing city locations. In particular, a biplex network is constructed by taking the data about car mobility for layer 1. Layer 2 is generated from data describing the local bus transport system. The algorithm establishes the most central locations in the city when these layers are intertwined with the location attributes in the biplex network. Four cases are evaluated and compared for different values of the parameter that modulates the importance of data in the network.Generalized net model of overall telecommunication system with queuinghttps://zbmath.org/1496.900192022-11-17T18:59:28.764376Z"Andonov, Velin"https://zbmath.org/authors/?q=ai:andonov.velin"Poryazov, Stoyan"https://zbmath.org/authors/?q=ai:poryazov.stoyan"Saranova, Emiliya"https://zbmath.org/authors/?q=ai:saranova.emiliyaSummary: Generalized Net (GN) model of overall telecommunication system with queuing is proposed. It is based on the classical conceptual model of overall telecommunication system which considers user's behaviour, finite number of users and terminals, losses due to abandoned and interrupted dialing, blocked and interrupted switching, unavailable intent terminal, blocked and abandoned ringing and abandoned communication. A queuing system with finite capacities of the server and buffer and FIFO discipline of service of the requests is included in the Switching stage. The proposed model can be used in the analytical modeling of overall telecommunication systems.
For the entire collection see [Zbl 1478.03003].Congestion control and optimal maintenance of communication networks with stochastic cost functions: a variational formulationhttps://zbmath.org/1496.900202022-11-17T18:59:28.764376Z"Passacantando, Mauro"https://zbmath.org/authors/?q=ai:passacantando.mauro"Raciti, Fabio"https://zbmath.org/authors/?q=ai:raciti.fabioSummary: We consider a game theory model of congestion control in communication networks, where each player is a user who wishes to maximize his/her flow over a path in the network. We allow for stochastic fluctuations of the cost function of each player, which consists of two parts: a pricing and a utility term. The solution concept we look for is the mean value of the (unique) variational Nash equilibrium of the game. Furthermore, we assume that it is possible to invest a certain amount of money to improve the network by enhancing the capacity of its links and, because of limited financial resources, an optimal choice of the links to improve has to be made. We model the investment problem as a nonlinear knapsack problem with generalized Nash equilibrium constraints in probabilistic Lebesgue spaces and solve it numerically for some examples.
For the entire collection see [Zbl 1483.00042].On relation between two-criteria user-optimized route choice problem and vector variational inequality problem in fuzzy environmenthttps://zbmath.org/1496.900212022-11-17T18:59:28.764376Z"Peyvand, Morad-Ali"https://zbmath.org/authors/?q=ai:peyvand.morad-aliSummary: A two-criteria user-optimized route choice problem is proposed, in which each user of a network system seeks to determine his/her optimal route of travel between an origin-destination (O-D) pair considering two-criteria simultaneously. In this problem, the two-criteria of travel, time and cost, between an O-D pair are fuzzy, in the sense that, time and cost of which links are chosen for traveling are uncertain. Applying the concept of \(\alpha\)-cut level, a fuzzy vector disutility function on a path is computed. Furthermore, the fuzzy vector equilibrium principle as a generalization and extension of the Wardrop equilibrium principle is defined. Finally, by reducing this fuzzy principle to a crisp one, the relationship between the vector equilibrium flow and the solution of a vector variational inequality problem is discussed.Near equilibrium fluctuations for supermarket models with growing choiceshttps://zbmath.org/1496.900222022-11-17T18:59:28.764376Z"Bhamidi, Shankar"https://zbmath.org/authors/?q=ai:bhamidi.shankar"Budhiraja, Amarjit"https://zbmath.org/authors/?q=ai:budhiraja.amarjit-s"Dewaskar, Miheer"https://zbmath.org/authors/?q=ai:dewaskar.miheerSummary: We consider the supermarket model in the usual Markovian setting where jobs arrive at rate \(n\lambda_n\) for some \(\lambda_n > 0\), with \(n\) parallel servers each processing jobs in its queue at rate 1. An arriving job joins the shortest among \(d_n \leq n\) randomly selected service queues. We show that when \(d_n\to \infty\) and \(\lambda_n\to \lambda \in (0,\infty)\), under natural conditions on the initial queues, the state occupancy process converges in probability, in a suitable path space, to the unique solution of an infinite system of constrained ordinary differential equations parametrized by \(\lambda\). Our main interest is in the study of fluctuations of the state process about its near equilibrium state in the critical regime, namely when \(\lambda_n\to 1\). Previous papers, for example, [\textit{D. Mukherjee} et al., Stoch. Syst. 8, No. 4, 265--292 (2018; Zbl 1446.60073)] have considered the regime \(\frac{d_n}{\sqrt{n}\log n}\to \infty\) while the objective of the current work is to develop diffusion approximations for the state occupancy process that allow for all possible rates of growth of \(d_n\). In particular, we consider the three canonical regimes (a) \(d_n /\sqrt{n}\to 0\); (b) \(d_n /\sqrt{n}\to c\in (0,\infty)\) and, (c) \(d_n /\sqrt{n}\to \infty\). In all three regimes, we show, by establishing suitable functional limit theorems, that (under conditions on \(\lambda_n)\) fluctuations of the state process about its near equilibrium are of order \(n^{-1/2}\) and are governed asymptotically by a one-dimensional Brownian motion. The forms of the limit processes in the three regimes are quite different; in the first case, we get a linear diffusion; in the second case, we get a diffusion with an exponential drift; and in the third case we obtain a reflected diffusion in a half space. In the special case \(d_n /(\sqrt{n}\log n)\to \infty\), our work gives alternative proofs for the universality results established in [loc. cit.].Analysis of a single server queue in a multi-phase random environment with working vacations and customers' impatiencehttps://zbmath.org/1496.900232022-11-17T18:59:28.764376Z"Bouchentouf, Amina Angelika"https://zbmath.org/authors/?q=ai:bouchentouf.amina-angelika"Guendouzi, Abdelhak"https://zbmath.org/authors/?q=ai:guendouzi.abdelhak"Meriem, Houalef"https://zbmath.org/authors/?q=ai:meriem.houalef"Shakir, Majid"https://zbmath.org/authors/?q=ai:shakir.majidSummary: In this paper, we analyze an \(M/M/1\) queueing system under both single and multiple working vacation policies, multiphase random environment, waiting server, balking and reneging. When the system is in operative phase \(j = 1,2,\ldots,K\), customers are served one by one. Whenever the system becomes empty, the server waits a random amount of time before taking a vacation, causing the system to move to working vacation phase 0 at which new arrivals are served at a lower rate. Using the probability generating function method, we obtain the distribution for the steady-state probabilities of the system. Then, we derive important performance measures of the queueing system. Finally, some numerical examples are illustrated to show the impact of system parameters on performance measures of the queueing system.A discussion on the optimality of bulk entry queue with differentiated hiatuseshttps://zbmath.org/1496.900242022-11-17T18:59:28.764376Z"Vadivukarasi, Manickam"https://zbmath.org/authors/?q=ai:vadivukarasi.manickam"Kalidass, Kaliappan"https://zbmath.org/authors/?q=ai:kalidass.kaliappanSummary: We consider Markovian differentiated hiatuses queues with bulk entries. With the help of the matrix geometric method, we discuss the stability condition for the existence of the steady-state solution of our model and we obtain the stationary system size by using a probability generating function. The stochastic decomposition form of stationary system size and the waiting time distribution of an arbitrary beneficiary are also analysed. Furthermore, we perform the expense analysis using the particle swarm optimization technique and we obtain the optimality of service rate and hiatus rate. Finally, we study the effects of changes in the parameters on some important performance measures of the system through numerical observations.Logarithmic similarity measures on Pythagorean fuzzy sets in admission processhttps://zbmath.org/1496.900252022-11-17T18:59:28.764376Z"Arora, Hari Darshan"https://zbmath.org/authors/?q=ai:arora.hari-darshan"Naithani, Anjali"https://zbmath.org/authors/?q=ai:naithani.anjaliSummary: The intuitionistic fuzzy sets (IFSs) have a more significant contribution to describing and dealing with uncertainty. The intuitionistic fuzzy measure is a significant consideration in the field of IFSs theory. However, Pythagorean fuzzy sets (PFSs) are an extension of the IFSs. PFSs are more capable of modelling uncertainties than IFSs in real-world decision-making scenarios. The majority of PFSs research has concentrated on establishing decision-making frameworks. A similarity measure is a key concept which measures the closeness of PFSs. IFSs-based similarity measures have been proposed in the literature. This type of similarity measure, however, has a drawback since it cannot satisfy the axiomatic definition of similarity by offering counter-intuitive examples. For this study, a similarity based on logarithmic function for Pythagorean fuzzy sets (PFSs) is proposed as a solution to the problem. A decision-making approach is presented to ascertain the suitability of careers for aspirants. Additionally, numerical illustration is applied to determine the strength and validity of the proposed similarity measures. The application of the proposed similarity measures is also presented in this article. A comparison of the suggested measures with the existing ones is also demonstrated to ensure the reliability of the measures. The results show that the proposed similarity measures are efficient and reasonable from both numerical and realistic assessments.Modeling innovation efficiency, its micro-level drivers, and its impact on stock returnshttps://zbmath.org/1496.900262022-11-17T18:59:28.764376Z"Atta Mills, Ebenezer Fiifi Emire"https://zbmath.org/authors/?q=ai:mills.ebenezer-fiifi-emire-atta"Zeng, Kailin"https://zbmath.org/authors/?q=ai:zeng.kailin"Fangbiao, Liu"https://zbmath.org/authors/?q=ai:fangbiao.liu"Fangyan, Li"https://zbmath.org/authors/?q=ai:fangyan.liSummary: Motivated by the COVID-19 pandemic and ensuing challenges to human and economic welfare, this research seeks to evaluate innovation efficiency, its micro-level drivers, and its impact on stock returns. This study considers innovation-related activities during two growth phases experienced by 138 listed pharmaceutical manufacturing companies in China: research and development (R\&D) and marketing. A dynamic two-phase network data envelopment analysis (DEA) model measured R\&D efficiency, marketing efficiency, and dynamic integrated innovation efficiency. A projection difference analysis was presented to offer a feasible solution to address inefficient companies. Then, panel regression methods were adopted to examine micro-level drivers of innovation efficiency. Additionally, a portfolio formation test was used to investigate innovation efficiency as a characteristic impacting stock returns. The results indicate that the listed companies are generally innovation inefficient. Only two are DEA innovation efficient. Low marketing and R\&D efficiencies are impeding innovation efficiency amelioration, with the most losses attributed to the marketing phase. Most companies lack good conditions for R\&D and the commercialization of scientific and technological breakthroughs. Institutional investors and financial analysts' coverage have a positive and significant impact on innovation efficiency. Foreign institutional ownership and stock market overvaluation impact listed companies with high innovation efficiency positively. There is a negative and significant effect of size on innovation efficiency. However, growth in pharmaceutical manufacturing company size positively influences innovation efficiency at higher levels. The portfolio formation test results reveal that investors consider companies with high innovation efficiency as high-profile targets that provide high stock returns. The findings of this study offer stakeholders avenues to shape the initiation, process, and outcome of innovation.A \(\frac{3}{2}\)-approximation algorithm for the student-project allocation problemhttps://zbmath.org/1496.900272022-11-17T18:59:28.764376Z"Cooper, Frances"https://zbmath.org/authors/?q=ai:cooper.frances"Manlove, David"https://zbmath.org/authors/?q=ai:manlove.david-fSummary: The Student-Project Allocation problem with lecturer preferences over Students (SPA-S) comprises three sets of agents, namely students, projects and lecturers, where students have preferences over projects and lecturers have preferences over students. In this scenario we seek a stable matching, that is, an assignment of students to projects such that there is no student and lecturer who have an incentive to deviate from their assignee/s. We study SPA-ST, the extension of SPA-S in which the preference lists of students and lecturers need not be strictly ordered, and may contain ties. In this scenario, stable matchings may be of different sizes, and it is known that MAX SPA-ST, the problem of finding a maximum stable matching in SPA-ST, is NP-hard. We present a linear-time \(\frac{3}{2}\)-approximation algorithm for MAX SPA-ST and an Integer Programming (IP) model to solve MAX SPA-ST optimally. We compare the approximation algorithm with the IP model experimentally using randomly-generated data. We find that the performance of the approximation algorithm easily surpassed the \(\frac{3}{2}\) bound, constructing a stable matching within 92\% of optimal in all cases, with the percentage being far higher for many instances.
For the entire collection see [Zbl 1390.68017].Managing large-scale projects in a mixed economyhttps://zbmath.org/1496.900282022-11-17T18:59:28.764376Z"Ereshko, F. I."https://zbmath.org/authors/?q=ai:ereshko.f-i.1"Mushkov, A. Yu."https://zbmath.org/authors/?q=ai:mushkov.a-yu"Turko, N. I."https://zbmath.org/authors/?q=ai:turko.n-i"Tsvirkun, A. D."https://zbmath.org/authors/?q=ai:tsvirkun.a-dSummary: The work continues the research by the present authors on the management of industrial and infrastructure systems in accordance with the global trend in the digitalization of the economy. A description of the initial fundamental foundations of the ongoing developments and a review of domestic experience in the use of mathematical models, information and communication technologies, and large amounts of information in the management of systems are given. The issues of centralization and decentralization of control in complex systems are considered. Theoretical constructions of decision making are given to analyze the prospects for the development of partnership between the state and business within the framework of given legal norms. A block of conceptual models corresponding to the level of planning of large-scale organizational systems is given, issues of data preparation and development of algorithmic support, and a combination of macro- and micro-descriptions of economic systems are considered.A literature review of interval-valued intuitionistic fuzzy multi-criteria decision-making methodologieshttps://zbmath.org/1496.900292022-11-17T18:59:28.764376Z"Kokoç, Melda"https://zbmath.org/authors/?q=ai:kokoc.melda"Ersöz, Süleyman"https://zbmath.org/authors/?q=ai:ersoz.suleymanSummary: Multi-criteria decision-making (MCDM) is one of the most popular problems handled by researchers in the literature. Since the interval-valued intuitionistic fuzzy set (IVIFS) theory generates as realistic as possible evaluation of linguistic expressions, researchers have been expanding traditional MCDM methods to the IVIF environment, especially in the last decade. This study provides a literature review of the relevant articles from several academic databases on applications of IVIF-MCDM methods. The review of 131 publications addresses specific research questions. To understand the research publication trend, this review offers a visual analysis that examines the studies from different perspectives, such as application areas, IVIF-MCDM methods, citations, most relevant journals, and validation methods. One of the most remarkable results of the literature review is that most publications in this field are published in SCIE indexed journals. Another noteworthy issue is that China is the country that produces the most articles in this field. In addition, English journals are mostly selected for the publication of articles. While it is seen that the investment selection problem is chosen mostly as the application area, the TOPSIS method is preferred mostly in the applications. This study stands out as the most comprehensive one that compiles publications containing extended traditional MCDM methods for IVIF sets. This review will be an important reference for future researchers and decision-makers involved in advancing MCDM methods considering vagueness and ambiguity.Simultaneous interpretive structural modelling and weighting (SISMW)https://zbmath.org/1496.900302022-11-17T18:59:28.764376Z"Nasrollahi, Mahdi"https://zbmath.org/authors/?q=ai:nasrollahi.mahdi"Ramezani, Javaneh"https://zbmath.org/authors/?q=ai:ramezani.javaneh"Sadraei, Mahmoud"https://zbmath.org/authors/?q=ai:sadraei.mahmoud"Fathi, Mohammad Reza"https://zbmath.org/authors/?q=ai:fathi.mohammadrezaSummary: Multi-criteria decision-making (MCDM) methods have been implemented in many fields. In the meantime, several methods have been proposed to obtain the weight of the criteria that each method determines the importance of each criterion in a different way. In this paper, a new approach, called simultaneous interpretive structural modelling and weighting (SISMW), is proposed to solve a multi-criterion decision-making (MCDM) problem. Using SISMW, the weight of the criteria and the relationship between them will be determined simultaneously. In this approach, like the ISM method, pair comparison between criteria is made by the decision-maker to determine the relationships among the different criteria. With the help of these data, the weight of the criteria, as well as the causal (cause and effect) relationships between them, will be determined in 12 steps. The main advantage of this method is that only one stage of data collection is required to obtain weights and modelling, and so the research process will be faster. This will increase the reliability of the collected data because, in a one-step survey, the impact of time is minimised. This process can be useful for conceptualising and developing theories to help decision-makers understand the problem better.Optimization of location of interconnected facilities on parallel lines with forbidden zoneshttps://zbmath.org/1496.900312022-11-17T18:59:28.764376Z"Zabudskiĭ, Gennadiĭ Grigor'evich"https://zbmath.org/authors/?q=ai:zabudskii.gennadii-grigorevich"Veremchuk, Natal'ya Sergeevna"https://zbmath.org/authors/?q=ai:veremchuk.natalya-sergeevnaSummary: An overview of statements, models and methods for solving location problem of interconnected rectangular facilities on parallel lines with forbidden zones is given. The centers of the facilities are connected by communications with each other and with forbidden zones. It is necessary to place facilities outside the zones in such a way that the total cost of communications facilities to each other and to the zones was minimal. The main focus is on the problem on the line. For several lines communication are through a viaduct. Models of graph-theoretic formulation and partially integer programming with Boolean variables are constructed. Properties are found that allow us to consider the problem as discrete and decompose it into a number of problems of smaller dimension. Algorithms for finding exact and approximate solutions are developed, and polynomial solvable cases are identified. The results of numerical experiments are presented.QPALM: a proximal augmented Lagrangian method for nonconvex quadratic programshttps://zbmath.org/1496.900322022-11-17T18:59:28.764376Z"Hermans, Ben"https://zbmath.org/authors/?q=ai:hermans.ben"Themelis, Andreas"https://zbmath.org/authors/?q=ai:themelis.andreas"Patrinos, Panagiotis"https://zbmath.org/authors/?q=ai:patrinos.panagiotisSummary: We propose QPALM, a nonconvex quadratic programming (QP) solver based on the proximal augmented Lagrangian method. This method solves a sequence of inner subproblems which can be enforced to be strongly convex and which therefore admit a unique solution. The resulting steps are shown to be equivalent to inexact proximal point iterations on the extended-real-valued cost function, which allows for a fairly simple analysis where convergence to a stationary point at an \(R\)-linear rate is shown. The QPALM algorithm solves the subproblems iteratively using semismooth Newton directions and an exact linesearch. The former can be computed efficiently in most iterations by making use of suitable factorization update routines, while the latter requires the zero of a monotone, one-dimensional, piecewise affine function. QPALM is implemented in open-source C code, with tailored linear algebra routines for the factorization in a self-written package LADEL. The resulting implementation is shown to be extremely robust in numerical simulations, solving all of the Maros-Meszaros problems and finding a stationary point for most of the nonconvex QPs in the Cutest test set. Furthermore, it is shown to be competitive against state-of-the-art convex QP solvers in typical QPs arising from application domains such as portfolio optimization and model predictive control. As such, QPALM strikes a unique balance between solving both easy and hard problems efficiently.Projected orthogonal vectors in two-dimensional search interior point algorithms for linear programminghttps://zbmath.org/1496.900332022-11-17T18:59:28.764376Z"Vitor, Fabio"https://zbmath.org/authors/?q=ai:vitor.fabio"Easton, Todd"https://zbmath.org/authors/?q=ai:easton.toddSummary: The vast majority of linear programming interior point algorithms successively move from an interior solution to an improved interior solution by following a single search direction, which corresponds to solving a one-dimensional subspace linear program at each iteration. On the other hand, two-dimensional search interior point algorithms select two search directions, and determine a new and improved interior solution by solving a two-dimensional subspace linear program at each step. This paper presents primal and dual two-dimensional search interior point algorithms derived from affine and logarithmic barrier search directions. Both search directions are determined by randomly partitioning the objective function into two orthogonal vectors. Computational experiments performed on benchmark instances demonstrate that these new methods improve the average CPU time by approximately 12\% and the average number of iterations by 14\%.A three-term conjugate gradient method with accelerated subspace quadratic optimizationhttps://zbmath.org/1496.900342022-11-17T18:59:28.764376Z"Jian, Jinbao"https://zbmath.org/authors/?q=ai:jian.jinbao"Chen, Wenrui"https://zbmath.org/authors/?q=ai:chen.wenrui"Jiang, Xianzhen"https://zbmath.org/authors/?q=ai:jiang.xianzhen"Liu, Pengjie"https://zbmath.org/authors/?q=ai:liu.pengjie(no abstract)Limited-memory common-directions method for large-scale optimization: convergence, parallelization, and distributed optimizationhttps://zbmath.org/1496.900352022-11-17T18:59:28.764376Z"Lee, Ching-pei"https://zbmath.org/authors/?q=ai:lee.ching-pei"Wang, Po-Wei"https://zbmath.org/authors/?q=ai:wang.po-wei"Lin, Chih-Jen"https://zbmath.org/authors/?q=ai:lin.chih-jenSummary: In this paper, we present a limited-memory common-directions method for smooth optimization that interpolates between first- and second-order methods. At each iteration, a subspace of a limited dimension size is constructed using first-order information from previous iterations, and an efficient Newton method is deployed to find an approximate minimizer within this subspace. With properly selected subspace of dimension as small as two, the proposed algorithm achieves the optimal convergence rates for first-order methods while remaining a descent method, and it also possesses fast convergence speed on nonconvex problems. Since the major operations of our method are dense matrix-matrix operations, the proposed method can be efficiently parallelized in multicore environments even for sparse problems. By wisely utilizing historical information, our method is also communication-efficient in distributed optimization that uses multiple machines as the Newton steps can be calculated with little communication. Numerical study shows that our method has superior empirical performance on real-world large-scale machine learning problems.Evaluating and tuning \(n\)-fold integer programminghttps://zbmath.org/1496.900362022-11-17T18:59:28.764376Z"Altmanová, Katerina"https://zbmath.org/authors/?q=ai:altmanova.katerina"Knop, Dusan"https://zbmath.org/authors/?q=ai:knop.dusan"Koutecký, Martin"https://zbmath.org/authors/?q=ai:koutecky.martinSummary: In recent years, algorithmic breakthroughs in stringology, computational social choice, scheduling, etc., were achieved by applying the theory of so-called \(n\)-fold integer programming. An \(n\)-fold integer program (IP) has a highly uniform block structured constraint matrix. \textit{R. Hemmecke} et al. [Math. Program. 137, No. 1--2 (A), 325--341 (2013; Zbl 1262.90104)] showed an algorithm with runtime \(a^{\mathcal{O}(rst + r^2s)}n^3\), where \(a\) is the largest coefficient, \(r\), \(s\), and \(t\) are dimensions of blocks of the constraint matrix and \(n\) is the total dimension of the IP; thus, an algorithm efficient if the blocks are of small size and with small coefficients. The algorithm works by iteratively improving a feasible solution with augmenting steps, and \(n\)-fold IPs have the special property that augmenting steps are guaranteed to exist in a not-too-large neighborhood. However, this algorithm has never been implemented and evaluated. We have implemented the algorithm and learned the following along the way. The original algorithm is practically unusable, but we discover a series of improvements which make its evaluation possible. Crucially, we observe that a certain constant in the algorithm can be treated as a tuning parameter, which yields an efficient heuristic (essentially searching in a smaller-than-guaranteed neighborhood). Furthermore, the algorithm uses an overly expensive strategy to find a ``best'' step, while finding only an ``approximatelly best'' step is much cheaper, yet sufficient for quick convergence. Using this insight, we improve the asymptotic dependence on \(n\) from \(n^3\) to \(n^2\log n\) which yields the currently asymptotically fastest algorithm for \(n\)-fold IP. Finally, we tested the behavior of the algorithm with various values of the tuning parameter and different strategies of finding improving steps. First, we show that decreasing the tuning parameter initially leads to an increased number of iterations needed for convergence and eventually to getting stuck in local optima, as expected. However, surprisingly small values of the parameter already exhibit good behavior. Second, our new strategy for finding ``approximatelly best'' steps wildly outperforms the original construction.
For the entire collection see [Zbl 1390.68017].A computational investigation on the strength of Dantzig-Wolfe reformulationshttps://zbmath.org/1496.900372022-11-17T18:59:28.764376Z"Bastubbe, Michael"https://zbmath.org/authors/?q=ai:bastubbe.michael"Lübbecke, Marco E."https://zbmath.org/authors/?q=ai:lubbecke.marco-e"Witt, Jonas T."https://zbmath.org/authors/?q=ai:witt.jonas-tSummary: In Dantzig-Wolfe reformulation of an integer program one convexifies a subset of the constraints, leading to potentially stronger dual bounds from the respective linear programming relaxation. As the subset can be chosen arbitrarily, this includes the trivial cases of convexifying no and all constraints, resulting in a weakest and strongest reformulation, respectively. Our computational study aims at better understanding of what happens in between these extremes. For a collection of integer programs with few constraints we compute, optimally solve, and evaluate the relaxations of all possible (exponentially many) Dantzig-Wolfe reformulations (with mild extensions to larger models from the MIPLIBs). We observe that only a tiny number of different dual bounds actually occur and that only a few inclusion-wise minimal representatives exist for each. This aligns with considerably different impacts of individual constraints on the strengthening the relaxation, some of which have almost no influence. In contrast, types of constraints that are convexified in textbook reformulations have a larger effect. We relate our experiments to what could be called a hierarchy of Dantzig-Wolfe reformulations.
For the entire collection see [Zbl 1390.68017].An optimization model for combined selecting, planting and harvesting sugarcane varietieshttps://zbmath.org/1496.900382022-11-17T18:59:28.764376Z"Florentino, Helenice de O."https://zbmath.org/authors/?q=ai:florentino.helenice-de-o"Jones, Dylan F."https://zbmath.org/authors/?q=ai:jones.dylan-f"Irawan, Chandra Ade"https://zbmath.org/authors/?q=ai:irawan.chandra-ade"Ouelhadj, Djamila"https://zbmath.org/authors/?q=ai:ouelhadj.djamila"Khosravi, Banafesh"https://zbmath.org/authors/?q=ai:khosravi.banafesh"Cantane, Daniela R."https://zbmath.org/authors/?q=ai:cantane.daniela-renataSummary: The problem of selecting sugarcane varieties has been widely discussed due to its computational complexity and its great impact for the sugar and ethanol industry. This paper proposes a new integrated mathematical programming model to deal with the selection of sugarcane varieties to be planted and the determination of the optimal period for planting and harvesting in order to increase production in the sugarcane industry. The proposed model optimizes the production of sugarcane and improves the quality of biomass whilst satisfying the main constraints imposed by sugarcane companies. The problem is modelled as an integer linear program and solved using an exact method to generate optimal solutions for small and medium problems. For large problems, metaheuristic approaches based on Genetic Algorithm and Variable Neighbourhood Search are proposed. According to the results, the proposed methodology provides sugarcane company managers with decision support in selecting the most suitable varieties and in determining the best period to plant and harvest their sugarcane.On lattice point counting in \(\varDelta\)-modular polyhedrahttps://zbmath.org/1496.900392022-11-17T18:59:28.764376Z"Gribanov, D. V."https://zbmath.org/authors/?q=ai:gribanov.dimitry-v|gribanov.dmitrii-vladimirovich"Zolotykh, N. Yu."https://zbmath.org/authors/?q=ai:zolotykh.n-yu|zolotykh.nikolai-yurevichSummary: Let a polyhedron \(P\) be defined by one of the following ways:
\begin{itemize}
\item[(i)] \(P = \{x \in \mathbb{R}^n :A x \le b\}\), where \(A \in\mathbb{Z}^{(n+k) \times n}, b \in\mathbb{Z}^{(n+k)}\) and \(\operatorname{rank} A = n\),
\item[(ii)] \(P = \{x \in \mathbb{R}_+^n :A x = b\}\), where \(A \in\mathbb{Z}^{k \times n}, b \in\mathbb{Z}^k\) and \(\operatorname{rank}A = k\),
\end{itemize}
and let all rank order minors of \(A\) be bounded by \(\varDelta\) in absolute values. We show that the short rational generating function for the power series
\[
\sum \limits_{m \in P \cap\mathbb{Z}^n} \mathbf{x}^m
\] can be computed with the arithmetical complexity \(O\left(T_{\operatorname{SNF}}(d) \cdot d^k \cdot d^{\log_2 \varDelta }\right)\), where \(k\) and \(\varDelta\) are fixed, \(d = \dim P\), and \(T_{\operatorname{SNF}}(m)\) is the complexity of computing the Smith Normal Form for \(m \times m\) integer matrices. In particular, \(d = n\), for the case (i), and \(d = n-k\), for the case (ii). The simplest examples of polyhedra that meet the conditions (i) or (ii) are the \textit{simplices}, the \textit{subset sum} polytope and the \textit{knapsack} or \textit{multidimensional knapsack} polytopes. Previously, the existence of a polynomial time algorithm in varying dimension for the considered class of problems was unknown already for simplicies \((k = 1)\). We apply these results to parametric polytopes and show that the step polynomial representation of the function \(c_P(\mathbf{y}) = |P_{\mathbf{y}} \cap \mathbb{Z}^n|\), where \(P_{\mathbf{y}}\) is a parametric polytope, whose structure is close to the cases (i) or (ii), can be computed in polynomial time even if the dimension of \(P_{\mathbf{y}}\) is not fixed. As another consequence, we show that the coefficients \(e_i(P,m)\) of the Ehrhart quasi-polynomial
\[
\left| mP \cap{\mathbb{Z}}^n\right| = \sum \limits_{j = 0}^n e_j(P,m)m^j
\] can be computed with a polynomial-time algorithm, for fixed \(k\) and \(\varDelta \).The supporting hyperplane optimization toolkit for convex MINLPhttps://zbmath.org/1496.900402022-11-17T18:59:28.764376Z"Lundell, Andreas"https://zbmath.org/authors/?q=ai:lundell.andreas"Kronqvist, Jan"https://zbmath.org/authors/?q=ai:kronqvist.jan"Westerlund, Tapio"https://zbmath.org/authors/?q=ai:westerlund.tapioSummary: In this paper, an open-source solver for mixed-integer nonlinear programming (MINLP) problems is presented. The Supporting Hyperplane Optimization Toolkit (SHOT) combines a dual strategy based on polyhedral outer approximations (POA) with primal heuristics. The POA is achieved by expressing the nonlinear feasible set of the MINLP problem with linearizations obtained with the extended supporting hyperplane (ESH) and extended cutting plane (ECP) algorithms. The dual strategy can be tightly integrated with the mixed-integer programming (MIP) subsolver in a so-called single-tree manner, \textit{i.e.}, only a single MIP optimization problem is solved, where the polyhedral linearizations are added as lazy constraints through callbacks in the MIP solver. This enables the MIP solver to reuse the branching tree in each iteration, in contrast to most other POA-based methods. SHOT is available as a COIN-OR open-source project, and it utilizes a flexible task-based structure making it easy to extend and modify. It is currently available in GAMS, and can be utilized in AMPL, Pyomo and JuMP as well through its ASL interface. The main functionality and solution strategies implemented in SHOT are described in this paper, and their impact on the performance are illustrated through numerical benchmarks on 406 convex MINLP problems from the MINLPLib problem library. Many of the features introduced in SHOT can be utilized in other POA-based solvers as well. To show the overall effectiveness of SHOT, it is also compared to other state-of-the-art solvers on the same benchmark set.Decomposition branching for mixed integer programminghttps://zbmath.org/1496.900412022-11-17T18:59:28.764376Z"Yıldız, Barış"https://zbmath.org/authors/?q=ai:yildiz.baris"Boland, Natashia"https://zbmath.org/authors/?q=ai:boland.natashia-l"Savelsbergh, Martin"https://zbmath.org/authors/?q=ai:savelsbergh.martin-w-pSummary: We introduce a novel and powerful approach for solving certain classes of mixed integer programs (MIPs): \textit{decomposition branching}. Two seminal and widely used techniques for solving MIPs, branch-and-bound and decomposition, form its foundation. Computational experiments with instances of a weighted set covering problem and a regionalized \(p\)-median facility location problem with assignment range constraints demonstrate its efficacy: it explores far fewer nodes and can be orders of magnitude faster than a commercial solver and an automatic Dantzig-Wolfe approach.Modeling and optimization of biomass quality variability for decision support systems in biomass supply chainshttps://zbmath.org/1496.900422022-11-17T18:59:28.764376Z"Aboytes-Ojeda, Mario"https://zbmath.org/authors/?q=ai:aboytes-ojeda.mario"Castillo-Villar, Krystel K."https://zbmath.org/authors/?q=ai:castillo-villar.krystel-k"Eksioglu, Sandra D."https://zbmath.org/authors/?q=ai:eksioglu.sandra-duniSummary: A feasible alternative to the production of fossil fuels is the production of biofuels. In order to minimize the costs of producing biofuels, we developed a stochastic programming formulation that optimizes the inbound delivery of biomass. The proposed model captures the variability in the moisture and ash content in the biomass, which define its quality and affect the cost of biofuel. We propose a novel hub-and-spoke network to take advantage of the economies of scale in transportation and to minimize the effect of poor quality. The first-stage variables are the potential locations of depots and biorefineries, and the necessary unit trains to transport the biomass. The second-stage variables are the flow of biomass between the network nodes and the third-party bioethanol supply. A case study from Texas is presented. The numerical results show that the biomass quality changes the selected depot/biorefinery locations and conversion technology in the optimal network design. The cost due to poor biomass quality accounts for approximately 8.31\% of the investment and operational cost. Our proposed L-shaped with connectivity constraints approach outperforms the benchmark L-shaped method in terms of solution quality and computational effort by 0.6\% and 91.63\% on average, respectively.Distributionally robust two-stage stochastic programminghttps://zbmath.org/1496.900432022-11-17T18:59:28.764376Z"Duque, Daniel"https://zbmath.org/authors/?q=ai:duque.daniel"Mehrotra, Sanjay"https://zbmath.org/authors/?q=ai:mehrotra.sanjay"Morton, David P."https://zbmath.org/authors/?q=ai:morton.david-pCorrection to: ``Complexity of stochastic dual dynamic programming''https://zbmath.org/1496.900442022-11-17T18:59:28.764376Z"Lan, Guanghui"https://zbmath.org/authors/?q=ai:lan.guanghuiWe point out some corrections needed in the author's paper [ibid. 191, No. 2 (A), 717--754 (2022; Zbl 1489.90082)].SRKCD: a stabilized Runge-Kutta method for stochastic optimizationhttps://zbmath.org/1496.900452022-11-17T18:59:28.764376Z"Stillfjord, Tony"https://zbmath.org/authors/?q=ai:stillfjord.tony"Williamson, Måns"https://zbmath.org/authors/?q=ai:williamson.mansSummary: We introduce a family of stochastic optimization methods based on the Runge-Kutta-Chebyshev (RKC) schemes. The RKC methods are explicit methods originally designed for solving stiff ordinary differential equations by ensuring that their stability regions are of maximal size. In the optimization context, this allows for larger step sizes (learning rates) and better robustness compared to e.g. the popular stochastic gradient descent method. Our main contribution is a convergence proof for essentially all stochastic Runge-Kutta optimization methods. This shows convergence in expectation with an optimal sublinear rate under standard assumptions of strong convexity and Lipschitz-continuous gradients. For non-convex objectives, we get convergence to zero in expectation of the gradients. The proof requires certain natural conditions on the Runge-Kutta coefficients, and we further demonstrate that the RKC schemes satisfy these. Finally, we illustrate the improved stability properties of the methods in practice by performing numerical experiments on both a small-scale test example and on a problem arising from an image classification application in machine learning.Distributionally robust linear and discrete optimization with marginalshttps://zbmath.org/1496.900462022-11-17T18:59:28.764376Z"Chen, Louis"https://zbmath.org/authors/?q=ai:chen.louis-hsiao-yun"Ma, Will"https://zbmath.org/authors/?q=ai:ma.will"Natarajan, Karthik"https://zbmath.org/authors/?q=ai:natarajan.karthik"Simchi-Levi, David"https://zbmath.org/authors/?q=ai:simchi-levi.david"Yan, Zhenzhen"https://zbmath.org/authors/?q=ai:yan.zhenzhenSummary: In this paper, we study linear and discrete optimization problems in which the objective coefficients are random, and the goal is to evaluate a robust bound on the expected optimal value, where the set of admissible joint distributions is assumed to be specified only up to the marginals. We study a primal-dual formulation for this problem, and in the process, unify existing results with new results. We establish NP-hardness of computing the bound for general polytopes and identify two sufficient conditions: one based on a dual formulation and one based on sublattices that provide a class of polytopes where the robust bounds are efficiently computable. We discuss several examples and applications in areas such as scheduling.Robust min-max regret covering problemshttps://zbmath.org/1496.900472022-11-17T18:59:28.764376Z"Coco, Amadeu A."https://zbmath.org/authors/?q=ai:coco.amadeu-almeida"Santos, Andréa Cynthia"https://zbmath.org/authors/?q=ai:santos.andrea-cynthia"Noronha, Thiago F."https://zbmath.org/authors/?q=ai:noronha.thiago-fSummary: This article deals with two min-max regret covering problems: the min-max regret Weighted Set Covering Problem (\textit{min-max regret} WSCP) and the min-max regret Maximum Benefit Set Covering Problem (\textit{min-max regret} MSCP). These problems are the robust optimization counterparts, respectively, of the Weighted Set Covering Problem and of the Maximum Benefit Set Covering Problem. In both problems, uncertainty in data is modeled by using an interval of continuous values, representing all the infinite values every uncertain parameter can assume. This study has the following major contributions: (i) a proof that MSCP is \(\varSigma_p^2\)-Hard, (ii) a mathematical formulation for the \textit{min-max regret} MSCP, (iii) exact and (iv) heuristic algorithms for the \textit{min-max regret} WSCP and the \textit{min-max regret} MSCP. We reproduce the main exact algorithms for the \textit{min-max regret} WSCP found in the literature: a Logic-based Benders decomposition, an extended Benders decomposition and a branch-and-cut. In addition, such algorithms have been adapted for the \textit{min-max regret} MSCP. Moreover, five heuristics are applied for both problems: two scenario-based heuristics, a path relinking, a pilot method and a linear programming-based heuristic. The goal is to analyze the impact of such methods on handling robust covering problems in terms of solution quality and performance.Convex optimization for finite-horizon robust covariance control of linear stochastic systemshttps://zbmath.org/1496.900482022-11-17T18:59:28.764376Z"Kotsalis, Georgios"https://zbmath.org/authors/?q=ai:kotsalis.georgios"Lan, Guanghui"https://zbmath.org/authors/?q=ai:lan.guanghui"Nemirovski, Arkadi S."https://zbmath.org/authors/?q=ai:nemirovski.arkadi-sIn this paper the following finite horizon, discrete-time control problem is considered:
\begin{gather*}
x_{0}=z+s_{0},\quad x_{t+1}=A_{t}x_{t}+B_{t}u_{t}+B_{t}^{(d)}d_{t}+B_{t} ^{(s)}e_{t}\\
y_{t}=C_{t}x_{t}+D_{t}^{(d)}d_{t}+D_{t}^{(s)}e_{t},\qquad0\leq t\leq N-1
\end{gather*}
where \(x_{t}\in \mathbb{R}^{n_{x}}\) are states, \(u_{t}\in \mathbb{R}^{n_{u}}\) are controls, \(y_{t}\in \mathbb{R}^{n_{y}}\) are observable outputs, \(z\in \mathbb{R}^{n_{x}}\) and \(d_{t}\in \mathbb{R}^{n_{d}}\) are deterministic factors, \(s_{0}\in \mathbb{R}^{n_{x}}\), \(e_{t}\in \mathbb{R}^{n_{e}}\) are stochastic factors. The deterministic disturbance vector \(\zeta=\left[ z;d_{0};\ldots;d_{N-1}\right] \) is assumed to lie in an ellitop (for example, a finite intersection of centered at the origin ellipsoids and elliptic cylinders). \(A_{t},B_{t},\ldots,D_{t}^{(s)}\) are known matrices.
For this problem a procedure for designing control policies that guarantee some performance specifications is developed. The parameters of the policy are obtained as solutions to an explicit convex program.
Reviewer: Nicolas Hadjisavvas (Ermoupoli)Effective scenarios in multistage distributionally robust optimization with a focus on total variation distancehttps://zbmath.org/1496.900492022-11-17T18:59:28.764376Z"Rahimian, Hamed"https://zbmath.org/authors/?q=ai:rahimian.hamed"Bayraksan, Güzin"https://zbmath.org/authors/?q=ai:bayraksan.guzin"Homem De-Mello, Tito"https://zbmath.org/authors/?q=ai:homem-de-mello.titoRobust inventory theory with perishable productshttps://zbmath.org/1496.900502022-11-17T18:59:28.764376Z"Santos, Marcio Costa"https://zbmath.org/authors/?q=ai:costa-santos.marcio"Agra, Agostinho"https://zbmath.org/authors/?q=ai:agra.agostinho"Poss, Michael"https://zbmath.org/authors/?q=ai:poss.michaelSummary: We consider a robust inventory problem where products are perishable with a given shelf life and demands are assumed uncertain and can take any value in a given polytope. Interestingly, considering uncertain demands leads to part of the production being spoiled, a phenomenon that does not appear in the deterministic context. Based on a deterministic model we propose a robust model where the production decisions are first-stage variables and the inventory levels and the spoiled production are recourse variables that can be adjusted to the demand scenario following a FIFO policy. To handle the non-anticipativity constraints related to the FIFO policy, we propose a non-linear reformulation for the robust problem, which is then linearized using classical techniques. We propose a row-and-column generation algorithm to solve the reformulated model to optimality using a decomposition algorithm. Computational tests show that the decomposition approach can solve a set of instances representing different practical situations within reasonable amount of time. Moreover, the robust solutions obtained ensure low losses of production when the worst-case scenarios are materialized.Quantum bridge analytics. I: A tutorial on formulating and using QUBO modelshttps://zbmath.org/1496.900512022-11-17T18:59:28.764376Z"Glover, Fred"https://zbmath.org/authors/?q=ai:glover.fred-w"Kochenberger, Gary"https://zbmath.org/authors/?q=ai:kochenberger.gary-a"Hennig, Rick"https://zbmath.org/authors/?q=ai:hennig.rick"Du, Yu"https://zbmath.org/authors/?q=ai:du.yuSummary: Quantum Bridge Analytics relates generally to methods and systems for hybrid classical-quantum computing, and more particularly is devoted to developing tools for bridging classical and quantum computing to gain the benefits of their alliance in the present and enable enhanced practical application of quantum computing in the future. This is the first of a two-part tutorial that surveys key elements of Quantum Bridge Analytics and its applications, with an emphasis on supplementing models with numerical illustrations. In Part 1 (the present paper) we focus on the Quadratic Unconstrained Binary Optimization model which is presently the most widely applied optimization model in the quantum computing area, and which unifies a rich variety of combinatorial optimization problems. This document extends an original version published in 4OR to include a section on advanced models related to quantum optimization and a section reporting comparative computational results on challenging combinatorial applications.The saddle point problem of polynomialshttps://zbmath.org/1496.900522022-11-17T18:59:28.764376Z"Nie, Jiawang"https://zbmath.org/authors/?q=ai:nie.jiawang"Yang, Zi"https://zbmath.org/authors/?q=ai:yang.zi"Zhou, Guangming"https://zbmath.org/authors/?q=ai:zhou.guangmingSummary: This paper studies the saddle point problem of polynomials. We give an algorithm for computing saddle points. It is based on solving Lasserre's hierarchy of semidefinite relaxations. Under some genericity assumptions on defining polynomials, we show that: (i) if there exists a saddle point, our algorithm can get one by solving a finite hierarchy of Lasserre-type semidefinite relaxations; (ii) if there is no saddle point, our algorithm can detect its nonexistence.Golden ratio primal-dual algorithm with linesearchhttps://zbmath.org/1496.900532022-11-17T18:59:28.764376Z"Chang, Xiao-Kai"https://zbmath.org/authors/?q=ai:chang.xiaokai"Yang, Junfeng"https://zbmath.org/authors/?q=ai:yang.junfeng"Zhang, Hongchao"https://zbmath.org/authors/?q=ai:zhang.hongchaoUsing \(\ell_1\)-relaxation and integer programming to obtain dual bounds for sparse PCAhttps://zbmath.org/1496.900542022-11-17T18:59:28.764376Z"Dey, Santanu S."https://zbmath.org/authors/?q=ai:dey.santanu-subhas"Mazumder, Rahul"https://zbmath.org/authors/?q=ai:mazumder.rahul"Wang, Guanyi"https://zbmath.org/authors/?q=ai:wang.guanyiSummary: Principal component analysis (PCA) is one of the most widely used dimensionality reduction tools in scientific data analysis. The PCA direction, given by the leading eigenvector of a covariance matrix, is a linear combination of all features with nonzero loadings; this impedes interpretability. Sparse principal component analysis (SPCA) is a framework that enhances interpretability by incorporating an additional sparsity requirement in the feature weights (factor loadings) while finding a direction that explains the maximal variation in the data. However, unlike PCA, the optimization problem associated with the SPCA problem is NP-hard. Most conventional methods for solving SPCA are heuristics with no guarantees, such as certificates of optimality on the solution quality via associated dual bounds. Dual bounds are available via standard semidefinite programming (SDP)-based relaxations, which may not be tight, and the SDPs are difficult to scale using off-the-shelf solvers. In this paper, we present a convex integer programming (IP) framework to derive dual bounds. At the heart of our approach is the so-called \(\ell_1\)-relaxation of SPCA. Although the \(\ell_1\)-relaxation leads to convex optimization problems for \(\ell_0\)-sparse linear regressions and relatives, it results in a nonconvex optimization problem for the PCA problem. We first show that the \(\ell_1\)-relaxation gives a tight multiplicative bound on SPCA. Then, we show how to use standard integer programming techniques to further relax the \(\ell_1\)-relaxation into a convex IP for which there are good commercial solvers. We present worst-case results on the quality of the dual bound provided by the convex IP. We empirically observe that the dual bounds are significantly better than the worst-case performance and are superior to the SDP bounds on some real-life instances. Moreover, solving the convex IP model using commercial IP solvers appears to scale much better that solving the SDP-relaxation using commercial solvers. To the best of our knowledge, we obtain the best dual bounds for real and artificial instances for SPCA problems involving covariance matrices of size up to \(2,000 \times 2,000\).Potential function-based framework for minimizing gradients in convex and min-max optimizationhttps://zbmath.org/1496.900552022-11-17T18:59:28.764376Z"Diakonikolas, Jelena"https://zbmath.org/authors/?q=ai:diakonikolas.jelena"Wang, Puqian"https://zbmath.org/authors/?q=ai:wang.puqianInertial accelerated primal-dual methods for linear equality constrained convex optimization problemshttps://zbmath.org/1496.900562022-11-17T18:59:28.764376Z"He, Xin"https://zbmath.org/authors/?q=ai:he.xin"Hu, Rong"https://zbmath.org/authors/?q=ai:hu.rong"Fang, Ya-Ping"https://zbmath.org/authors/?q=ai:fang.yapingSummary: In this paper, we propose an inertial accelerated primal-dual method for the linear equality constrained convex optimization problem. When the objective function has a ``nonsmooth + smooth'' composite structure, we further propose an inexact inertial primal-dual method by linearizing the smooth individual function and solving the subproblem inexactly. Assuming merely convexity, we prove that the proposed methods enjoy \(\mathcal{O}(1/k^2)\) convergence rate on the objective residual and the feasibility violation in the primal model. Numerical results are reported to demonstrate the validity of the proposed methods.An accelerated variance reducing stochastic method with Douglas-Rachford splittinghttps://zbmath.org/1496.900572022-11-17T18:59:28.764376Z"Liu, Jingchang"https://zbmath.org/authors/?q=ai:liu.jingchang"Xu, Linli"https://zbmath.org/authors/?q=ai:xu.linli"Shen, Shuheng"https://zbmath.org/authors/?q=ai:shen.shuheng"Ling, Qing"https://zbmath.org/authors/?q=ai:ling.qingSummary: We consider the problem of minimizing the regularized empirical risk function which is represented as the average of a large number of convex loss functions plus a possibly non-smooth convex regularization term. In this paper, we propose a fast variance reducing (VR) stochastic method called Prox2-SAGA. Different from traditional VR stochastic methods, Prox2-SAGA replaces the stochastic gradient of the loss function with the corresponding gradient mapping. In addition, Prox2-SAGA also computes the gradient mapping of the regularization term. These two gradient mappings constitute a Douglas-Rachford splitting step. For strongly convex and smooth loss functions, we prove that Prox2-SAGA can achieve a linear convergence rate comparable to other accelerated VR stochastic methods. In addition, Prox2-SAGA is more practical as it involves only the stepsize to tune. When each loss function is smooth but non-strongly convex, we prove a convergence rate of \({\mathcal {O}}(1/k)\) for the proposed Prox2-SAGA method, where \(k\) is the number of iterations. Moreover, experiments show that Prox2-SAGA is valid for non-smooth loss functions, and for strongly convex and smooth loss functions, Prox2-SAGA is prominently faster when loss functions are ill-conditioned.Fast convergence of generalized forward-backward algorithms for structured monotone inclusionshttps://zbmath.org/1496.900582022-11-17T18:59:28.764376Z"Maingé, Paul-Emile"https://zbmath.org/authors/?q=ai:mainge.paul-emileSummary: We develop rapidly convergent forward-backward algorithms for computing zeroes of the sum of finitely many maximally monotone operators. A modification of the classical forward-backward method for two general operators is first considered, by incorporating an inertial term (close to the acceleration techniques introduced by Nesterov), a constant relaxation factor and a correction
term. In a Hilbert space setting, we prove the weak convergence to equilibria of the iterates \((x_n)\), with worst-case rates of \(o(n^{-1})\) in terms of both the discrete velocity and the fixed point residual, instead of the classical rates of \(\mathcal O(n^{-1/2})\) established so far for related algorithms. Our procedure
is then adapted to more general monotone inclusions and a fast primal-dual algorithm is proposed for solving convex-concave saddle point problems.Nonlinear optimization and support vector machineshttps://zbmath.org/1496.900592022-11-17T18:59:28.764376Z"Piccialli, Veronica"https://zbmath.org/authors/?q=ai:piccialli.veronica"Sciandrone, Marco"https://zbmath.org/authors/?q=ai:sciandrone.marcoSummary: Support vector machine (SVM) is one of the most important class of machine learning models and algorithms, and has been successfully applied in various fields. Nonlinear optimization plays a crucial role in SVM methodology, both in defining the machine learning models and in designing convergent and efficient algorithms for large-scale training problems. In this paper we present the convex programming problems underlying SVM focusing on supervised binary classification. We analyze the most important and used optimization methods for SVM training problems, and we discuss how the properties of these problems can be incorporated in designing useful algorithms.Fast inertial dynamic algorithm with smoothing method for nonsmooth convex optimizationhttps://zbmath.org/1496.900602022-11-17T18:59:28.764376Z"Qu, Xin"https://zbmath.org/authors/?q=ai:qu.xin"Bian, Wei"https://zbmath.org/authors/?q=ai:bian.weiSummary: In order to solve the minimization of a nonsmooth convex function, we design an inertial second-order dynamic algorithm, which is obtained by approximating the nonsmooth function by a class of smooth functions. By studying the asymptotic behavior of the dynamic algorithm, we prove that each trajectory of it weakly converges to an optimal solution under some appropriate conditions on the smoothing parameters, and the convergence rate of the objective function values is \(o\left( t^{-2}\right)\). We also show that the algorithm is stable, that is, this dynamic algorithm with a perturbation term owns the same convergence properties when the perturbation term satisfies certain conditions. Finally, we verify the theoretical results by some numerical experiments.Abstract strongly convergent variants of the proximal point algorithmhttps://zbmath.org/1496.900612022-11-17T18:59:28.764376Z"Sipoş, Andrei"https://zbmath.org/authors/?q=ai:sipos.andreiSummary: We prove an abstract form of the strong convergence of the Halpern-type and Tikhonov-type proximal point algorithms in CAT(0) spaces. In addition, we derive uniform and computable rates of metastability (in the sense of Tao) for these iterations using proof mining techniques.The \(p\)-Lagrangian relaxation for separable nonconvex MIQCQP problemshttps://zbmath.org/1496.900622022-11-17T18:59:28.764376Z"Andrade, Tiago"https://zbmath.org/authors/?q=ai:andrade.tiago"Belyak, Nikita"https://zbmath.org/authors/?q=ai:belyak.nikita"Eberhard, Andrew"https://zbmath.org/authors/?q=ai:eberhard.andrew-c"Hamacher, Silvio"https://zbmath.org/authors/?q=ai:hamacher.silvio"Oliveira, Fabricio"https://zbmath.org/authors/?q=ai:oliveira.fabricio-alvesSummary: This paper presents a novel technique to compute Lagrangian bounds for nonconvex mixed-integer quadratically constrained quadratic programming problems presenting a separable structure (i.e., a separable problems) such as those arising in deterministic equivalent representations of two-stage stochastic programming problems. In general, the nonconvex nature of these models still poses a challenge to the available solvers, which do not consistently perform well for larger-scale instances. Therefore, we propose an appealing alternative algorithm that allows for overcoming computational performance issues. Our novel technique, named the \(p\)-Lagrangian decomposition, is a decomposition method that combines Lagrangian decomposition with mixed-integer programming-based relaxations. These relaxations are obtained using the \textit{reformulated normalised multiparametric disaggregation technique} and can be made arbitrarily precise by means of a precision parameter \(p\). We provide a technical analysis showing the convergent behaviour of the approach as the approximation is made increasingly precise. We observe that the proposed method presents significant reductions in computational time when compared with a previously proposed techniques in the literature and the direct employment of a commercial solver. Moreover, our computational experiments show that the employment of a simple heuristic can recover solutions with small duality gaps.Optimality condition and quasi-conjugate duality with zero gap in nonconvex optimizationhttps://zbmath.org/1496.900632022-11-17T18:59:28.764376Z"Anh, Pham Ngoc"https://zbmath.org/authors/?q=ai:pham-ngoc-anh."Van Thang, Tran"https://zbmath.org/authors/?q=ai:van-thang.tranNonconvex scalar-minimization and vector-minimization problems are studied. The authors extend the concept of quasi-conjugate function \(f^\ast\) of a functon \(f:\mathbb{R}^n \rightarrow \mathbb{R}\), which was introduced in a paper by \textit{P. T. Thach} [J. Optim. Theory Appl. 188, No. 2, 317--331 (2021; Zbl 1471.90134)] as follows:
\[
f^\ast(p) = -\inf \{f(x) \mid p^Tx \geq 1 \}, \forall p \in \mathbb{R}^n.
\]
Quasi-conjugate duality to a general class of non-convex scalar- and vector- minimization problems is developed. The duality is symmetric and has a zero gap. Optimality conditions in the form of generalized KKT conditions are proved.
Reviewer: Karel Zimmermann (Praha)On constrained optimization with nonconvex regularizationhttps://zbmath.org/1496.900642022-11-17T18:59:28.764376Z"Birgin, E. G."https://zbmath.org/authors/?q=ai:birgin.ernesto-g"Martínez, J. M."https://zbmath.org/authors/?q=ai:martinez.jose-mario"Ramos, A."https://zbmath.org/authors/?q=ai:ramos.albertoAuthors' abstract: In many engineering applications, it is necessary to minimize smooth functions plus penalty (or regularization) terms that violate smoothness and convexity. Specific algorithms for this type of problems are available in recent literature. Here, a smooth reformulation is analyzed and equivalence with the original problem is proved both from the points of view of global and local optimization. Moreover, for the cases in which the objective function is much more expensive than the constraints, modelintensive algorithms, accompanied by their convergence and complexity theories, are introduced. Finally, numerical experiments are presented.
Reviewer: Rita Pini (Milano)A generalized proximal linearized algorithm for DC functions with application to the optimal size of the firm problemhttps://zbmath.org/1496.900652022-11-17T18:59:28.764376Z"Cruz Neto, J. X."https://zbmath.org/authors/?q=ai:da-cruz-neto.joao-xavier"Oliveira, P. R."https://zbmath.org/authors/?q=ai:oliveira.paulo-roberto"Soubeyran, A."https://zbmath.org/authors/?q=ai:soubeyran.antoine"Souza, J. C. O."https://zbmath.org/authors/?q=ai:souza.joao-carlos-oSummary: The purpose of this paper is twofold. First, we examine convergence properties of an inexact proximal point method with a quasi distance as a regularization term in order to find a critical point (in the sense of Toland) of a DC function (difference of two convex functions). Global convergence of the sequence and some convergence rates are obtained with additional assumptions. Second, as an application and its inspiration, we study in a dynamic setting, the very important and difficult problem of the limit of the firm and the time it takes to reach it (maturation time), when increasing returns matter in the short run. Both the formalization of the critical size of the firm in term of a recent variational rationality approach of human dynamics and the speed of convergence results are new in Behavioral Sciences.Inertial alternating direction method of multipliers for non-convex non-smooth optimizationhttps://zbmath.org/1496.900662022-11-17T18:59:28.764376Z"Hien, Le Thi Khanh"https://zbmath.org/authors/?q=ai:hien.le-thi-khanh"Phan, Duy Nhat"https://zbmath.org/authors/?q=ai:phan.duy-nhat"Gillis, Nicolas"https://zbmath.org/authors/?q=ai:gillis.nicolasSummary: In this paper, we propose an algorithmic framework, dubbed inertial alternating direction methods of multipliers (iADMM), for solving a class of nonconvex nonsmooth multiblock composite optimization problems with linear constraints. Our framework employs the general minimization-majorization (MM) principle to update each block of variables so as to not only unify the convergence analysis of previous ADMM that use specific surrogate functions in the MM step, but also lead to new efficient ADMM schemes. To the best of our knowledge, in the \textit{nonconvex nonsmooth} setting, ADMM used in combination with the MM principle to update each block of variables, and ADMM combined with \textit{inertial terms for the primal variables} have not been studied in the literature. Under standard assumptions, we prove the subsequential convergence and global convergence for the generated sequence of iterates. We illustrate the effectiveness of iADMM on a class of nonconvex low-rank representation problems.A stochastic primal-dual method for a class of nonconvex constrained optimizationhttps://zbmath.org/1496.900672022-11-17T18:59:28.764376Z"Jin, Lingzi"https://zbmath.org/authors/?q=ai:jin.lingzi"Wang, Xiao"https://zbmath.org/authors/?q=ai:wang.xiao.2|wang.xiao|wang.xiao.1Summary: In this paper we study a class of nonconvex optimization which involves uncertainty in the objective and a large number of nonconvex functional constraints. Challenges often arise when solving this type of problems due to the nonconvexity of the feasible set and the high cost of calculating function value and gradient of all constraints simultaneously. To handle these issues, we propose a stochastic primal-dual method in this paper. At each iteration, a proximal subproblem based on a stochastic approximation to an augmented Lagrangian function is solved to update the primal variable, which is then used to update dual variables. We explore theoretical properties of the proposed algorithm and establish its iteration and sample complexities to find an \(\epsilon\)-stationary point of the original problem. Numerical tests on a weighted maximin dispersion problem and a nonconvex quadratically constrained optimization problem demonstrate the promising performance of the proposed algorithm.Running primal-dual gradient method for time-varying nonconvex problemshttps://zbmath.org/1496.900682022-11-17T18:59:28.764376Z"Tang, Yujie"https://zbmath.org/authors/?q=ai:tang.yujie"Dall'Anese, Emiliano"https://zbmath.org/authors/?q=ai:dallanese.emiliano"Bernstein, Andrey"https://zbmath.org/authors/?q=ai:bernstein.andrey"Low, Steven"https://zbmath.org/authors/?q=ai:low.steven-hCharacterization results of solutions in interval-valued optimization problems with mixed constraintshttps://zbmath.org/1496.900692022-11-17T18:59:28.764376Z"Treanţă, Savin"https://zbmath.org/authors/?q=ai:treanta.savinSummary: In this paper, we establish some characterization results of solutions associated with a class of interval-valued optimization problems with mixed constraints. More precisely, we investigate the connections between the LU-optimal solutions of the considered interval-valued variational control problem and the saddle-points associated with an interval-valued Lagrange functional corresponding to a modified interval-valued variational control problem. The main derived resuts are accompanied by illustrative examples.HNCcorr: combinatorial optimization for neuron identificationhttps://zbmath.org/1496.900702022-11-17T18:59:28.764376Z"Asín Achá, Roberto"https://zbmath.org/authors/?q=ai:asin-acha.roberto"Hochbaum, Dorit S."https://zbmath.org/authors/?q=ai:hochbaum.dorit-s"Spaen, Quico"https://zbmath.org/authors/?q=ai:spaen.quicoSummary: We present a combinatorial algorithm for cell detection in two-photon calcium imaging. Calcium imaging is a modern technique used by neuroscientists for recording movies of in-vivo neuronal activity at cellular resolution. The proposed algorithm, named HNCcorr, builds on the combinatorial clustering problem Hochbaum's Normalized Cut (HNC). HNC is a model that trades off two goals: One goal is that the cluster has low similarity to the remaining objects. The second goal is that the cluster is highly similar to itself. The HNC model is closely related to the Normalized Cut problem of Shi and Malik, a well-known problem in image segmentation. However, whereas Normalized Cut is an NP-hard problem, HNC is solvable in polynomial time. The neuronal cell detection in calcium imaging movies is viewed here as a clustering problem. HNCcorr utilizes HNC to detect cells in these movies as coherent clusters of pixels that are highly distinct from the remaining pixels. HNCcorr guarantees, unlike existing methodologies for cell identification, a globally optimal solution to the underlying optimization problem. Of independent interest is a novel method, named \textit{similarity-squared}, that is devised here for measuring similarity. In an experimental study on data from the Neurofinder cell identification benchmark, HNCcorr is a top performer. In particular, it achieves a higher average score than two frequently used matrix factorization algorithms. The Python and Matlab implementations of HNCcorr used here are publicly available. The use of HNCcorr demonstrates that combinatorial optimization is a valuable tool for neuroscience and other biomedical disciplines.Polyhedral analysis and a new algorithm for the length constrained \(K\)-drones rural postman problemhttps://zbmath.org/1496.900712022-11-17T18:59:28.764376Z"Campbell, James"https://zbmath.org/authors/?q=ai:campbell.james-f"Corberán, Ángel"https://zbmath.org/authors/?q=ai:corberan.angel"Plana, Isaac"https://zbmath.org/authors/?q=ai:plana.isaac"Sanchis, José M."https://zbmath.org/authors/?q=ai:sanchis.jose-maria"Segura, Paula"https://zbmath.org/authors/?q=ai:segura.paulaSummary: The Length Constrained \(K\)-Drones Rural Postman Problem (LC \(K\)-DRPP) is a continuous optimization problem where a set of curved or straight lines of a network have to be traversed, in order to be serviced, by a fleet of homogeneous drones, with total minimum cost. Since the range and endurance of drones is limited, we consider here that the length of each route is constrained to a given limit \(L\). Drones are not restricted to travel on the network, and they can enter and exit a line through any of its points, servicing only a portion of that line. Therefore, shorter solutions are obtained with ``aerial'' drones than with ``ground'' vehicles that are restricted to the network. If a LC \(K\)-DRPP instance is digitized by approximating each line with a polygonal chain, and it is assumed that drones can only enter and exit a line through the points of the chain, an instance of the Length Constrained \(K\)-vehicles Rural Postman Problem (LC K-RPP) is obtained. This is a discrete arc routing problem, and therefore can be solved with combinatorial optimization techniques. However, when the number of points in each polygonal chain is very large, the LC \(K\)-RPP instance can be so large that it is very difficult to solve, even for heuristic algorithms. Therefore, it is necessary to implement a procedure that generates smaller LC \(K\)-RPP instances by approximating each line by a few but ``significant'' points and segments. In this paper, we present a new formulation for the LC \(K\)-RPP with two binary variables for each edge and each drone representing the first and second traversals of the edge, respectively. We make a polyhedral study of the set of solutions of a relaxed formulation and prove that several families of inequalities induce facets of the polyhedron. We design and implement a branch-and-cut algorithm for the LC \(K\)-RPP that incorporates the separation of these inequalities. This B\&C is the main routine of an iterative algorithm that, by solving a LC \(K\)-RPP instance at each step, finds good solutions for the original LC \(K\)-DRPP. The computational results show that the proposed method is effective in finding good solutions for LC \(K\)-DRPP, and that the branch-and-cut algorithm for the LC \(K\)-RPP outperforms the only published exact method for this problem.Matheuristic algorithms for the parallel drone scheduling traveling salesman problemhttps://zbmath.org/1496.900722022-11-17T18:59:28.764376Z"Dell'Amico, Mauro"https://zbmath.org/authors/?q=ai:dellamico.mauro"Montemanni, Roberto"https://zbmath.org/authors/?q=ai:montemanni.roberto"Novellani, Stefano"https://zbmath.org/authors/?q=ai:novellani.stefanoSummary: In a near future drones are likely to become a viable way of distributing parcels in a urban environment. In this paper we consider the parallel drone scheduling traveling salesman problem, where a set of customers requiring a delivery is split between a truck and a fleet of drones, with the aim of minimizing the total time required to service all the customers. We present a set of matheuristic methods for the problem. The new approaches are validated via an experimental campaign on two sets of benchmarks available in the literature. It is shown that the approaches we propose perform very well on small/medium size instances. Solving a mixed integer linear programming model to optimality leads to the first optimality proof for all the instances with 20 customers considered, while the heuristics are shown to be fast and effective on the same dataset. When considering larger instances with 48 to 229 customers, the results are competitive with state-of-the-art methods and lead to 28 new best known solutions out of the 90 instances considered.Homogeneous grouping of non-prime steel products for online auctions: a case studyhttps://zbmath.org/1496.900732022-11-17T18:59:28.764376Z"Ena, Borja"https://zbmath.org/authors/?q=ai:ena.borja"Gomez, Alberto"https://zbmath.org/authors/?q=ai:gomez.alberto"Ponte, Borja"https://zbmath.org/authors/?q=ai:ponte.borja"Priore, Paolo"https://zbmath.org/authors/?q=ai:priore.paolo"Diaz, Diego"https://zbmath.org/authors/?q=ai:diaz.diegoSummary: Not all products meet customers' quality expectations after the steelmaking process. Some of them, labelled as `non-prime' products, are sold in a periodic online auction. These products need to be grouped into the smallest feasible number of bundles as homogeneous as possible, as this increases the attractiveness of the bundles and hence their selling prices. This results in a highly complex optimisation problem, also conditioned by other requirements, with large economic implications. It may be interpreted as a variant of the well-known bin packing problem. In this article, we formalise it mathematically by studying the real problem faced by a multinational in the steel industry. We also propose a structured, three-stage solution procedure: (i) initial division of the products according to their characteristics; (ii) cluster analysis; and (iii) allocation of products to bundles via optimisation methods. In the last stage, we implement three heuristic algorithms: FIFO, greedy, and distance-based. Building on previous works, we develop 80 test instances, which we use to compare the heuristics. We observe that the greedy algorithm generally outperforms its competitors; however, the distance-based one proves to be more appropriate for large sets of products. Last, we apply the proposed solution procedure to real-world datasets and discuss the benefits obtained by the organisation.Legal assignments and fast EADAM with consent via classic theory of stable matchingshttps://zbmath.org/1496.900742022-11-17T18:59:28.764376Z"Faenza, Yuri"https://zbmath.org/authors/?q=ai:faenza.yuri"Zhang, Xuan"https://zbmath.org/authors/?q=ai:zhang.xuanSummary: Gale and Shapley's \textit{stable assignment problem} has been extensively studied, applied, and extended. In the context of school choice, mechanisms often aim at finding an assignment that is more favorable to students. We investigate two extensions introduced in this framework -- \textit{legal assignments} and the \textit{efficiency adjusted deferred acceptance mechanism} (EADAM) algorithm -- through the lens of the classic theory of stable matchings. In any instance, the set \(\mathcal{L}\) of legal assignments is known to contain all stable assignments. We prove that \(\mathcal{L}\) is exactly the set of stable assignments in \textit{another} instance. Moreover, we show that essentially all optimization problems over \(\mathcal{L}\) can be solved within the same time bound needed for solving it over the set of stable assignments. A key tool for this latter result is an algorithm that finds the student-optimal legal assignment. We then generalize our algorithm to obtain the assignment output of EADAM with any given set of consenting students without sacrificing the running time, hence largely improving in both theory and practice over known algorithms. Finally, we show that the set \(\mathcal{L}\) can be much larger than the set of stable matchings, connecting legal matchings with certain concepts and open problems in the literature.Quantum bridge analytics. II: QUBO-plus, network optimization and combinatorial chaining for asset exchangehttps://zbmath.org/1496.900752022-11-17T18:59:28.764376Z"Glover, Fred"https://zbmath.org/authors/?q=ai:glover.fred-w"Kochenberger, Gary"https://zbmath.org/authors/?q=ai:kochenberger.gary-a"Ma, Moses"https://zbmath.org/authors/?q=ai:ma.moses"Du, Yu"https://zbmath.org/authors/?q=ai:du.yuSummary: Quantum Bridge Analytics relates to methods and systems for hybrid classical-quantum computing, and is devoted to developing tools for bridging classical and quantum computing to gain the benefits of their alliance in the present and enable enhanced practical application of quantum computing in the future. This is the second of a two-part tutorial that surveys key elements of Quantum Bridge Analytics and its applications. Part I [\textit{F. Glover} et al., Ann. Oper. Res. 314, No. 1, 141--183 (2022; Zbl 1496.90051)] focused on the Quadratic Unconstrained Binary Optimization (QUBO) model which is presently the most widely applied optimization model in the quantum computing area, and which unifies a rich variety of combinatorial optimization problems. Part II (the present paper) introduces the domain of QUBO-Plus models that enables a larger range of problems to be handled effectively. After illustrating the scope of these QUBO-Plus models with examples, we give special attention to an important instance of these models called the Asset Exchange Problem (AEP). Solutions to the AEP enable market players to identify exchanges of assets that benefit all participants. Such exchanges are generated by a combination of two optimization technologies for this class of QUBO-Plus models, one grounded in network optimization and one based on a new metaheuristic optimization approach called combinatorial chaining. This combination opens the door to expanding the links to quantum computing applications established by QUBO models through the Quantum Bridge Analytics perspective. We show how the modeling and solution capability for the AEP instance of QUBO-Plus models provides a framework for solving a broad range of problems arising in financial, industrial, scientific, and social settings.An efficient local search for the minimum independent dominating set problemhttps://zbmath.org/1496.900762022-11-17T18:59:28.764376Z"Haraguchi, Kazuya"https://zbmath.org/authors/?q=ai:haraguchi.kazuyaSummary: In the present paper, we propose an efficient local search for the minimum independent dominating set problem. We consider a local search that uses \(k\)-swap as the neighborhood operation. Given a feasible solution \(S\), it is the operation of obtaining another feasible solution by dropping exactly \(k\) vertices from \(S\) and then by adding any number of vertices to it. We show that, when \(k=2\) (resp., \(k=3\) and a given solution is minimal with respect to 2-swap), we can find an improved solution in the neighborhood or conclude that no such solution exists in \(O(n\Delta)\) (resp., \(O(n\Delta^3))\) time, where \(n\) denotes the number of vertices and \(\Delta\) denotes the maximum degree. We develop a metaheuristic algorithm that repeats the proposed local search and the plateau search iteratively, where the plateau search examines solutions of the same size as the current solution that are obtainable by exchanging a solution vertex and a non-solution vertex. The algorithm is so effective that, among 80 DIMACS graphs, it updates the best-known solution size for five graphs and performs as well as existing methods for the remaining graphs.
For the entire collection see [Zbl 1390.68017].The single line moving target traveling salesman problem with release timeshttps://zbmath.org/1496.900772022-11-17T18:59:28.764376Z"Hassoun, Michael"https://zbmath.org/authors/?q=ai:hassoun.michael"Shoval, Shraga"https://zbmath.org/authors/?q=ai:shoval.shraga"Simchon, Eran"https://zbmath.org/authors/?q=ai:simchon.eran"Yedidsion, Liron"https://zbmath.org/authors/?q=ai:yedidsion.lironSummary: We define and study a variant of the Moving Target Traveling Salesman Problem, with all targets confined to a line and moving at the same speed. Target may appear at different times and the agent's (salesman's) objective is to intercept all targets in a minimum of time. We present a polynomial time algorithm to solve this problem.An effective heuristic based on column generation for the two-dimensional three-stage steel plate cutting problemhttps://zbmath.org/1496.900782022-11-17T18:59:28.764376Z"Long, Jianyu"https://zbmath.org/authors/?q=ai:long.jianyu"Zheng, Zhong"https://zbmath.org/authors/?q=ai:zheng.zhong"Gao, Xiaoqiang"https://zbmath.org/authors/?q=ai:gao.xiaoqiang"Pardalos, Panos M."https://zbmath.org/authors/?q=ai:pardalos.panos-m"Hu, Wanzhe"https://zbmath.org/authors/?q=ai:hu.wanzheSummary: In this study, we focus on the steel plate cutting problem (SPCP), where a set of rectangular order plates with specified demand are cut from large rectangular steel plates. The aim of solving SPCP is to minimize the number of steel plates used in the cutting process. According to the analysis of the cutting production line in steel mills, we regard the SPCP as a two-dimensional non-exact three-stage cutting stock problem (2D3SCSP) with two additional practical constraints. Since these two practical constraints limit the length between any two adjacent guillotine cuts in the first stage by a predetermined parameter and the number of guillotine cuts in the second stage by one, the existing solving methods proposed for 2D3SCSP cannot be used for SPCP directly. Four heuristics based on column generation (HCG) are proposed to solve SPCP. The performance of the four HCGs is analyzed through conducting a set of experiments, and an effective HCG with the ability of obtaining high-quality solutions within acceptable computational times is finally obtained.Approximation algorithms for some minimum postmen cover problemshttps://zbmath.org/1496.900792022-11-17T18:59:28.764376Z"Mao, Yuying"https://zbmath.org/authors/?q=ai:mao.yuying"Yu, Wei"https://zbmath.org/authors/?q=ai:yu.wei"Liu, Zhaohui"https://zbmath.org/authors/?q=ai:liu.zhaohui"Xiong, Jiafeng"https://zbmath.org/authors/?q=ai:xiong.jiafengSummary: In this work we introduce the Minimum Rural Postmen Cover Problem (MRPCP) and the Minimum Chinese Postmen Cover Problem (MCPCP). The MRPCP aims to cover a given subset \(R\) of edges of an undirected weighted graph \(G = ( V , E )\) by a minimum size set of closed walks of bounded length \(\lambda \). The MCPCP is a special case of the MRPCP with \(R = E\). We give the first approximation algorithms for these two problems, which have constant approximation ratios of 5 and 4, respectively.Covering and packing of triangles intersecting a straight linehttps://zbmath.org/1496.900802022-11-17T18:59:28.764376Z"Pandit, Supantha"https://zbmath.org/authors/?q=ai:pandit.supanthaSummary: We study four geometric optimization problems: \textit{set cover}, \textit{hitting set}, \textit{piercing set}, and \textit{independent set} with \textit{right-triangles} (a triangle is a right-triangle whose base is parallel to the \(x\)-axis, perpendicular is parallel to the \(y\)-axis, and the slope of the hypotenuse is \(- 1\)). The input triangles are constrained to be intersecting a \textit{straight line}. The straight line can either be a \textit{horizontal} or an \textit{inclined} line (a line whose slope is \(- 1\)). A right-triangle is said to be a \(\lambda\)-\textit{right-triangle}, if the length of both its base and perpendicular is \(\lambda \). For 1-right-triangles where the triangles intersect an inclined line, we prove that the set cover and hitting set problems are \(\mathsf{NP} \)-hard, whereas the piercing set and independent set problems are in \(\mathsf{P} \). The same results hold for 1-right-triangles where the triangles are intersecting a horizontal line instead of an inclined line. We prove that the piercing set and independent set problems with right-triangles intersecting an inclined line are \(\mathsf{NP} \)-hard. Finally, we give an \(n^{O ( \lceil \log c \rceil + 1 )}\) time exact algorithm for the independent set problem with \(\lambda \)-right-triangles intersecting a straight line such that \(\lambda\) takes more than one value from \([ 1 , c ]\), for some integer \(c\). We also present \(O ( n^2 )\)-time dynamic programming algorithms for the independent set problem with 1-right-triangles where the triangles intersect a horizontal line and an inclined line.Objective selection for cancer treatment: an inverse optimization approachhttps://zbmath.org/1496.900812022-11-17T18:59:28.764376Z"Ajayi, Temitayo"https://zbmath.org/authors/?q=ai:ajayi.temitayo"Lee, Taewoo"https://zbmath.org/authors/?q=ai:lee.taewoo"Schaefer, Andrew J."https://zbmath.org/authors/?q=ai:schaefer.andrew-jSummary: In radiation therapy treatment plan optimization, selecting a set of clinical objectives that are tractable and parsimonious yet effective is a challenging task. In clinical practice, this is typically done by trial and error based on the treatment planner's subjective assessment, which often makes the planning process inefficient and inconsistent. We develop the objective selection problem that infers a sparse set of objectives for prostate cancer treatment planning based on historical treatment data. We formulate the problem as a nonconvex bilevel mixed-integer program using inverse optimization and highlight its connection with feature selection to propose multiple solution approaches, including greedy heuristics and regularized problems and application-specific methods that use anatomical information of the patients. Our results show that the proposed heuristics find objectives that are near optimal. Via curve analysis on dose-volume histograms, we show that the learned objectives closely represent latent clinical preferences.Exact and heuristic methods to solve a bi-objective problem of sustainable cultivationhttps://zbmath.org/1496.900822022-11-17T18:59:28.764376Z"Aliano, Angelo Filho"https://zbmath.org/authors/?q=ai:aliano.angelo-filho"de Oliveira Florentino, Helenice"https://zbmath.org/authors/?q=ai:de-oliveira-florentino.helenice"Vaz Pato, Margarida"https://zbmath.org/authors/?q=ai:vaz-pato.margarida"Poltroniere, Sônia Cristina"https://zbmath.org/authors/?q=ai:poltroniere.sonia-cristina"da Silva Costa, João Fernando"https://zbmath.org/authors/?q=ai:da-silva-costa.joao-fernandoSummary: This work proposes a binary nonlinear bi-objective optimization model for the problem of planning the sustainable cultivation of crops. The solution to the problem is a planting schedule for crops to be cultivated in predefined plots, in order to minimize the possibility of pest proliferation and maximize the profit of this process. Biological constraints were also considered. Exact methods, based on the nonlinear model and on a linearization of that model were proposed to generate Pareto optimal solutions for the problem of sustainable cultivation, along with a metaheuristic approach for the problem based on a genetic algorithm and on constructive heuristics. The methods were tested using semi-randomly generated instances to simulate real situations. According to the experimental results, the exact methodologies performed favorably for small and medium size instances. The heuristic method was able to potentially determine Pareto optimal solutions of good quality, in a reduced computational time, even for high dimension instances. Therefore, the mathematical models and the methods proposed may support a powerful methodology for this complex decision-making problem.A Lagrangian relaxation algorithm for optimizing a bi-objective agro-supply chain model considering CO\(_2\) emissionshttps://zbmath.org/1496.900832022-11-17T18:59:28.764376Z"Keshavarz-Ghorbani, Fatemeh"https://zbmath.org/authors/?q=ai:keshavarz-ghorbani.fatemeh"Pasandideh, Seyed Hamid Reza"https://zbmath.org/authors/?q=ai:pasandideh.seyed-hamid-rezaSummary: In this research, an agro-supply chain in the context of both economic and environmental issues has been investigated. To this end, a bi-objective model is formulated as a mixed-integer linear programming that aims to minimize the total costs and CO\(_2\) emissions. It generates the integration between purchasing, transporting, and storing decisions, considering specific characteristics of agro-products such as seasonality, perishability, and uncertainty. This study provides a different set of temperature conditions for preserving products from spoilage. In addition, a robust optimization approach is used to tackle the uncertainty in this paper. Then, \( \varepsilon \)-constraint method is used to convert the bi-objective model to a single one. To solve the problem, Lagrangian relaxation algorithm is applied as an efficient approach giving lower bounds for the original problem and used for estimating upper bounds. At the end, a real case study is presented to give valuable insight via assessing the impacts of uncertainty in system costs.Multicriteria optimization problems under conditions of nonstatistical uncertaintyhttps://zbmath.org/1496.900842022-11-17T18:59:28.764376Z"Mukhamedieva, D. T."https://zbmath.org/authors/?q=ai:mukhamedieva.d-t(no abstract)An algorithm based on fuzzy set theory for solving multicriteria optimization problemshttps://zbmath.org/1496.900852022-11-17T18:59:28.764376Z"Mukhamedieva, D. T."https://zbmath.org/authors/?q=ai:mukhamedieva.d-t(no abstract)Fritz John optimality conditions for interval-valued multi-objective functions using gH-symmetrical derivativehttps://zbmath.org/1496.900862022-11-17T18:59:28.764376Z"Rastogi, Sachin"https://zbmath.org/authors/?q=ai:rastogi.sachin"Iqbal, Akhlad"https://zbmath.org/authors/?q=ai:iqbal.akhlad"Rajan, Sanjeev"https://zbmath.org/authors/?q=ai:rajan.sanjeevOn the quasiconcave multilevel programming problemshttps://zbmath.org/1496.900872022-11-17T18:59:28.764376Z"Sadeghi, H."https://zbmath.org/authors/?q=ai:sadeghi.hamid-m-m|sadeghi.hassan|sadeghi.hatef|sadeghi.haibatolah|sadeghi.habibe|sadeghi.hossein|sadeghi.hamed"Esmaeili, M."https://zbmath.org/authors/?q=ai:esmaeili.mohammad|esmaeili.mostafa|esmaeili.mehdi|esmaeili.mahboobeh|esmaeili.mahin|esmaeili.maryam|esmaeili.mortezaEfficient fair division with minimal sharinghttps://zbmath.org/1496.900882022-11-17T18:59:28.764376Z"Sandomirskiy, Fedor"https://zbmath.org/authors/?q=ai:sandomirskiy.fedor"Segal-Halevi, Erel"https://zbmath.org/authors/?q=ai:segal-halevi.erelSummary: A collection of objects, some of which are good and some of which are bad, is to be divided fairly among agents with different tastes, modeled by additive utility functions. If the objects cannot be shared, so that each of them must be entirely allocated to a single agent, then a fair division may not exist. What is the smallest number of objects that must be shared between two or more agents to attain a fair and efficient division? In this paper, fairness is understood as proportionality or envy-freeness and efficiency as fractional Pareto-optimality. We show that, for a generic instance of the problem (all instances except a zero-measure set of degenerate problems), a \textit{fair fractionally Pareto-optimal division with the smallest possible number of shared objects can be found in polynomial time}, assuming that the number of agents is fixed. The problem becomes computationally hard for degenerate instances, where agents' valuations are aligned for many objects.Connectedness of solution sets for generalized vector equilibrium problems via free-disposal sets in complete metric spacehttps://zbmath.org/1496.900892022-11-17T18:59:28.764376Z"Shao, Chong-Yang"https://zbmath.org/authors/?q=ai:shao.chongyang"Peng, Zai-Yun"https://zbmath.org/authors/?q=ai:peng.zaiyun"Xiao, Yi-Bin"https://zbmath.org/authors/?q=ai:xiao.yibin"Zhao, Yong"https://zbmath.org/authors/?q=ai:zhao.yongSummary: In this paper, the connectedness of solution sets for generalized vector equilibrium problems via free-disposal sets (GVEPVF) in complete metric space is discussed. Firstly, by virtue of Gerstewitz scalarization functions and oriented distance functions, a new scalarization function \(\omega\) is constructed and some properties of it are given. Secondly, with the help of \(\omega \), the existence of solutions for scalarization problems (GVEPVF)\(_\omega\) and the relationship between the solution sets of (GVEPVF)\(_\omega\) and (GVEPVF) are obtained. Then, under some suitable assumptions, sufficient conditions of (path) connectedness of solution sets for (GVEPVF) are established. Finally, as an application, the connectedness results of \(E\)-efficient solution set for a class of vector programming problems are derived. The obtained results are new, and some examples are given to illustrate the main results.Finding non dominated points for multiobjective integer convex programs with linear constraintshttps://zbmath.org/1496.900902022-11-17T18:59:28.764376Z"Zerfa, Lamia"https://zbmath.org/authors/?q=ai:zerfa.lamia"Chergui, Mohamed El-Amine"https://zbmath.org/authors/?q=ai:chergui.mohamed-el-amineSummary: In this paper, we present a branch-and-bound based algorithm to generate all non dominated points for a multiobjective integer programming problem with convex objective functions and linear constraints (MOICP). The principle is to solve a single objective program \((P)\) defined from the original MOICP program with relaxed integrality constraints. Whenever an integer solution is found through the branching process, a node is created in the search tree for each criterion. That is, by adding a cutting plane that locally approximates the criterion, as to exclude a subset of dominated points. The nodes are traversed according to the depth-first strategy and the same process is repeated for the obtained programs as \((P)\). Finally, as to illustrate the efficiency of the suggested algorithm, we present an experimental study, where we assess its efficiency using randomly generated quadratic multiobjective integer problems with linear constraints.Quantifying uncertainty with ensembles of surrogates for blackbox optimizationhttps://zbmath.org/1496.900912022-11-17T18:59:28.764376Z"Audet, Charles"https://zbmath.org/authors/?q=ai:audet.charles"Le Digabel, Sébastien"https://zbmath.org/authors/?q=ai:le-digabel.sebastien"Saltet, Renaud"https://zbmath.org/authors/?q=ai:saltet.renaudSummary: Blackbox optimization tackles problems where the functions are expensive to evaluate and where no analytical information is available. In this context, a tried and tested technique is to build surrogates of the objective and the constraints in order to conduct the optimization at a cheaper computational cost. This work introduces an extension to a specific type of surrogates: ensembles of surrogates, enabling them to quantify the uncertainty on the predictions they produce. The resulting extended ensembles of surrogates behave as stochastic models and allow the use of efficient Bayesian optimization tools. The method is incorporated in the search step of the mesh adaptive direct search (MADS) algorithm to improve the exploration of the search space. Computational experiments are conducted on seven analytical problems, two multi-disciplinary optimization problems and two simulation problems. The results show that the proposed approach solves expensive simulation-based problems at a greater precision and with a lower computational effort than stochastic models.Block coordinate descent for smooth nonconvex constrained minimizationhttps://zbmath.org/1496.900922022-11-17T18:59:28.764376Z"Birgin, E. G."https://zbmath.org/authors/?q=ai:birgin.ernesto-g"Martínez, J. M."https://zbmath.org/authors/?q=ai:martinez.jose-marioSummary: At each iteration of a block coordinate descent method one minimizes an approximation of the objective function with respect to a generally small set of variables subject to constraints in which these variables are involved. The unconstrained case and the case in which the constraints are simple were analyzed in the recent literature. In this paper we address the problem in which block constraints are not simple and, moreover, the case in which they are not defined by global sets of equations and inequations. A general algorithm that minimizes quadratic models with quadratic regularization over blocks of variables is defined and convergence and complexity are proved. In particular, given tolerances \(\delta >0\) and \(\varepsilon >0\) for feasibility/complementarity and optimality, respectively, it is shown that a measure of \((\delta,0)\)-criticality tends to zero; and the number of iterations and functional evaluations required to achieve \((\delta,\varepsilon)\)-criticality is \(O(\varepsilon^{-2})\). Numerical experiments in which the proposed method is used to solve a continuous version of the traveling salesman problem are presented.A new view of some fundamental results in optimizationhttps://zbmath.org/1496.900932022-11-17T18:59:28.764376Z"Evtushenko, Yu. G."https://zbmath.org/authors/?q=ai:evtushenko.yuri-g"Tret'yakov, A. A."https://zbmath.org/authors/?q=ai:tretyakov.alexey-aThe authors point out that some of the basic results of the optimization theory can be proved in a simpler way than it is usually done in the literature. They show that for instance separation theorems, Farkas lemma, contraction mapping principle, implicit function theorems can be avoided and present new elementary proofs of the Lagrange theorem in the case of equality constraints and a Kuhn-Tucker theorem. It is proved that the Farkas theorem and the cone closedness theorem follow from each other. Besides, the authors simplify the Farkas condition in the Farkas theorem and formulate a general version of the Farkas theorem. The equivalence of several optimality conditions is proved. A further part of the paper deals with the reducibility of optimization problems with inequality constraints to optimization problems with equality constraints. The last section of the paper studies the solution of a singular Kuhn-Tucker system using the 2-factor Newton method.
Reviewer: Karel Zimmermann (Praha)Essentials of numerical nonsmooth optimizationhttps://zbmath.org/1496.900942022-11-17T18:59:28.764376Z"Gaudioso, Manlio"https://zbmath.org/authors/?q=ai:gaudioso.manlio"Giallombardo, Giovanni"https://zbmath.org/authors/?q=ai:giallombardo.giovanni"Miglionico, Giovanna"https://zbmath.org/authors/?q=ai:miglionico.giovannaSummary: Approximately sixty years ago two seminal findings, the cutting plane and the subgradient methods, radically changed the landscape of mathematical programming. They provided, for the first time, the practical chance to optimize real functions of several variables characterized by \textit{kinks}, namely by discontinuities in their derivatives. Convex functions, for which a superb body of theoretical research was growing in parallel, naturally became the main application field of choice. The aim of the paper is to give a concise survey of the key ideas underlying successive development of the area, which took the name of numerical nonsmooth optimization. The focus will be, in particular, on the research mainstreams generated under the impulse of the two initial discoveries.Convergence of an augmented Lagrange algorithm for nonlinear optimizations with second-order cone constraintshttps://zbmath.org/1496.900952022-11-17T18:59:28.764376Z"Guo, Jin"https://zbmath.org/authors/?q=ai:guo.jin"He, Suxiang"https://zbmath.org/authors/?q=ai:he.suxiangSummary: An augmented Lagrange algorithm for nonlinear optimizations with second-order cone constraints is proposed based on a Löwner operator associated with a potential function for the optimization problems with inequality constraints. The favorable properties of both the Löwner operator and the corresponding augmented Lagrangian are discussed. And under some mild assumptions, the rate of convergence of the augmented Lagrange algorithm is studied in detail.An ordinal weighted EDM model for nonmetric multidimensional scalinghttps://zbmath.org/1496.900962022-11-17T18:59:28.764376Z"Li, Qing-Na"https://zbmath.org/authors/?q=ai:li.qingna"Zhang, Chi"https://zbmath.org/authors/?q=ai:zhang.chi"Cao, Mengzhi"https://zbmath.org/authors/?q=ai:cao.mengzhiDifference-of-convex algorithms for a class of sparse group \(\ell_0\) regularized optimization problemshttps://zbmath.org/1496.900972022-11-17T18:59:28.764376Z"Li, Wenjing"https://zbmath.org/authors/?q=ai:li.wenjing|li.wenjing.1"Bian, Wei"https://zbmath.org/authors/?q=ai:bian.wei"Toh, Kim-Chuan"https://zbmath.org/authors/?q=ai:toh.kimchuanSeveral approximation algorithms for sparse best rank-1 approximation to higher-order tensorshttps://zbmath.org/1496.900982022-11-17T18:59:28.764376Z"Mao, Xianpeng"https://zbmath.org/authors/?q=ai:mao.xianpeng"Yang, Yuning"https://zbmath.org/authors/?q=ai:yang.yuningSummary: Sparse tensor best rank-1 approximation (BR1Approx), which is a sparsity generalization of the dense tensor BR1Approx, and is a higher-order extension of the sparse matrix BR1Approx, is one of the most important problems in sparse tensor decomposition and related problems arising from statistics and machine learning. By exploiting the multilinearity as well as the sparsity structure of the problem, four polynomial-time approximation algorithms are proposed, which are easily implemented, of low computational complexity, and can serve as initial procedures for iterative algorithms. In addition, theoretically guaranteed approximation lower bounds are derived for all the algorithms. We provide numerical experiments on synthetic and real data to illustrate the efficiency and effectiveness of the proposed algorithms; in particular, serving as initialization procedures, the approximation algorithms can help in improving the solution quality of iterative algorithms while reducing the computational time.On the generalized essential matrix correction: an efficient solution to the problem and its applicationshttps://zbmath.org/1496.900992022-11-17T18:59:28.764376Z"Miraldo, Pedro"https://zbmath.org/authors/?q=ai:miraldo.pedro"Cardoso, João R."https://zbmath.org/authors/?q=ai:cardoso.joao-rSummary: This paper addresses the problem of finding the closest generalized essential matrix from a given \(6\times 6\) matrix, with respect to the Frobenius norm. To the best of our knowledge, this nonlinear constrained optimization problem has not been addressed in the literature yet. Although it can be solved directly, it involves a large number of constraints, and any optimization method to solve it would require much computational effort. We start by deriving a couple of unconstrained formulations of the problem. After that, we convert the original problem into a new one, involving only orthogonal constraints, and propose an efficient algorithm of steepest descent type to find its solution. To test the algorithms, we evaluate the methods with synthetic data and conclude that the proposed steepest descent-type approach is much faster than the direct application of general optimization techniques to the original formulation with 33 constraints and to the unconstrained ones. To further motivate the relevance of our method, we apply it in two pose problems (relative and absolute) using synthetic and real data.Fully stable well-posedness and fully stable minimum with respect to an admissible functionhttps://zbmath.org/1496.901002022-11-17T18:59:28.764376Z"Zhu, Jiangxing"https://zbmath.org/authors/?q=ai:zhu.jiangxing"Arthur Köbis, Markus"https://zbmath.org/authors/?q=ai:kobis.markus-arthur"Hu, Chunhai"https://zbmath.org/authors/?q=ai:hu.chunhai"He, Qinghai"https://zbmath.org/authors/?q=ai:he.qinghai"Li, Jiaxiong"https://zbmath.org/authors/?q=ai:li.jiaxiongThe authors consider parametric optimization problems in an infinite-dimensional setting where the parameters are taken from a metric space. In particular, parameter and tilt perturbations are taken into account. Generalizing known concepts such as stable well-posedness and fully stable Hölder minimum, the authors introduce the two new notions of fully stable well-posedness and fully stable minimum and discuss some of their relationships. Moreover, they present conditions for full stability as well as for full minimality.
Reviewer: Jan-Joachim Rückmann (Bergen)Fractional 0-1 programming and submodularityhttps://zbmath.org/1496.901012022-11-17T18:59:28.764376Z"Han, Shaoning"https://zbmath.org/authors/?q=ai:han.shaoning"Gómez, Andrés"https://zbmath.org/authors/?q=ai:gomez.andres"Prokopyev, Oleg A."https://zbmath.org/authors/?q=ai:prokopyev.oleg-alexanSummary: In this note we study multiple-ratio fractional 0-1 programs, a broad class of \(\mathcal{NP}\)-hard combinatorial optimization problems. In particular, under some relatively mild assumptions we provide a complete characterization of the conditions, which ensure that a single-ratio function is submodular. Then we illustrate our theoretical results with the assortment optimization and facility location problems, and discuss practical situations that guarantee submodularity in the considered application settings. In such cases, near-optimal solutions for multiple-ratio fractional 0-1 programs can be found via simple greedy algorithms.Convergence analysis of new construction explicit methods for solving equilibrium programming and fixed point problemshttps://zbmath.org/1496.901022022-11-17T18:59:28.764376Z"Khunpanuk, Chainarong"https://zbmath.org/authors/?q=ai:khunpanuk.chainarong"Pakkaranang, Nuttapol"https://zbmath.org/authors/?q=ai:pakkaranang.nuttapol"Panyanak, Bancha"https://zbmath.org/authors/?q=ai:panyanak.banchaSummary: In this paper, we present improved iterative methods for evaluating the numerical solution of an equilibrium problem in a Hilbert space with a pseudomonotone and a Lipschitz-type bifunction. The method is built around two computing phases of a proximal-like mapping with inertial terms. Many such simpler step size rules that do not involve line search are examined, allowing the technique to be enforced more effectively without knowledge of the Lipschitz-type constant of the cost bifunction. When the control parameter conditions are properly defined, the iterative sequences converge weakly on a particular solution to the problem. We provide weak convergence theorems without knowing the Lipschitz-type bifunction constants. A few numerical tests were performed, and the results demonstrated the appropriateness and rapid convergence of the new methods over traditional ones.A direct proof of the Gale-Nikaido-Debreu lemma using Sperner's lemmahttps://zbmath.org/1496.901032022-11-17T18:59:28.764376Z"Le, Thanh"https://zbmath.org/authors/?q=ai:le.thanh-manh|le.thanh-tung|le.thanh-nam|le.thanh-nhan|le.thanh-ha|le.thanh-hieu|le.thanh-trung|le.thanh-binh|le.thanh-tam"Le Van, Cuong"https://zbmath.org/authors/?q=ai:le-van.cuong"Pham, Ngoc-Sang"https://zbmath.org/authors/?q=ai:pham.ngoc-sang"Saglam, Cagri"https://zbmath.org/authors/?q=ai:saglam.cagriSummary: The Gale-Nikaido-Debreu lemma plays an important role in establishing the existence of competitive equilibrium. In this paper, we use Sperner's lemma and basic elements of topology to prove the Gale-Nikaido-Debreu lemma.Existence of solutions of set-valued strong vector equilibrium problemshttps://zbmath.org/1496.901042022-11-17T18:59:28.764376Z"Ram, Tirth"https://zbmath.org/authors/?q=ai:ram.tirth"Lal, Parshotam"https://zbmath.org/authors/?q=ai:lal.parshotamSummary: In this paper, we considered set-valued strong vector equilibrium problems and obtained some existence results with and without compactness assumptions in Hausdorff topological vector spaces ordered by a cone. Further, we established some existence results by making use of self-segment dense set, a special type of dense set. Our results in this paper are new which can be considered as a generalization of many known results in the literature.Bumblebee visitation problemhttps://zbmath.org/1496.901052022-11-17T18:59:28.764376Z"Das, Sandip"https://zbmath.org/authors/?q=ai:das.sandip-kumar|das.sandip-kr"Gahlawat, Harmender"https://zbmath.org/authors/?q=ai:gahlawat.harmenderSummary: Let \(G ( V , E , c , w )\) be a weighted graph with vertex set \(V\), edge set \(E\), vertex-capacity function \(c : V \to \mathbb{R}_+\), and edge-weight function \(w : E \to \mathbb{R}_+\). In \textit{Bumblebee visitation problem}, a mobile agent Bumblebee, denoted by \(B\), begins by entering a vertex of the graph, and then moves along the edges of the graph. When \(B\) moves along an edge \(e = u v\), both \(c ( u )\) and \(c ( v )\) are decreased by \(w ( e )\). The \textit{Bumblebee visitation problem} deals with placing and moving \(B\) in \(G\) such that the sum of the residual-capacities at the visited vertices is maximum.
We consider four variants of this problem depending on edge-weights and constraints on the possible movements of \(B\). The four variants are \textit{uniform-weight-constrained \textsc{Bumblebee Visitation} problem}, \textit{variable-weight-constrained \textsc{Bumblebee Visitation} problem}, \textit{uniform-weight-unconstrained \textsc{Bumblebee Visitation} problem}, and \textit{variable-weight-unconstrained \textsc{Bumblebee Visitation} problem}.
We show that all four variants are NP-hard for general graphs, and the variable-weight constrained variant is NP-hard even for star graphs \(( K_{1 , n} )\). On the positive side, for the uniform-weight constrained variant, we give a dynamic programming based linear-time algorithm for trees and a quadratic-time algorithm for cactus. We then extend these algorithms for the variable-weight unconstrained variant. We also give a 3-factor approximation algorithm for the uniform-weight unconstrained variant where each vertex-capacity is at least five.Quantile Markov decision processeshttps://zbmath.org/1496.901062022-11-17T18:59:28.764376Z"Li, Xiaocheng"https://zbmath.org/authors/?q=ai:li.xiaocheng"Zhong, Huaiyang"https://zbmath.org/authors/?q=ai:zhong.huaiyang"Brandeau, Margaret L."https://zbmath.org/authors/?q=ai:brandeau.margaret-lSummary: The goal of a traditional Markov decision process (MDP) is to maximize expected cumulative reward over a defined horizon (possibly infinite). In many applications, however, a decision maker may be interested in optimizing a specific quantile of the cumulative reward instead of its expectation. In this paper, we consider the problem of optimizing the quantiles of the cumulative rewards of an MDP, which we refer to as a quantile Markov decision process (QMDP). We provide analytical results characterizing the optimal QMDP value function and present a dynamic programming-based algorithm to solve for the optimal policy. The algorithm also extends to the MDP problem with a conditional value-at-risk objective. We illustrate the practical relevance of our model by evaluating it on an HIV treatment initiation problem, in which patients aim to balance the potential benefits and risks of the treatment.Optimizing pig marketing decisions under price fluctuationshttps://zbmath.org/1496.901072022-11-17T18:59:28.764376Z"Pourmoayed, Reza"https://zbmath.org/authors/?q=ai:pourmoayed.reza"Nielsen, Lars Relund"https://zbmath.org/authors/?q=ai:nielsen.lars-relundSummary: In the manufacturing of fattening pigs, pig marketing refers to a sequence of culling decisions until the production unit is empty. The profit of a production unit is highly dependent on the price of pork, the cost of feeding and the cost of buying piglets. Price fluctuations in the market consequently influence the profit, and the optimal marketing decisions may change under different price conditions. Most studies have considered pig marketing under constant price conditions. However, because price fluctuations have an influence on profit and optimal marketing decisions it is relevant to consider pig marketing under price fluctuations. In this paper we formulate a hierarchical Markov decision process with two levels which model sequential marketing decisions under price fluctuations in a pig pen. The state of the system is based on information about pork, piglet and feed prices. Moreover, the information is updated using a Bayesian approach and embedded into the hierarchical Markov decision process. The optimal policy is analyzed under different patterns of price fluctuations. We also assess the value of including price information into the model.Bregman proximal point algorithm revisited: a new inexact version and its inertial varianthttps://zbmath.org/1496.901082022-11-17T18:59:28.764376Z"Yang, Lei"https://zbmath.org/authors/?q=ai:yang.lei.3"Toh, Kim-Chuan"https://zbmath.org/authors/?q=ai:toh.kimchuanThe Savage principle and accounting for outcome in single-criterion nonlinear problem under uncertaintyhttps://zbmath.org/1496.901092022-11-17T18:59:28.764376Z"Zhukovskiĭ, Vladislav Iosifovich"https://zbmath.org/authors/?q=ai:zhukovskiy.vladislav-i"Zhukovskaya, Lidiya Vladislavovna"https://zbmath.org/authors/?q=ai:zhukovskaya.lidija-vladislavna"Samsonov, Sergeĭ Petrovich"https://zbmath.org/authors/?q=ai:samsonov.sergei-petrovich"Smirnova, Lidiya Viktorovna"https://zbmath.org/authors/?q=ai:smirnova.lydia-vSummary: In the middle of the last century the American mathematician and statistician professor of Michigan University Leonard Savage (1917--1971) and the well-known economist, professor of Zurich University (Switzerland) Jurg Niehans (1919--2007) independently from each other suggested the approach to decision-making in one-criterion problem under uncertainty (OPU), called the principle of minimax regret. This principle along with Wald principle of guaranteed result (maximin) is playing the most important role in guaranteed under uncertainty decision-making in OPU. The main role in the principle of minimax regret is carrying out the regret function, which determines the Niehans-Savage risk in OPU. Such risk has received the broad extension in practical problems during last years. In the present article we suggest one of possible approaches to finding decision in OPU from the position of a decision-maker, which simultaneously tries to increase the payoff (outcome) and to reduce the risk (i. e., ``to kill two birds with one stone in one throw''). As an application, an explicit form of such a solution was immediately found for a linear-quadratic variant of the OPU of a fairly general form.Sub-linear convergence of a stochastic proximal iteration method in Hilbert spacehttps://zbmath.org/1496.901102022-11-17T18:59:28.764376Z"Eisenmann, Monika"https://zbmath.org/authors/?q=ai:eisenmann.monika"Stillfjord, Tony"https://zbmath.org/authors/?q=ai:stillfjord.tony"Williamson, Måns"https://zbmath.org/authors/?q=ai:williamson.mansSummary: We consider a stochastic version of the proximal point algorithm for convex optimization problems posed on a Hilbert space. A typical application of this is supervised learning. While the method is not new, it has not been extensively analyzed in this form. Indeed, most related results are confined to the finite-dimensional setting, where error bounds could depend on the dimension of the space. On the other hand, the few existing results in the infinite-dimensional setting only prove very weak types of convergence, owing to weak assumptions on the problem. In particular, there are no results that show strong convergence with a rate. In this article, we bridge these two worlds by assuming more regularity of the optimization problem, which allows us to prove convergence with an (optimal) sub-linear rate also in an infinite-dimensional setting. In particular, we assume that the objective function is the expected value of a family of convex differentiable functions. While we require that the full objective function is strongly convex, we do not assume that its constituent parts are so. Further, we require that the gradient satisfies a weak local Lipschitz continuity property, where the Lipschitz constant may grow polynomially given certain guarantees on the variance and higher moments near the minimum. We illustrate these results by discretizing a concrete infinite-dimensional classification problem with varying degrees of accuracy.A convex analysis view of the barrier problemhttps://zbmath.org/1496.901112022-11-17T18:59:28.764376Z"Bessenyei, Mihály"https://zbmath.org/authors/?q=ai:bessenyei.mihaly"Tóth, Norbert"https://zbmath.org/authors/?q=ai:toth.norbertSummary: Besides the simplex algorithm, linear programs can also be solved via interior point methods. The theoretical background of such algorithms is the classical log-barrier problem. The aim of this note is to study and generalize the barrier problem using the standard tools of Convex Analysis.Sketched Newton-Raphsonhttps://zbmath.org/1496.901122022-11-17T18:59:28.764376Z"Yuan, Rui"https://zbmath.org/authors/?q=ai:yuan.rui"Lazaric, Alessandro"https://zbmath.org/authors/?q=ai:lazaric.alessandro"Gower, Robert M."https://zbmath.org/authors/?q=ai:gower.robert-manselImproved exploitation of higher order smoothness in derivative-free optimizationhttps://zbmath.org/1496.901132022-11-17T18:59:28.764376Z"Novitskii, Vasilii"https://zbmath.org/authors/?q=ai:novitskii.vasilii"Gasnikov, Alexander"https://zbmath.org/authors/?q=ai:gasnikov.alexander-vSummary: We consider \(\beta \)-smooth (satisfies the generalized Hölder condition with parameter \(\beta > 2)\) stochastic convex optimization problem with zero-order one-point oracle. The best known result was [\textit{A. Akhavan} et al., ``Exploiting higher order smoothness in derivative-free optimization and continuous bandits'', in: H. Larochelle (ed.) et al., Advances in neural information processing systems. Vancouver, BC, Canada: Curran Associates, Inc. 9017--9027 (2020)] :
\[
{\mathbb{E}}\left[ f(\overline{x}_N) - f(x^\ast)\right] = {\mathcal{O}} \left( \dfrac{n^2}{\gamma N^{\frac{\beta -1}{\beta}}} \right)
\]
in \(\gamma \)-strongly convex case, where \(n\) is the dimension. In this paper we improve this bound:
\[
{\mathbb{E}} \left[ f(\overline{x}_N) - f(x^\ast)\right] = {\mathcal{O}} \left(\dfrac{n^{2-{\frac{1}{\beta}}}}{\gamma N^{\frac{\beta -1}{\beta}}} \right).
\]Chaos based optics inspired optimization algorithms as global solution search approachhttps://zbmath.org/1496.901142022-11-17T18:59:28.764376Z"Bingol, Harun"https://zbmath.org/authors/?q=ai:bingol.harun"Alatas, Bilal"https://zbmath.org/authors/?q=ai:alatas.bilalSummary: Metaheuristic optimization algorithms are efficiently used in many large-scale complex problems. Recently, a physics-based metaheuristic search and optimization method entitled Optics Inspired Optimization (OIO) has been proposed. OIO treats the search field of the interested problem to be optimized as a wavy mirror in which the concave mirror is represented as a valley and the convex mirror is represented as a peak. Each candidate solution represents an artificial light point. OIO is a very new metaheuristic method and different approaches should be integrated to obtain a faster convergence with high accuracy by balancing the exploitation and exploration. This paper is the first work on performance improvement of this method by preventing the falling into local optimum solutions and slow convergence speed. In this article, different ergodic chaotic systems are used for the first time to generate chaotic values instead of random values in OIO processes in order to enhance the global convergence speed and prevent stuck on local solutions of classical OIO algorithm. For this purpose, three new enhanced OIO methods are proposed. Furthermore, a new application area for chaos is proposed. The chaotic OIO algorithms proposed in this study are tested in unconstrained benchmark problems and constrained real-world engineering problems. Promising results are obtained from the detailed simulations.Solution of a fuzzy multicriteria optimization problem under risk conditionshttps://zbmath.org/1496.901152022-11-17T18:59:28.764376Z"Mukhamedieva, D. T."https://zbmath.org/authors/?q=ai:mukhamedieva.d-t(no abstract)Systems analysis of the problem of constructing fuzzy-correct models of decision making problemshttps://zbmath.org/1496.901162022-11-17T18:59:28.764376Z"Mukhamedieva, D. T."https://zbmath.org/authors/?q=ai:mukhamedieva.d-t(no abstract)Models of parametric optimization problems and criteria for their stabilityhttps://zbmath.org/1496.901172022-11-17T18:59:28.764376Z"Mukhamedieva, D. T."https://zbmath.org/authors/?q=ai:mukhamedieva.d-t(no abstract)Fuzzy parametric programming problems in the case of the dependence of the coefficients of the target function on many parametershttps://zbmath.org/1496.901182022-11-17T18:59:28.764376Z"Mukhamedieva, D. T."https://zbmath.org/authors/?q=ai:mukhamedieva.d-t(no abstract)The method of \(R\)-functions in mathematical programming problemshttps://zbmath.org/1496.901192022-11-17T18:59:28.764376Z"Nazirov, Sh. A."https://zbmath.org/authors/?q=ai:nazirov.shodmankula-abdirozikovich(no abstract)Numerical solution of mean field problem with limited management resourcehttps://zbmath.org/1496.910122022-11-17T18:59:28.764376Z"Kornienko, V."https://zbmath.org/authors/?q=ai:kornienko.vladimir-v|kornienko.viktoria-s|kornienko.v-f|kornienko.v-g|kornienko.v-n"Shaydurov, V."https://zbmath.org/authors/?q=ai:shaidurov.vladimir-victorovichSummary: The paper presents a computational algorithm for solving problem formulated in terms of Mean Field Game theory with limited management resource. The Mean Field equilibrium leads to a coupled system of two parabolic partial differential equations: Fokker-Planck-Kolmogorov and Hamilton-Jacobi-Bellman ones with an additional constraint in the form of the inequality. The article is devoted to the discrete approximation of these equations and reformulating the discrete statement in the form of the saddle point problem with the condition of complementary slackness. An iterative algorithm is presented for solving the obtained discrete problem with justification of the convergence of its elements. The convergence of the algorithm as a whole is illustrated by a numerical example.A novel ranking-based non-linear programming approach to solve bi-matrix games in dense fuzzy environmenthttps://zbmath.org/1496.910132022-11-17T18:59:28.764376Z"Karmakar, Shuvasree"https://zbmath.org/authors/?q=ai:karmakar.shuvasree"Rahaman Seikh, Mijanur"https://zbmath.org/authors/?q=ai:seikh.mijanur-rahamanSummary: In reality, occasionally, the players of a bi-matrix game problem are forced to bring little changes in their game strategies to manage the situation. As a result, this phenomenon could lead to a change in the pay-offs of a game problem. This paper aims to model such kind of bi-matrix games with pay-offs as dense fuzzy lock sets. A novel defuzzification function of this new set, viz., \(\mathrm{Val}_D(\cdot)\) function is defined here. An auxiliary quadratic dense fuzzy programming problem (QDFPP) is established to solve the bi-matrix game. Later this QDFPP is transformed into an equivalent crisp programming problem by employing the induced defuzzification function and its linearity property. A notable facet of this approach is that players' profits increase with increased trials. The efficacy and applicability of the proposed methodology are explained by reflecting a tourism planning strategy problem.
For the entire collection see [Zbl 1491.65006].Multicriteria problems with importance-ordered criteria groupshttps://zbmath.org/1496.910442022-11-17T18:59:28.764376Z"Nelyubin, A. P."https://zbmath.org/authors/?q=ai:nelyubin.a-p"Podinovski, V. V."https://zbmath.org/authors/?q=ai:podinovski.vladislav-vSummary: We develop a statement of the decision-making problem in the presence of information about the importance of criteria groups, give definitions of the relationships of the importance of criteria groups, and introduce coefficients of importance and preference relations based on such information. Methods for checking the consistency of information about importance are indicated, and ways of constructing the introduced preference relations are shown. The interrelation of qualitative importance and qualitative probability is revealed.Variational inequalities and general equilibrium modelshttps://zbmath.org/1496.910532022-11-17T18:59:28.764376Z"Donato, Maria Bernadette"https://zbmath.org/authors/?q=ai:donato.maria-bernadette"Maugeri, Antonino"https://zbmath.org/authors/?q=ai:maugeri.antonino"Milasi, Monica"https://zbmath.org/authors/?q=ai:milasi.monica"Villanacci, Antonio"https://zbmath.org/authors/?q=ai:villanacci.antonioSummary: We deal with the study of several general equilibrium models by using the variational inequality theory. The theory of variational inequalities was introduced in the sixties of the past century by \textit{G. Fichera} [Atti Accad. Naz. Lincei, Mem., Cl. Sci. Fis. Mat. Nat., VIII. Ser., Sez. I 7, 91--140 (1964; Zbl 0146.21204)], and
\textit{J. L. Lions} and \textit{G. Stampacchia} [Commun. Pure Appl. Math. 20, 493--519 (1967; Zbl 0152.34601)], as an innovative and effective method to solve equilibrium problems arising in mathematical physics. Afterward this theory turned out as a powerful tool, and it was used to analyze different kinds of equilibrium problems.
For the entire collection see [Zbl 1483.00042].Equilibrium flow assignment in a network of homogeneous goodshttps://zbmath.org/1496.910622022-11-17T18:59:28.764376Z"Krylatov, A. Yu."https://zbmath.org/authors/?q=ai:krylatov.aleksandr-yu"Lonyagina, Yu. E."https://zbmath.org/authors/?q=ai:lonyagina.yuliya-eSummary: This paper is devoted to the problem of analyzing the emergence of a nonzero product flow between suppliers and consumers of a certain product that are distant from each other in space. The problem is formulated as a problem of equilibrium flow assignment in a network of homogeneous goods represented by a digraph that models an integrated market for a certain product with multiple suppliers and consumers with linear functions of demand, supply, and transportation. In the problem under study, an explicit form of conditions for identifying active variables is obtained, as well as an explicit form of the optimal values of the unknown variables. The explicit form of the conditions for the emergence of a nonzero product flow between suppliers-consumers will allow developing methodological decision support tools in the field of analyzing spatial market relations within the framework of some integrated market of homogeneous goods.Hybrid interconnection of iterative bidding and power network dynamics for frequency regulation and optimal dispatchhttps://zbmath.org/1496.910662022-11-17T18:59:28.764376Z"Stegink, Tjerk"https://zbmath.org/authors/?q=ai:stegink.tjerk-w"Cherukuri, Ashish"https://zbmath.org/authors/?q=ai:cherukuri.ashish"De Persis, Claudio"https://zbmath.org/authors/?q=ai:de-persis.claudio"van der Schaft, Arjan"https://zbmath.org/authors/?q=ai:van-der-schaft.arjan-j"Cortés, Jorge"https://zbmath.org/authors/?q=ai:cortes.jorgeEditorial remark: No review copy delivered.Multi-objective optimization of a nonlinear batch time-delay system with minimum system sensitivityhttps://zbmath.org/1496.920452022-11-17T18:59:28.764376Z"Wang, Lei"https://zbmath.org/authors/?q=ai:wang.lei.14"Yuan, Jinlong"https://zbmath.org/authors/?q=ai:yuan.jinlong"Meng, Lixia"https://zbmath.org/authors/?q=ai:meng.lixia"Zhao, Shuang"https://zbmath.org/authors/?q=ai:zhao.shuang"Xie, Jun"https://zbmath.org/authors/?q=ai:xie.jun"Huang, Ming"https://zbmath.org/authors/?q=ai:huang.ming"Teo, Kok Lay"https://zbmath.org/authors/?q=ai:teo.kok-laySummary: In this paper, we consider a nonlinear time-delay dynamic (NTDD) system with uncertain time-delay in batch culture of glycerol bioconversion to 1,3-propanediol (1,3-PD) induced by \textit{Klebsiella pneumoniae}. Our goal is to design an optimization scheme for the NTDD system with the aim of balancing two competing objectives: (i) system cost (the relative error between experimental data and the output of the mathematical model); (ii) system sensitivity (the variation of the system cost with respect to uncertain time-delay). Thus, a multi-objective optimization problem (MOOP) governed by the NTDD system and subject to continuous state inequality constraints is proposed, where the two competing objective functions are to be minimized. The optimization variables in this problem are the initial concentrations of biomass and glycerol along with the free terminal time. The MOOP is first converted into a sequence of single-objective optimization problems (SOOCPs) by using convex weighted sum and modified normal boundary intersection methods. By incorporating the time scaling transformation, the constraint transcription and locally smoothing approximation, a parallel hybrid SOOCP solver is developed based on gradient-based method and genetic algorithm. Finally, numerical results are provided to verify the effectiveness of the proposed solution method.Fast, flexible, and exact minimum flow decompositions via ILPhttps://zbmath.org/1496.920662022-11-17T18:59:28.764376Z"Dias, Fernando H. C."https://zbmath.org/authors/?q=ai:dias.fernando-h-c"Williams, Lucia"https://zbmath.org/authors/?q=ai:williams.lucia"Mumey, Brendan"https://zbmath.org/authors/?q=ai:mumey.brendan"Tomescu, Alexandru I."https://zbmath.org/authors/?q=ai:tomescu.alexandru-ioanSummary: Minimum flow decomposition (MFD) -- the problem of finding a minimum set of paths that perfectly decomposes a flow -- is a classical problem in computer science, and variants of it are powerful models in multiassembly problems in bioinformatics (e.g. RNA assembly). However, because this problem and its variants are NP-hard, practical multiassembly tools either use heuristics or solve simpler, polynomial-time solvable versions of the problem, which may yield solutions that are not minimal or do not perfectly decompose the flow. Many RNA assemblers also use integer linear programming (ILP) formulations of such practical variants, having the major limitation they need to encode all the potentially exponentially many solution paths. Moreover, the only exact solver for MFD does not scale to large instances, and cannot be efficiently generalized to practical MFD variants.
In this work, we provide the first practical ILP formulation for MFD (and thus the first fast and exact solver for MFD), based on encoding all of the exponentially many solution paths using only a \textit{quadratic} number of variables. On both simulated and real flow graphs, our approach runs in under 13 s on average. We also show that our ILP formulation can be easily and efficiently adapted for many practical variants, such as incorporating longer or paired-end reads, or minimizing flow errors.
We hope that our results can remove the current tradeoff between the complexity of a multiassembly model and its tractability, and can lie at the core of future practical RNA assembly tools. Our implementations are freely available at github.com/algbio/MFD-ILP.
For the entire collection see [Zbl 1493.92001].A mixed integer linear programming algorithm for plasmid binninghttps://zbmath.org/1496.920722022-11-17T18:59:28.764376Z"Mane, Aniket"https://zbmath.org/authors/?q=ai:mane.aniket-c"Faizrahnemoon, Mahsa"https://zbmath.org/authors/?q=ai:faizrahnemoon.mahsa"Chauve, Cedric"https://zbmath.org/authors/?q=ai:chauve.cedricSummary: The problem of analysing bacterial isolates in order to detect plasmids has been widely studied. With the development of whole genome sequencing (WGS) technologies, several approaches have been proposed to bin contigs into putative plasmids. Reference-based approaches aim to bin contigs by mapping or comparing their sequences against databases of previously identified plasmids or plasmid genes. On the other hand, de novo approaches use contig features such as read coverage and length for plasmid binning. Hybrid approaches that combine both strategies have also been proposed recently.
We present PlasBin a mixed integer linear programming based hybrid approach for plasmid binning. We evaluate the performance of several binning methods on a real data set of bacterial samples.
For the entire collection see [Zbl 1492.92002].Unknotted strand routings of triangulated mesheshttps://zbmath.org/1496.920732022-11-17T18:59:28.764376Z"Mohammed, Abdulmelik"https://zbmath.org/authors/?q=ai:mohammed.abdulmelik"Hajij, Mustafa"https://zbmath.org/authors/?q=ai:hajij.mustafaSummary: In molecular self-assembly such as DNA origami, a circular strand's topological routing determines the feasibility of a design to assemble to a target. In this regard, the Chinese Postman DNA scaffold routings of \textit{E. Benson} et al. [``DNA rendering of polyhedral meshes at the nanoscale'', Nature 523, No. 7561, 441--444 (2015; \url{doi:10.1038/nature14586})] only ensure the unknottedness of the scaffold strand for triangulated topological spheres. In this paper, we present a cubic-time \(\frac{5}{3}-\)approximation algorithm to compute unknotted Chinese Postman scaffold routings on triangulated orientable surfaces of higher genus. Our algorithm guarantees every edge is routed at most twice, hence permitting low-packed designs suitable for physiological conditions.
For the entire collection see [Zbl 1369.68012].Staticization and iterated staticizationhttps://zbmath.org/1496.930622022-11-17T18:59:28.764376Z"McEneaney, William M."https://zbmath.org/authors/?q=ai:mceneaney.william-mac-m"Zhao, Ruobing"https://zbmath.org/authors/?q=ai:zhao.ruobingStability analysis of nonlinear inviscid microscopic and macroscopic traffic flow models of bidirectional cruise-controlled vehicleshttps://zbmath.org/1496.930652022-11-17T18:59:28.764376Z"Karafyllis, Iasson"https://zbmath.org/authors/?q=ai:karafyllis.iasson"Theodosis, Dionysios"https://zbmath.org/authors/?q=ai:theodosis.dionysios"Papageorgiou, Markos"https://zbmath.org/authors/?q=ai:papageorgiou.markosSummary: The paper introduces a new bidirectional microscopic inviscid adaptive cruise control (ACC) model that uses only spacing information from the preceding and following vehicles in order to select the proper control action to avoid collisions and maintain a desired speed. \(KL\) estimates that guarantee uniform convergence of the ACC model to the set of equilibria are provided. Moreover, the corresponding macroscopic model is derived, consisting of a conservation equation and a momentum equation that contains a nonlinear relaxation term. It is shown that, if the density is sufficiently small, then the macroscopic model has a solution that approaches exponentially the equilibrium speed (in the sup norm) while the density converges exponentially to a traveling wave. Numerical simulations are also provided, illustrating the properties of the microscopic and macroscopic inviscid ACC models.Sampled-data extremum-seeking framework for constrained optimization of nonlinear dynamical systemshttps://zbmath.org/1496.930742022-11-17T18:59:28.764376Z"Hazeleger, Leroy"https://zbmath.org/authors/?q=ai:hazeleger.leroy"Nešić, Dragan"https://zbmath.org/authors/?q=ai:nesic.dragan"van de Wouw, Nathan"https://zbmath.org/authors/?q=ai:van-de-wouw.nathanSummary: Most extremum-seeking control (ESC) approaches focus solely on the problem of finding the extremum of some unknown, steady-state input-output map, providing parameter settings that lead to optimal steady-state system performance. However, many industrial applications also have to deal with constraints on operating conditions due to, e.g., actuator limitations, limitations on tunable system parameters, or constraints on measurable variables. In particular, constraints on measurable variables are typically unknown in terms of their relationship with the tunable system parameters. In addition, the constraints on system inputs as a result of the constraints on measurable variables may conflict with the otherwise optimal operational condition, and hence should be taken into account in the data-based optimization approach. In this work, we propose a sampled-data extremum-seeking framework for the constrained optimization of a class of nonlinear dynamical systems with measurable constrained variables. In this framework, barrier function methods are employed, exploiting both the objective function and constraint functions which are available through output measurement only. We show, under the assumption that the parametric initialization yield operating conditions that do not violate the constraints, that (1) the resulting closed-loop dynamics is stable, (2) constraint satisfaction of the inputs is guaranteed for all iterations of the optimization process, and (3) constrained optimization is achieved. We illustrate the working principle of the proposed framework by means of an industrial case study of the constrained optimization of extreme ultraviolet light generation in a laser-produced plasma source within a state-of-the-art lithography system.On distributed fusion estimation with stochastic scheduling over sensor networkshttps://zbmath.org/1496.931182022-11-17T18:59:28.764376Z"Yu, Dongdong"https://zbmath.org/authors/?q=ai:yu.dongdong"Xia, Yuanqing"https://zbmath.org/authors/?q=ai:xia.yuanqing"Zhai, Di-Hua"https://zbmath.org/authors/?q=ai:zhai.dihua"Zhan, Yufeng"https://zbmath.org/authors/?q=ai:zhan.yufengSummary: The paper deals with the distributed fusion estimation for linear time-varying systems over sensor networks, in which stochastic sensor scheduling and unknown exogenous inputs are taken into account. In the stochastic sensor scheduling, expensive and cheap channels are used to respectively transmit the high-precision data and the low-precision quantized data. Based on the stochastic scheduling scheme, a recursive minimum mean square error (MMSE) estimator is proposed against the unknown inputs. Then, a distributed fusion estimator is presented by combining local estimates and covariances from all sensors, relying on the covariance intersection (CI) fusion rule. Sufficient conditions are established to ensure that the proposed fusion estimator is stable with the stochastically ultimately bounded estimation error. Finally, a target tracking example is given to show the effectiveness of the proposed method.