Abstract: We investigate the problem of separating cover inequalities of maximum-depth exactly. We propose a pseudopolynomial-time dynamic-programming algorithm for its solution, thanks to which we show that this problem is weakly \({\mathcal {N}}{\mathcal {P}}\) -hard (similarly to the problem of separating cover inequalities of maximum violation). We carry out extensive computational experiments on instances of the knapsack and the multi-dimensional knapsack problems with and without conflict constraints. The results show that, with a cutting-plane generation method based on the maximum-depth criterion, we can optimize over the cover-inequality closure by generating a number of cuts smaller than when adopting the standard maximum-violation criterion. We also introduce the Point-to-Hyperplane Distance Knapsack Problem (PHD-KP), a problem closely related to the separation problem for maximum-depth cover inequalities, and show how the proposed dynamic programming algorithm can be adapted for effectively solving the PHD-KP as well. PubDate: 2021-05-01
Abstract: In this paper, we prove new complexity bounds for zeroth-order methods in non-convex optimization with inexact observations of the objective function values. We use the Gaussian smoothing approach of Nesterov and Spokoiny(Found Comput Math 17(2): 527–566, 2015. https://doi.org/10.1007/s10208-015-9296-2) and extend their results, obtained for optimization methods for smooth zeroth-order non-convex problems, to the setting of minimization of functions with Hölder-continuous gradient with noisy zeroth-order oracle, obtaining noise upper-bounds as well. We consider finite-difference gradient approximation based on normally distributed random Gaussian vectors and prove that gradient descent scheme based on this approximation converges to the stationary point of the smoothed function. We also consider convergence to the stationary point of the original (not smoothed) function and obtain bounds on the number of steps of the algorithm for making the norm of its gradient small. Additionally we provide bounds for the level of noise in the zeroth-order oracle for which it is still possible to guarantee that the above bounds hold. We also consider separately the case of \(\nu = 1\) and show that in this case the dependence of the obtained bounds on the dimension can be improved. PubDate: 2021-04-29
Abstract: This paper is focused on solving an industrially-motivated, rich routing variant of the so-called full truckload pickup and delivery problem. It addresses a setting where the distributor has to transport full truckload shipments between distribution centers and customer locations, yet the distributor’s owned fleet is inadequate to perform the totality of the required deliveries and thus a subset of the deliveries has to be outsourced to third-party carriers. In this work, we propose a novel mixed-integer linear programming formulation to model this problem. Using datasets inspired from industrial practice, we evaluate the computational tractability of this model and demonstrate its potential to serve as a decision-support system for real-life operations. Furthermore,we hypothesize that the distributor may realize cost savings when the later portion of the distribution period is utilized to pre-load cargo for delivery during the following period. To that end, we augment the original model to allow for such cargo pre-loading, and we conduct a rolling horizon-based simulation study to quantify its overall economic effect. PubDate: 2021-04-26
Abstract: In this paper, we propose a new modified subgradient extragradient method for solving equilibrium problems involving pseudomonotone and Lipchitz-type bifunctions in Hilbert spaces. We establish the strong convergence of the proposed method under several suitable conditions. In addition, the linear convergence is obained under strong pseudomonotonicity assumption. Our results generalize and extend some related results in the literature. Finally, we provide numerical experiments to illustrate the performance of the proposed algorithm. PubDate: 2021-04-22
Abstract: The paper is mainly devoted to the theory of duality of boundary value problems (BVPs) for differential inclusions of higher orders. For this, on the basis of the apparatus of locally conjugate mappings in the form of Euler–Lagrange-type inclusions and transversality conditions, sufficient optimality conditions are obtained. Wherein remarkable is the fact that inclusions of Euler–Lagrange type for prime and dual problems are “duality relations”. To demonstrate this approach, the optimization of some third-order semilinear BVPs and polyhedral fourth-order BVPs is considered. These problems show that sufficient conditions and dual problems can be easily established for problems of any order. PubDate: 2021-04-22
Abstract: This paper presents an approach to shortest path minimization for graphs with random weights of arcs. To deal with uncertainty we use the following risk measures: Probability of Exceedance (POE), Buffered Probability of Exceedance (bPOE), Value-at-Risk (VaR), and Conditional Value-at-Risk (CVaR). Minimization problems with POE and VaR objectives result in mixed integer linear problems (MILP) with two types of binary variables. The first type models path, and the second type calculates POE and VaR functions. Formulations with bPOE and CVaR objectives have only the first type binary variables. The bPOE and CVaR minimization problems have a smaller number of binary variables and therefore can be solved faster than problems with POE or VaR objectives. The paper suggested a heuristic algorithm for minimizing bPOE by solving several CVaR minimization problems. Case study (posted at web) numerically compares optimization times with considered risk functions. PubDate: 2021-04-20
Abstract: Using a dual method for solving linear fractional programming problems, we propose an approach to find optimal solutions of linear countable semi-infinite fractional programming problems via optimizing sequences. Duality theorems are established. A dual scheme for solving linear countable semi-infinite fractional problems is proposed. Examples are provided. PubDate: 2021-04-18
Abstract: In a recent paper, Bauschke et al. study \(\rho \) -comonotonicity as a generalized notion of monotonicity of set-valued operators A in Hilbert space and characterize this condition on A in terms of the averagedness of its resolvent \(J_A.\) In this note we show that this result makes it possible to adapt many proofs of properties of the proximal point algorithm PPA and its strongly convergent Halpern-type variant HPPA to this more general class of operators. This also applies to quantitative results on the rates of convergence or metastability (in the sense of T. Tao). E.g. using this approach we get a simple proof for the convergence of the PPA in the boundedly compact case for \(\rho \) -comonotone operators and obtain an effective rate of metastability. If A has a modulus of regularity w.r.t. \(zer\, A\) we also get a rate of convergence to some zero of A even without any compactness assumption. We also study a Halpern-type variant HPPA of the PPA for \(\rho \) -comonotone operators, prove its strong convergence (without any compactness or regularity assumption) and give a rate of metastability. PubDate: 2021-04-16
Abstract: We propose a cut-based algorithm for finding all vertices and all facets of the convex hull of all integer points of a polyhedron defined by a system of linear inequalities. Our algorithm, DDMCuts, is based on the Gomory cuts and the dynamic version of the double description method. We describe the computer implementation of the algorithm and present the results of computational experiments comparing our algorithm with a naive one and an algorithm implemented in Normaliz. PubDate: 2021-04-15
Abstract: We consider scheduling problems such that the due date is assigned to a job, depending on its position, and the intervals between consecutive due dates are identical. The objective is to minimize the weighted number of tardy jobs or the total weighted tardiness. Both two-machine flow shop and single-machine cases are considered. We establish the computational complexity of each case, based on the relationship with the scheduling problem with a common due date. PubDate: 2021-04-15
Abstract: Misinformation detection in Online Social Networks has recently become a critical topic due to its important role in restraining misinformation. Recent studies have showed that machine learning methods can be used to detect misinformation/fake news/rumors by detecting user’s behaviour. However, we can not implement this strategy for all users on a social network due to the limitation of budget. Therefore, it is critical to optimize the monitor/sensor placement to effectively detect misinformation. In this paper, we investigate Minimum Budget for Misinformation Detection problem which aims to find the smallest set of nodes to place monitors in a social network so that detection function is at least a given threshold. Beside showing the inapproximability of the problem under the well-known Independent Cascade diffusion model, we then propose three approximation algorithms including: Greedy, Sampling-based Misinformation Detection and Importance Sampling-based Misinformation Detection. Greedy is a deterministic approximation algorithm which utilizes the properties of monotone and submodular of the detection function. The rest is two randomized algorithms with provable guarantees based on developing two novel techniques (1) estimating detection function by using the concepts of influence sample and importance influence sample with proof of correctness, and (2) an algorithmic framework to select the solution with theoretical analysis. Experiments on real social networks show the effectiveness and scalability of our algorithms. PubDate: 2021-04-13
Abstract: In this paper we compare two new binary linear formulations to a standard quadratic binary program for the gray pattern problem and solved all three by the Gurobi solver. One formulation performed significantly better and obtained seven optimal solutions that were not proven optimal before. It is interesting that the formulation that performed best is based on significantly more variables and constraints. PubDate: 2021-04-13
Abstract: The constant rank constraint qualification, introduced by Janin in 1984 for nonlinear programming, has been extensively used for sensitivity analysis, global convergence of first- and second-order algorithms, and for computing the directional derivative of the value function. In this paper we discuss naive extensions of constant rank-type constraint qualifications to second-order cone programming and semidefinite programming, which are based on the Approximate-Karush–Kuhn–Tucker necessary optimality condition and on the application of the reduction approach. Our definitions are strictly weaker than Robinson’s constraint qualification, and an application to the global convergence of an augmented Lagrangian algorithm is obtained. PubDate: 2021-04-13
Abstract: The multiple obnoxious facilities location problem is an extremely non-convex optimization problem with millions of local optima. It is a very challenging problem. We improved the best known solution for 33 out of 76 test instances. We believe that the results of many instances reported here are still not optimal and thus better objective function values exist. We challenge the optimization community to design procedures that will further improve some of the results reported here. Optimality can be proven for a small number of new facilities. Proving optimality for a large number of facilities would be an achievement. PubDate: 2021-04-08
Abstract: In this paper, we focus on the problem of minimizing the sum of nonconvex smooth component functions and a nonsmooth weakly convex function composed with a linear operator. One specific application is logistic regression problems with weakly convex regularizers that introduce better sparsity than the standard convex regularizers. Based on the Moreau envelope with a decreasing sequence of smoothing parameters as well as incremental aggregated gradient method, we propose a variable smoothing incremental aggregated gradient (VS-IAG) algorithm. We also prove a complexity of \({\mathcal {O}}(\epsilon ^{-3})\) to achieve an \(\epsilon \) -approximate solution. PubDate: 2021-04-07
Abstract: This paper considers a general convex constrained problem setting where functions are not assumed to be differentiable nor Lipschitz continuous. Our motivation is in finding a simple first-order method for solving a wide range of convex optimization problems with minimal requirements. We study the method of weighted dual averages (Nesterov in Math Programm 120(1): 221–259, 2009) in this setting and prove that it is an optimal method. PubDate: 2021-04-05
Abstract: This paper aims at providing further studies of the notion of quasi-relative interior for convex sets. We obtain new formulas for representing quasi-relative interiors of convex graphs of set-valued mappings and for convex epigraphs of extended-real-valued functions defined on locally convex topological vector spaces. We also show that the role, which this notion plays in infinite dimensions and the results obtained in this vein, are similar to those involving relative interior in finite-dimensional spaces. PubDate: 2021-04-01
Abstract: This paper deals with the proximal point algorithm for finding a singularity of sum of a single-valued vector field and a set-valued vector field in the setting of Hadamard manifolds. The convergence analysis of the proposed algorithm is discussed. Applications to composite minimization problems and variational inequality problems are also presented. PubDate: 2021-04-01
Abstract: A local minimum of a quasiconvex function is not necessarily a global minimum. In this paper, we show that every lower semicontinuous quasiconvex function can be approximated uniformly by a sequence of quasiconvex functions for which every local minimum is a global minimum. We also study the continuity of the functions appearing in a recently obtained decomposition of quasiconvex functions. PubDate: 2021-04-01
Hybrid journal (It can contain Open Access articles)
