Search

In this study, we present a general framework of outer approximation algorithms to solve convex vector optimization problems, in which the Pascoletti-Serafini (PS) scalarization is solved iteratively. This scalarization finds the minimum 'distance' from a reference point, which is usually taken as a vertex of the current outer approximation, to the upper image through a given direction. We propose efficient methods to select the parameters (the reference point and direction vector) of the PS scalarization and analyse the effects of these on the overall performance of the algorithm. Different from the existing vertex selection rules from the literature, the proposed methods do not require solving additional single-objective optimization problems. Using some test problems, we conduct an extensive computational study where three different measures are set as the stopping criteria: the approximation error, the runtime, and the cardinality of the solution set. We observe that the proposed variants have satisfactory results, especially in terms of runtime compared to the existing variants from the literature. [ABSTRACT FROM AUTHOR]

In this paper, we propose a novel dual active-set algorithm that is based on proximal gradient and semi-smooth Newton iterations for the sparse approximation of correlation matrices in the Frobenius norm. A new dual formulation with upper and lower bounds is derived. To solve the dual, the proximal gradient method is developed to guarantee global convergence. Also, it provides information to estimate active/inactive constraints. Then, the semi-smooth Newton method is applied to accelerate the convergence of the proximal gradient method, which is the key ingredient of our algorithm. It is shown that the proposed algorithm for the dual is globally convergent under certain conditions. Some preliminary numerical results are given to illustrate the effectiveness of our algorithm on synthetic and real data sets. [ABSTRACT FROM AUTHOR]

For a graph G = (V , E) , a double Roman dominating function (DRDF) is a function f : V → { 0 , 1 , 2 , 3 } having the property that if f (v) = 0 , then vertex v must have at least two neighbours assigned 2 under f or at least one neighbour u with f (u) = 3 , and if f (v) = 1 , then vertex v must have at least one neighbour u with f (u) ≥ 2. In this paper, we consider the double Roman domination problem, which is an optimization problem of finding the DRDF f such that ∑ v ∈ V f (v) is minimum. We propose five integer linear programming (ILP) formulations and one mixed integer linear programming formulation with polynomial number of constraints for this problem. Some additional valid inequalities and bounds are also proposed for some of these formulations. Further, we prove that the first four models indeed solve the double Roman domination problem, and the last two models are equivalent to the others regardless of the variable relaxation or usage of a smaller number of constraints and variables. Additionally, we use one ILP formulation to give an H (2 (Δ + 1)) -approximation algorithm. All proposed formulations and approximation algorithm are evaluated on randomly generated graphs to compare the performance. [ABSTRACT FROM AUTHOR]

We consider two-machine routing open shop problem on a tree. In this problem, a transportation network with a tree-like structure is given, and each node contains some jobs to be processed by two mobile machines. Machines are initially located in the predefined node called the depot, have to traverse the network to perform their operations on each job (and each job has to be processed by both machines in arbitrary order), and machines have to return to the depot after performing all the operations. The goal is to construct a feasible schedule for machines to process all the jobs and to return to the depot in shortest time possible. This problem is known to be NP-hard even in the case when the transportation network consists of just two nodes. We propose an instance reduction procedure which allows to transform any instance of the problem to a simplified instance on a chain with limited number of jobs. The reduction considered preserves the standard lower bound on the optimum. We describe four possible outcomes of this procedure and prove that in three of them the initial instance can be solved to the optimum in linear time, thus introducing a wide polynomially solvable subclass of the problem considered. Our research can be used as a foundation to construct efficient approximation algorithms for the two-machine routing open shop on a tree. [ABSTRACT FROM AUTHOR]

We consider a conflict-free minimum latency data aggregation problem that occurs in different wireless networks. Given a network that is presented as an undirected graph with one selected vertex (a sink), the goal is to find a spanning aggregation tree rooted in the sink and to define a conflict-free aggregation minimum length schedule along the arcs of the tree directed to the sink. Herewith, at the same time slot, each element of the network can either send or receive at most one message. Only one message should be sent by each network element during the whole aggregation session, and the conflicts caused by signal interference should be excluded. This problem is NP-hard and remains NP-hard even in the case when the aggregation tree is given. Therefore, the development of efficient approximation algorithms is very important for this problem. In this paper, we present new heuristic algorithms based on genetic local search and variable neighbourhood search metaheuristics. We conducted an extensive simulation that demonstrates the superiority of our algorithms compared with the best of the previous approaches. [ABSTRACT FROM AUTHOR]

This paper presents a generic framework for the design and comparison of polynomial-time approximation algorithms for MINIMUM STAR BICOLORING. This generic framework is parameterized by algorithms which produce sequences of distance- 2 independent sets. As our main technical result we show that, when the parameterized algorithm produces sequences of distance- 2 independent sets that remove at least Ω (n ϵ) edges during each step, the generic framework produces a polynomial-time approximation algorithm for MINIMUM STAR BICOLORING that is always at least O (n 1 − ϵ / (1 + ϵ) ) of optimal. Under the generic framework, we model two algorithms for MINIMUM STAR BICOLORING from the literature: Complete Direct Cover (CDC) [Hossain and Steihaug, Computing a sparse Jacobian matrix by rows and columns, Optim. Methods Softw. 10 (1998), pp. 33–48] and ASBC [Juedes and Jones, Coloring Jacobians revisited: A new algorithm for star and acyclic bicoloring, Optim. Methods Softw. 27(1–3) (2012), pp. 295–309]. We apply our main result to show approximation upper bounds of O (n 3 / 4) and O (n 2 / 3) , respectively, for these two algorithms. Our approximation upper bound for CDC is the first known approximation analysis for this algorithm. In addition to modelling CDC and ASBC, we use the generic framework to build and analyze three new O (n 2 / 3) approximation algorithms for MINIMUM STAR BICOLORING: MAX-NEIGHBORHOOD, MAX-RATIO c , and LOCAL-SEARCH-k. [ABSTRACT FROM AUTHOR]

In an application of map labelling to air-traffic control, labels should be placed with as few overlaps as possible since labels include important information about airplanes. Motivated by this application, de Berg and Gerrits (Comput. Geom. 2012) proposed a problem of maximizing the number of free labels (i.e. labels not intersecting with any other label) and developed approximation algorithms for their problem under various label-placement models. In this paper, we propose an alternative problem of minimizing a degree of overlap at a point. Specifically, the objective of this problem is to minimize the maximum of λ (p) over p ∈ R 2 , where λ (p) is defined as the sum of weights of labels that overlap with a point p. We develop a 4-approximation algorithm by LP-rounding under the 4-position model. We also investigate the case when labels are rectangles with bounded height/length ratios. [ABSTRACT FROM AUTHOR]

We present a method to solve constrained convex stochastic optimization problems when the objective is a finite sum of convex functions. Our method is based on Incremental Stochastic Subgradient Algorithms and String-Averaging techniques, with an assumption that the subgradient directions are affected by random errors in each iteration. Our analysis allows the method to perform approximate projections onto the feasible set in each iteration. We provide convergence results for the case where a diminishing step-size rule is used. We test our method in a large set of random instances of a stochastic convex programming problem and we compare its performance with the robust mirror descent stochastic approximation algorithm proposed in Nemirovski et al. (Robust stochastic approximation approach to stochastic programming, SIAM J Optim 19 (2009), pp. 15741609). [ABSTRACT FROM AUTHOR]

The clusterwise linear regression problem is formulated as a nonsmooth nonconvex optimization problem using the squared regression error function. The objective function in this problem is represented as a difference of convex functions. Optimality conditions are derived, and an algorithm is designed based on such a representation. An incremental approach is proposed to generate starting solutions. The algorithm is tested on small to large data sets. [ABSTRACT FROM AUTHOR]

We deal with a recently proposed method of Chubanov [A polynomial projection algorithm for linear feasibility problems. Math. Program. 153 (2015), pp. 687–713] for solving linear homogeneous systems with positive variables. Some improvements of Chubanov's method and its analysis are presented. We propose a new and simple cut criterion and show that the cuts defined by the new criterion are at least as sharp as in [1]. The new cut criterion reduces the iteration bound for his Basic Procedure by a factor 5, without changing the order of its strongly polynomial complexity. Our Modified Main Algorithm is in essence the same as Chubanov's Main Algorithm, except that it uses our Modified Basic Procedure as a subroutine. It is shown that it hastime complexity, just as in [1]. Some promising computational results are presented, in comparison with the optimization package Gurobi. [ABSTRACT FROM AUTHOR]

We describe general heuristics to approximately solve a wide variety of problems with convex objective and decision variables from a non-convex set. The heuristics, which employ convex relaxations, convex restrictions, local neighbour search methods, and the alternating direction method of multipliers, require the solution of a modest number of convex problems, and are meant to apply to general problems, without much tuning. We describe an implementation of these methods in a package called NCVX, as an extension of CVXPY, a Python package for formulating and solving convex optimization problems. We study several examples of well known non-convex problems, and show that our general purpose heuristics are effective in finding approximate solutions to a wide variety of problems. [ABSTRACT FROM AUTHOR]

Since the pioneering work by Dentcheva and Ruszczyński [Optimization with stochastic dominance constraints, SIAM J. Optim. 14 (2003), pp. 548–566], stochastic programs with second-order dominance constraints (SPSODC) have received extensive discussions over the past decade from theory of optimality to numerical schemes and practical applications. In this paper, we investigate discrete approximation of SPSODC when (a) the true probability is known but continuously distributed and (b) the true probability distribution is unknown but it lies within an ambiguity set of distributions. Differing from the well-known Monte Carlo discretization method, we propose a deterministic discrete approximation scheme due to Pflug and Pichler [Approximations for Probability Distributions and Stochastic Optimization Problems, International Series in Operations Research & Management Science, Vol. 163, Springer, New York, 2011, pp. 343–387] and demonstrate that the discrete probability measure and the ambiguity set of discrete probability measures approximate their continuous counterparts under the Kantorovich metric. Stability analysis of the optimal value and optimal solutions of the resulting discrete optimization problems is presented and some comparative numerical test results are reported. [ABSTRACT FROM AUTHOR]

In this paper we consider the two-stage stochastic linear assignment (2SSLA) problem, which is a stochastic extension of the classical deterministic linear assignment problem. For each agent and job, the decision maker has to decide whether to make assignments now or to wait for the second stage. Assignments of agents and jobs, for which decisions are delayed to the second stage, are then completed based on the scenario realized. We discuss two greedy approximation algorithms from the literature and derive a simple necessary optimality condition that generalizes the key ideas behind both of these approaches. Subsequently, based on this result we design a new greedy approximation method. Theoretical observations and the results of computational experiments are also presented. [ABSTRACT FROM AUTHOR]

This paper presents a new polynomial-time algorithm, approximate star bicoloring (ASBC), for star bicoloring and acyclic bicoloring. These NP-complete combinatorial problems arise from problems associated with computing large sparse Jacobian matrices. The main results of this paper lie in approximation analysis related to these problems. In particular, it is shown that (i) both star and acyclic bicoloring can be approximated in polynomial time to the ratio O(n 2/3) and (ii) both star and acyclic bicoloring cannot be approximated to the ratio O(n 1/3−ε) in polynomial time under reasonable complexity theoretic hypotheses. The ASBC algorithm is also analysed experimentally on a collection of realistic test cases from the Harwell–Boeing sparse matrix collection. The experimental results indicate that ASBC performs quite well in practice; the performance of the new algorithm always fell within the range of 1.53 and 6 times optimal on the given test sets. [ABSTRACT FROM AUTHOR]