作者：
Gupta, SamarthAmin, SaurabhMIT
Ctr Computat Sci & Engn Cambridge MA 02139 USA MIT
Lab Informat & Decis Syst Cambridge MA 02139 USA
Error-Correcting Output Codes (ECOCs) offer a principled approach for combining binary classifiers into multiclass classifiers. In this paper, we study the problem of designing optimal ECOCs to achieve both nominal an...
详细信息
Error-Correcting Output Codes (ECOCs) offer a principled approach for combining binary classifiers into multiclass classifiers. In this paper, we study the problem of designing optimal ECOCs to achieve both nominal and adversarial accuracy using Support Vector Machines (SVMs) and binary deep neural networks. We develop a scalable integer programming (IP) formulation to design minimal codebooks with desirable error correcting properties. Our work leverages the advances in IP solution techniques to generate codebooks with optimality guarantees. To achieve tractability, we exploit the underlying graph-theoretic structure of the constraint set. Particularly, the size of the constraint set can be significantly reduced using edge clique covers. Using this reduction technique along with Plotkin's bound in coding theory, we demonstrate that our approach is scalable to a large number of classes. The resulting codebooks achieve a high nominal accuracy relative to standard codebooks (e.g., one-vs-all, one-vs-one, and dense/sparse codes). Interestingly, our codebooks provide non-trivial robustness to white-box attacks without any adversarial training.
The problem of finding an ancestral acyclic directed mixed graph (ADMG) that represents the causal relationships between a set of variables is an important area of research on causal inference. Most existing score-bas...
详细信息
ISBN:
(纸本)9781713845065
The problem of finding an ancestral acyclic directed mixed graph (ADMG) that represents the causal relationships between a set of variables is an important area of research on causal inference. Most existing score-based structure learning methods focus on learning directed acyclic graph (DAG) models without latent variables. A number of score-based methods have recently been proposed for the ADMG learning, yet they are heuristic in nature and do not guarantee an optimal solution. We propose a novel exact score-based method that solves an integer programming (IP) formulation and returns a score-maximizing ancestral ADMG for a set of continuous variables that follow a multivariate Gaussian distribution. We generalize the state-of-the-art IP model for DAG learning problems and derive new classes of valid inequalities to formulate an IP model for ADMG learning. Empirically, our model can be solved efficiently for medium-sized problems and achieves better accuracy than state-of-the-art score-based methods as well as benchmark constraint-based methods.
In this tutorial, we present a computational overview on computing Nash equilibria in integer programming Games (IPGs), i.e., how to compute solutions for a class of non-cooperative and non-convex games where each pla...
详细信息
In this paper, we further study the concepts of hop domination and 2-step domination and introduce the concepts of restrained hop domination, total restrained hop domination, 2-step restrained domination, and total 2-...
详细信息
This thesis exhibits a collection of combinatorial optimization problems and the integer programs proposed to solve them based on new mathematical insights. In particular, graph propagation and graph throttling proble...
详细信息
This thesis exhibits a collection of combinatorial optimization problems and the integer programs proposed to solve them based on new mathematical insights. In particular, graph propagation and graph throttling problems including the positive semidefinite zero forcing set problem and the minimum power dominating set problem are considered, as well as the graph connectivity problem known as the strong rainbow connection problem. A parallel treatment of the graph propagation problems is provided in which set cover problems are defined using problem specific blocking sets. These blocking sets are introduced, their structural properties are investigated, and computational methods for identifying them are proposed, providing a general recipe for developing integer programming approaches for graph propagation problems. The strong rainbow connection problem is also studied, and the first general computational method for the problem is introduced. New lower bounds, computational enhancements, and an alternative solution method based on iterative lower bound improvement are also proposed, the latter of which is shown to be highly effective in practice.
Objective-space decomposition algorithms (ODAs) are widely studied for solving multi-objective integer programs. However, they often encounter difficulties in handling scalarized problems, which could cause infeasibil...
详细信息
ISBN:
(纸本)9781713871088
Objective-space decomposition algorithms (ODAs) are widely studied for solving multi-objective integer programs. However, they often encounter difficulties in handling scalarized problems, which could cause infeasibility or repetitive non-dominated points and thus induce redundant runtime. To mitigate the issue, we present a graph neural network (GNN) based method to learn the reduction rule in the ODA. We formulate the algorithmic procedure of generic ODAs as a Markov decision process, and parameterize the policy (reduction rule) with a novel two-stage GNN to fuse information from variables, constraints and especially objectives for better state representation. We train our model with imitation learning and deploy it on a state-of-the-art ODA. Results show that our method significantly improves the solving efficiency of the ODA. The learned policy generalizes fairly well to larger problems or more objectives, and the proposed GNN outperforms existing ones for integer programming in terms of test and generalization accuracy.
The kidney exchange problem (KEP) seeks to determine a constellation of exchanges that maximizes the number of possible transplants between a set of patients and their incompatible donors. Recently, Secure Multi-Party...
详细信息
ISBN:
(数字)9781665473989
ISBN:
(纸本)9781665473989
The kidney exchange problem (KEP) seeks to determine a constellation of exchanges that maximizes the number of possible transplants between a set of patients and their incompatible donors. Recently, Secure Multi-Party Computation (SMPC) techniques were used to devise privacy-preserving protocols that allow the solving of the KEP in a distributed fashion. However, these protocols lack sufficient performance in practice. In the non-privacy-preserving case, the most efficient algorithms solving the KEP are based on integer programming. It is in this context, that we propose a privacy-preserving protocol based on these integer programming techniques that efficiently solves the KEP in a privacy-preserving fashion. We prove the security of this protocol and analyze its complexity. Furthermore, we provide a comprehensive performance evaluation of an implementation of the protocol in the SMPC benchmarking framework MP-SPDZ.
Military academy cadets reside in a brigade organized by cadets. Despite its importance, squads have traditionally been organized based on the personal preferences of the fourth-year squad leader without considering t...
详细信息
Military academy cadets reside in a brigade organized by cadets. Despite its importance, squads have traditionally been organized based on the personal preferences of the fourth-year squad leader without considering the compatibility of the squad members. This study proposes a more scientific approach to increase cadet satisfaction with their squads and foster their leadership development. Initially, a multiple linear regression analysis was conducted to identify the leadership factors of squad leaders that significantly affect squad organizational satisfaction. The model maximized the sum of the factor scores among squad leaders to enhance squad organizational satisfaction and maximized the difference in factor scores to improve the effectiveness of leadership discipline. Applying the squad formation algorithm to data from cadets at the Korea Military Academy revealed that the squad organizational satisfaction and leadership discipline effectiveness were significantly increased compared to the existing squad formation methods.
For robots to successfully execute tasks assigned to them, they must be capable of planning the right sequence of actions. These actions must be both optimal with respect to a specified objective and satisfy whatever ...
详细信息
ISBN:
(数字)9781665479271
ISBN:
(纸本)9781665479271
For robots to successfully execute tasks assigned to them, they must be capable of planning the right sequence of actions. These actions must be both optimal with respect to a specified objective and satisfy whatever constraints exist in their world. We propose an approach for robot task planning that is capable of planning the optimal sequence of grounded actions to accomplish a task given a specific objective function while satisfying all specified numerical constraints. Our approach accomplishes this by encoding the entire task planning problem as a single mixed integer convex program, which it then solves using an off-the-shelf Mixed integer programming solver. We evaluate our approach on several mobile manipulation tasks in both simulation and on a physical humanoid robot. Our approach is able to consistently produce optimal plans while accounting for all specified numerical constraints in the mobile manipulation tasks. Open-source implementations of the components of our approach as well as videos of robots executing planned grounded actions in both simulation and the physical world can be found at this url: https://***/gtpmip
We show that a circuit walk from a given feasible point of a given linear program to an optimal point can be computed in polynomial time using only linear algebra operations and the solution of the single given linear...
详细信息
We show that a circuit walk from a given feasible point of a given linear program to an optimal point can be computed in polynomial time using only linear algebra operations and the solution of the single given linear program. We also show that a Graver walk from a given feasible point of a given integer program to an optimal point is polynomial time computable using an integer programming oracle, but without such an oracle, it is hard to compute such a walk even if an optimal solution to the given program is given as well. Combining our oracle algorithm with recent results on sparse integer programming, we also show that Graver walks from any point are polynomial time computable over matrices of bounded tree-depth and subdeterminants.
暂无评论