-
作者：Kimura, Kei; Nakayama, Kotaro
作者单位：Kyushu University
摘要：For an integer linear optimization (ILO) problem, persistency of its linear optimization (LO) relaxation is a property that for every optimal solution of the relaxation that assigns integer values to some variables, there exists an optimal solution of the ILO problem in which these variables retain the same values. Although persistency has been used to develop heuristic, approximation, and fixed-parameter algorithms for special cases of ILO, its applicability remains unknown in the literature....
-
作者：Bui, Quang Minh; Carvalho, Margarida; Neto, Jose
作者单位：Universite de Montreal; Universite de Montreal; IMT - Institut Mines-Telecom; Institut Polytechnique de Paris; Telecom SudParis
摘要：The network pricing problem (NPP) is a bilevel problem, where the leader optimizes its revenue by deciding on the prices of certain arcs in a graph, while expecting the followers (also known as the commodities) to choose a shortest path based on those prices. In this paper, we investigate the complexity of the NPP with respect to two parameters: the number of tolled arcs, and the number of commodities. We devise a simple algorithm showing that if the number of tolled arcs is fixed, then the pr...
-
作者：Grimmer, Benjamin
作者单位：Johns Hopkins University
摘要：Renegar (SIAM J Optim 26(4):2649-2676, https://doi.org/10.1137/15M1027371 2016) introduced a novel approach to transforming generic conic optimization problems into unconstrained, uniformly Lipschitz continuous minimization. We introduce radial transformations generalizing these ideas, equipped with an entirely new motivation and development that avoids any reliance on convex cones or functions. Of practical importance, this facilitates the development of new families of projection-free first-...
-
作者：Behling, Roger; Bello-Cruz, Yunier; Iusem, Alfredo N. N.; Santos, Luiz-Rafael
作者单位：Getulio Vargas Foundation; Northern Illinois University; Universidade Federal de Santa Catarina (UFSC)
摘要：This paper is devoted to deriving the first circumcenter iteration scheme that does not employ a product space reformulation for finding a point in the intersection of two closed convex sets. We introduce a so-called centralized version of the circumcentered-reflection method (CRM). Developed with the aim of accelerating classical projection algorithms, CRM is successful for tracking a common point of a finite number of affine sets. In the case of general convex sets, CRM was shown to possibly...
-
作者：Smeulders, B.; Blom, D. A. M. P.; Spieksma, F. C. R.
作者单位：Eindhoven University of Technology
摘要：In Kidney Exchange Games, agents (e.g. hospitals or national organizations) have control over a number of incompatible recipient-donor pairs whose recipients are in need of a transplant. Each agent has the opportunity to join a collaborative effort which aims to maximize the total number of transplants that can be realized. However, the individual agent is only interested in maximizing the number of transplants within the set of recipients under its control. Then, the question becomes: which r...
-
作者：Balinski, Michel; Ramirez, Victoriano
作者单位：Institut Polytechnique de Paris; Ecole Polytechnique; Centre National de la Recherche Scientifique (CNRS); University of Granada
摘要：Several different arguments support the use of Webster's method when seats in a parliament are to be apportioned proportionally according to populations. This note-instigated by a new property-summarizes the reasons.
-
作者：Gonzalez-Rodriguez, Brais; Froger, Aurelien; Jabali, Ola; Naoum-Sawaya, Joe
作者单位：Western University (University of Western Ontario); Centre National de la Recherche Scientifique (CNRS); CNRS - National Institute for Mathematical Sciences (INSMI); Universite de Bordeaux; Inria; Polytechnic University of Milan; Universite de Montreal; HEC Montreal
摘要：Establishing the size of an EV fleet is a vital decision for logistics operators. In urban settings, this issue is often dealt with by partitioning the geographical area around a depot into service zones, each served by a single vehicle. Such zones ultimately guide daily routing decisions. We study the problem of determining the optimal partitioning of an urban logistics area served by EVs. We cast this problem in a Continuous Approximation (CA) framework. Considering a ring radial region with...
-
作者：Cela, Eranda; Klinz, Bettina; Lendl, Stefan; Woeginger, Gerhard J.; Wulf, Lasse
作者单位：Graz University of Technology; University of Graz; RWTH Aachen University
摘要：An instance of the NP-hard Quadratic Shortest Path Problem (QSPP) is called linearizable iff it is equivalent to an instance of the classic Shortest Path Problem (SPP) on the same input digraph. The linearization problem for the QSPP (LinQSPP) decides whether a given QSPP instance is linearizable and determines the corresponding SPP instance in the positive case. We provide a novel linear time algorithm for the LinQSPP on acyclic digraphs which runs considerably faster than the previously best...
-
作者：Ahookhosh, Masoud; Nesterov, Yurii
作者单位：University of Antwerp
摘要：We introduce a Bi-level OPTimization (BiOPT) framework for minimizing the sum of two convex functions, where one of them is smooth enough. The BiOPT framework offers three levels of freedom: (i) choosing the order p of the proximal term; (ii) designing an inexact pth-order proximal-point method in the upper level; (iii) solving the auxiliary problem with a lower-level non-Euclidean method in the lower level. We here regularize the objective by a (p+1)\documentclass[12pt]{minimal} \usepackage{a...
-
作者：Abdi, Ahmad; Cornuejols, Gerard; Guenin, Bertrand; Tuncel, Levent
作者单位：University of London; London School Economics & Political Science; Carnegie Mellon University; University of Waterloo
摘要：A vector is dyadic if each of its entries is a dyadic rational number, i.e. of the form (a)/(2)k for some integers a, k with k = 0. A linear system Ax = b with integral data is totally dual dyadic if whenever min{b(T)y : A(T)y = w, y = 0J for w integral, has an optimal solution, it has a dyadic optimal solution. In this paper, we study total dual dyadicness, and give a co-NP characterization of it in terms of dyadic generating sets for cones and subspaces, the former being the dyadic analogue ...
