“There are some things which cannot be learned quickly, and time, which is all we have, must be paid heavily for their acquiring. They are the very simplest things, and because it takes a man’s life to know them the little new that each man gets from life is very costly and the only heritage he has to leave.” - Ernest Hemingway (More…)
News #
I will be updating both good news, bad news and all kinds of news.
Posts #
Maximal Cut (Max-Cut)
Maximal Cut (Max-Cut) # The Maximal Cut problem is to partition the vertices of a graph into two sets to maximize the number of edges between them. It’s a fundamental problem in combinatorial optimization. Recent Literature # Learning Combinatorial Optimization Algorithms over Graphs. NeurIPS, 2017. paper Dai, Hanjun and Khalil, Elias B and Zhang, Yuyu and Dilkina, Bistra and Song, Le Exploratory Combinatorial Optimization with Reinforcement Learning. AAAI, 2020. paper LBarrett, Thomas and Clements, William and Foerster, Jakob and Lvovsky, Alex.
Maximum Independent Set
Maximum Independent Set # The Maximum Independent Set problem is about finding the largest subset of vertices in a graph with no edges between them. It’s an NP-hard problem with important applications. Recent Literature # Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search. NeurIPS, 2018. paper Li, Zhuwen and Chen, Qifeng and Koltun, Vladlen. Learning What to Defer for Maximum Independent Sets ICML, 2020. paper Ahn, Sungsoo and Seo, Younggyo and Shin, Jinwoo
Metric $k$-center
General $k$-center problem statement: Let \((X, d)\) be a metric space where \(X\) is a set and \(d\) is a metric. A set \(V \subseteq X\) is provided together with a parameter \(k\). The goal is to find a subset \(C \subseteq V\) with \(|C| = k\) such that the maximum distance of a point in \(V\) to the closest point in \(C\) is minimized. The problem can be formally defined as follows: Input: a set $V \subseteq X$, and a parameter $k$. Output: a set $C \subseteq V$ of $k$ points. Goal: Minimize the cost $r^C(V) = \max_{v \in V} d(v, C)$ The k-Center Clustering problem can also be defined on a complete undirected graph $G = (V, E)$ as follows:
Mixed Integer Programming (MIP)
Mixed Integer Programming (MIP) # Mixed Integer Programming is a fundamental optimization framework widely used in operations research. Machine learning approaches are being applied to improve MIP solvers. Recent Literature # Sequential model-based optimization for general algorithm configuration International conference on learning and intelligent optimization, 2011. journal Hutter, Frank and Hoos, Holger H and Leyton-Brown, Kevin Non-model-based Search Guidance for Set Partitioning Problems AAAI, 2012. paper Kadioglu, Serdar and Malitsky, Yuri and Sellmann, Meinolf
Optimal Power Flow
Optimal Power Flow # Optimal Power Flow (OPF) is a fundamental problem in power systems optimization, determining the setpoints for generators to supply electricity while minimizing costs and satisfying physical and operational constraints. Recent Literature # Learning-based Optimal Power Flow ICLR, 2023. paper, code Yunqi Ding, Kai Wang, Yuanzhang Xiao, Dongyu Zhang Physics-Informed Neural Networks for Power Systems in the Presence of Uncertainty IEEE Power & Energy Society General Meeting, 2023. paper