Mixed Integer Programming for Searching Maximum Quasi-Bicliques

2020-02-23 · Dmitry I. Ignatov, Polina Ivanova, Albina Zamaletdinova

This paper is related to the problem of finding the maximal quasi-bicliques in a bipartite graph (bigraph). A quasi-biclique in the bigraph is its "almost" complete subgraph. The relaxation of completeness can be understood variously; here, we assume that the subgraph is a $\gamma$-quasi-biclique if it lacks a certain number of edges to form a biclique such that its density is at least $\gamma \in (0,1]$. For a bigraph and fixed $\gamma$, the problem of searching for the maximal quasi-biclique consists of finding a subset of vertices of the bigraph such that the induced subgraph is a quasi-biclique and its size is maximal for a given graph. Several models based on Mixed Integer Programming (MIP) to search for a quasi-biclique are proposed and tested for working efficiency. An alternative model inspired by biclustering is formulated and tested; this model simultaneously maximizes both the size of the quasi-biclique and its density, using the least-square criterion similar to the one exploited by triclustering \textsc{TriBox}.

📄 PDF Abstract BibTeX arXiv:2002.09880

Code (0)

등록된 구현이 없습니다.

Learning to Search in Branch and Bound Algorithms

2014-12-01 · NeurIPS 2014 12 · He He, Hal Daume III, Jason M. Eisner

Branch-and-bound is a widely used method in combinatorial optimization, including mixed integer programming, structured prediction and MAP inference. While most work has been focused on developing problem-specific techni…

Combinatorial Optimization Imitation Learning Structured Prediction

Molecular Design Based on Artificial Neural Networks, Integer Programming and Grid Neighbor Search

2021-08-23 · Naveed Ahmed Azam, Jianshen Zhu, Kazuya Haraguchi, Liang Zhao 외

A novel framework has recently been proposed for designing the molecular structure of chemical compounds with a desired chemical property using both artificial neural networks and mixed integer linear programming. In the…

OMPQ: Orthogonal Mixed Precision Quantization

2021-09-16 · Yuexiao Ma, Taisong Jin, Xiawu Zheng, Yan Wang 외

To bridge the ever increasing gap between deep neural networks' complexity and hardware capability, network quantization has attracted more and more research attention. The latest trend of mixed precision quantization ta…

AutoML Quantization

Smart Feasibility Pump: Reinforcement Learning for (Mixed) Integer Programming

2021-02-18 · Meng Qi, Mengxin Wang, Zuo-Jun Shen

In this work, we propose a deep reinforcement learning (DRL) model for finding a feasible solution for (mixed) integer programming (MIP) problems. Finding a feasible solution for MIP problems is critical because many suc…

Deep Reinforcement Learning reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Guaranteed Outlier Removal With Mixed Integer Linear Programs

2016-06-01 · CVPR 2016 6 · Tat-Jun Chin, Yang Heng Kee, Anders Eriksson, Frank Neumann

The maximum consensus problem is fundamentally important to robust geometric fitting in computer vision. Solving the problem exactly is computationally demanding, and the effort required increases rapidly with the proble…

global-optimization