-
作者：Anderson, Ross; Huchette, Joey; Ma, Will; Tjandraatmadja, Christian; Vielma, Juan Pablo
作者单位：Alphabet Inc.; Google Incorporated; Rice University; Columbia University; Massachusetts Institute of Technology (MIT)
摘要：We present strong mixed-integer programming (MIP) formulations for high-dimensional piecewise linear functions that correspond to trained neural networks. These formulations can be used for a number of important tasks, such as verifying that an image classification network is robust to adversarial inputs, or solving decision problems where the objective function is a machine learning model. We present a generic framework, which may be of independent interest, that provides a way to construct s...
-
作者：Cornuejols, Gerard; Lee, Dabeen; Li, Yanjun
作者单位：Carnegie Mellon University; Purdue University System; Purdue University
摘要：We study the following problem: given a rational polytope with Chvatal rank 1, does it contain an integer point? Boyd and Pulleyblank observed that this problem is in the complexity class NP boolean AND\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\cap $$\end{document} co-NP, an indication that it is probably not...
-
作者：Buchbinder, Niv; Feldman, Moran; Filmus, Yuval; Garg, Mohit
作者单位：Tel Aviv University; Open University Israel; Technion Israel Institute of Technology; University of Haifa; Universita della Svizzera Italiana
摘要：The Submodular Welfare Maximization problem (SWM) captures an important subclass of combinatorial auctions and has been studied extensively. In particular, it has been studied in a natural online setting in which items arrive one-by-one and should be allocated irrevocably upon arrival. For this setting, Korula et al. (SIAM J Comput 47(3):1056-1086, 2018) were able to show that the greedy algorithm is 0.5052-competitive when the items arrive in a uniformly random order. Unfortunately, however, ...
-
作者：Yang, Wenzhuo; Sim, Melvyn; Xu, Huan
作者单位：National University of Singapore; National University of Singapore; University System of Georgia; Georgia Institute of Technology
摘要：Motivated by the binary classification problem in machine learning, we study in this paper a class of decision problems where the decision maker has a list of goals, from which he aims to attain the maximal possible number of goals. In binary classification, this essentially means seeking a prediction rule to achieve the lowest probability of misclassification, and computationally it involves minimizing a (difficult) non-convex, 0-1 loss function. To address the intractability, previous method...
-
作者：Kronqvist, Jan; Bernal, David E.; Grossmann, Ignacio E.
作者单位：Abo Akademi University; Carnegie Mellon University
摘要：In this paper, we present two new methods for solving convex mixed-integer nonlinear programming problems based on the outer approximation method. The first method is inspired by the level method and uses a regularization technique to reduce the step size when choosing new integer combinations. The second method combines ideas from both the level method and the sequential quadratic programming technique and uses a second order approximation of the Lagrangean when choosing the new integer combi...
-
作者：Kroer, Christian; Waugh, Kevin; Kilinc-Karzan, Fatma; Sandholm, Tuomas
作者单位：Carnegie Mellon University; University of Alberta; Carnegie Mellon University
摘要：Sparse iterative methods, in particular first-order methods, are known to be among the most effective in solving large-scale two-player zero-sum extensive-form games. The convergence rates of these methods depend heavily on the properties of the distance-generating function that they are based on. We investigate both the theoretical and practical performance improvement of first-order methods (FOMs) for solving extensive-form games through better design of the dilated entropy function-a class ...
-
作者：Shen, Xiangkun; Nagarajan, Viswanath
作者单位：University of Michigan System; University of Michigan
摘要：We consider fractional online covering problems withlq-norm objectives as well as its dual packing problems. The problem of interest is of the formmin{f(x):Ax >= 1,x >= 0}wheref(x)= n-ary sumation ece||x(Se)||qeis the weighted sum oflq-norms andAis a non-negative matrix. The rows ofA(i.e. covering constraints) arrive online over time. We provide an onlineO(logd+log rho)-competitive algorithm where rho=amaxaminanddis the maximum of the row sparsity ofAandmax|Se|This is based on the online prima...
-
作者：Berczi, Kristof; Chandrasekaran, Karthekeyan; Kiraly, Tamas; Madan, Vivek
作者单位：Eotvos Lorand University; University of Illinois System; University of Illinois Urbana-Champaign; University System of Georgia; Georgia Institute of Technology
摘要：In the multiway cut problem, we are given an undirected graph with non-negative edge weights and a collection of k terminal nodes, and the goal is to partition the node set of the graph into k non-empty parts each containing exactly one terminal, so that the total weight of the edges crossing the partition is minimized. The multiway cut problem for k >= 3 is APX-hard. For arbitrary k, the best-known approximation factor is 1.2965 due to Sharma and Vondrak (Proceedings of the forty-sixth annual...
-
作者：Li, Xudong; Sun, Defeng; Toh, Kim-Chuan
作者单位：Fudan University; Hong Kong Polytechnic University; National University of Singapore; National University of Singapore
摘要：We derive an explicit formula, as well as an efficient procedure, for constructing a generalized Jacobian for the projector of a given square matrix onto the Birkhoff polytope, i.e., the set of doubly stochastic matrices. To guarantee the high efficiency of our procedure, a semismooth Newton method for solving the dual of the projection problem is proposed and efficiently implemented. Extensive numerical experiments are presented to demonstrate the merits and effectiveness of our method by com...
-
作者：Koh, Zhuan Khye; Sanita, Laura
作者单位：University of London; London School Economics & Political Science; University of Waterloo; Eindhoven University of Technology
摘要：Cooperative games form an important class of problems in game theory, where a key goal is to distribute a value among a set of players who are allowed to cooperate by forming coalitions. An outcome of the game is given by an allocation vector that assigns a value share to each player. A crucial aspect of such games is submodularity (or convexity). Indeed, convex instances of cooperative games exhibit several nice properties, e.g. regarding the existence and computation of allocations realizing...
