Transportation discrete network design problem (DNDP) is about how to modify an existing network of roads and highways in order to improve its total system travel time, and the candidate road building or expansion plan can only be added as a whole. DNDP can be formulated into a bi-level problem with binary variables. An active set algorithm has been proposed to solve the bi-level discrete network design problem, while it made an assumption that the capacity increase and construction cost of each road are based on the number of lanes. This paper considers a more general case when the capacity increase and construction cost are specified for each candidate plan. This paper also uses numerical methods instead of solvers to solve each step, so it provides a more direct understanding and control of the algorithm and running procedure. By analyzing the differences and getting corresponding solving methods, a modified active set algorithm is proposed in the paper. In the implementation of the algorithm and the validation, we use binary numeral system and ternary numeral system to avoid too many layers of loop and save storage space. Numerical experiments show the correctness and efficiency of the proposed modified active set algorithm.
In this paper we propose a method for solving systems of nonlinear inequalities with predefined accuracy based on nonuniform covering concept formerly adopted for global optimization. The method generates inner and outer approximations of the solution set. We describe the general concept and three ways of numerical implementation of the method. The first one is applicable only in a few cases when a minimum and a maximum of the constraints convolution function can be found analytically. The second implementation uses a global optimization method to find extrema of the constraints convolution function numerically. The third one is based on extrema approximation with Lipschitz under- and overestimations. We obtain theoretical bounds on the complexity and the accuracy of the generated approximations as well as compare proposed approaches theoretically and experimentally.
The currently adopted notion of a tolerance in combinatorial optimization is defined referring to an arbitrarily chosen optimal solution, i.e., locally. In this paper we introduce global tolerances with respect to the set of all optimal solutions, and show that the assumption of nonembededdness of the set of feasible solutions in the provided relations between the extremal values of upper and lower global tolerances can be relaxed. The equality between globally and locally defined tolerances provides a new criterion for the multiplicity (uniqueness) of the set of optimal solutions to the problem under consideration.
We consider a class of nonlinear integer optimization problems commonly known as fractional 0–1 programming problems (also, often referred to as hyperbolic 0–1 programming problems), where the objective is to optimize the sum of ratios of affine functions subject to a set of linear constraints. Such problems arise in diverse applications across different fields, and have been the subject of study in a number of papers during the past few decades. In this survey we overview the literature on fractional 0–1 programs including their applications, related computational complexity issues and solution methods including exact, approximation and heuristic algorithms.
The inverse max ++ sum spanning tree (MSST) problem is considered by modifying the sum-cost vector under the Hamming Distance. On an undirected network G(V, E, w, c), a weight w(e) and a cost c(e) are prescribed for each edge e∈Ee∈E. The MSST problem is to find a spanning tree T∗T∗ which makes the combined weight maxe∈Tw(e)+∑e∈Tc(e)maxe∈Tw(e)+∑e∈Tc(e) as small as possible. It can be solved in O(mlogn)O(mlogn) time, where m:=|E|m:=|E| and n:=|V|n:=|V|. Whereas, in an inverse MSST problem, a given spanning tree T0T0 of G is not an optimal MSST. The sum-cost vector c is to be modified to c¯c¯ so that T0T0 becomes an optimal MSST of the new network G(V,E,w,c¯)G(V,E,w,c¯) and the cost ∥c¯−c∥‖c¯−c‖ can be minimized under Hamming Distance. First, we present a mathematical model for the inverse MSST problem and a method to check the feasibility. Then, under the weighted bottleneck-type Hamming distance, we design a binary search algorithm whose time complexity is O(mlog2n)O(mlog2n). Next, under the unit sum-type Hamming distance, which is also called l0l0 norm, we show that the inverse MSST problem (denoted by IMSST00) is NP−NP−hard. Assuming NP⊈DTIME(mpolylogm)NP⊈DTIME(mpolylogm), the problem IMSST00 is not approximable within a factor of 2log1−εm2log1−εm, for any ε>0ε>0. Finally, We consider the augmented problem of IMSST00 (denoted by AIMSST00), whose objective function is to multiply the l0l0 norm ∥β∥0‖β‖0 by a sufficiently large number M plus the l1l1 norm ∥β∥1‖β‖1. We show that the augmented problem and the l1l1 norm problem have the same Lagrange dual problems. Therefore, the l1l1 norm problem is the best convex relaxation (in terms of Lagrangian duality) of the augmented problem AIMSST00, which has the same optimal solution as that of the inverse problem IMSST00.
A sensor with two active phases means that active mode has two phases, the full-active phase and the semi-active phase, which require different energy consumptions. A full-active sensor can sense data packets, transmit, receive, and relay the data packets. A semi-active sensor cannot sense data packets, but it can transmit, receive, and relay data packets. Given a set of targets and a set of sensors with two active phases, find a sleep/active schedule of sensors to maximize the time period during which active sensors form a connected coverage set. In this paper, this problem is showed to have polynomial-time (7.875+ε) -approximations for any ε>0 when all targets and sensors lie in the Euclidean plane and all sensors have the same sensing radius R s and the same communication radius R c with R c ≥ 2R s .
Various Condorcet consistent social choice functions based on majority rule (tournament solutions) are considered in the general case, when ties are allowed: the core, the weak and strong top cycle sets, versions of the uncovered and minimal weakly stable sets, the uncaptured set, the untrapped set, classes of k-stable alternatives and k-stable sets. The main focus of the paper is to construct a unified matrix-vector representation of a tournament solution in order to get a convenient algorithm for its calculation. New versions of some solutions are also proposed.
In this paper, we consider the class of quasiconvex functions and its proper subclass of conic functions. The integer minimization problem of these functions is considered, assuming that the optimized function is defined by the comparison oracle. We will show that there is no a polynomial algorithm on log R to optimize quasiconvex functions in the ball of radius R using only the comparison oracle. On the other hand, if the optimized function is conic, then we show that there is a polynomial on log R algorithm (the dimension is fixed). We also present an exponential on the dimension lower bound for the oracle complexity of the conic function integer optimization problem. Additionally, we give examples of known problems that can be polynomially reduced to the minimization problem of functions in our classes.
The earliest approaches to the cell formation problem in group technology, dealing with a binary machine-part incidence matrix, were aimed only at minimizing the number of intercell moves (exceptional elements in the block-diagonalized matrix). Later on this goal was extended to simultaneous minimization of the numbers of exceptions and voids, and minimization of intercell moves and within-cell load variation, respectively. In this paper we design the first exact branch-and-bound algorithm to create a Pareto-optimal front for the bi-criterion cell formation problem.
In this paper we consider two branch and bound algorithms for the maximum clique problem which demonstrate the best performance on DIMACS instances among the existing methods. These algorithms are MCS algorithm by Tomita et al. (2010) and MAXSAT algorithm by Li and Quan (2010a, b). We suggest a general approach which allows us to speed up considerably these branch and bound algorithms on hard instances. The idea is to apply a powerful heuristic for obtaining an initial solution of high quality. This solution is then used to prune branches in the main branch and bound algorithm. For this purpose we apply ILS heuristic by Andrade et al. (2012). The best results are obtained for p_hat1000-3 instance and gen instances with up to 11,000 times speedup.
The tolerance of an element of a combinatorial optimization problem with respect to its optimal solution is the maximum change of the cost of the element while preserving the optimality of the given optimal solution and keeping all other input data unchanged. Tolerances play an important role in the design of exact and approximation algorithms, but the computation of tolerances requires additional computational time. In this paper, we concentrate on combinatorial optimization problems for which the computation of all tolerances and an optimal solution have almost the same computational complexity as of finding an optimal solution only. We summarize efficient computational methods for computing tolerances for these problems and determine their time complexity experimentally.