Papers

The Jobs Shop Scheduling problem (JSP) is a canonical combinatorial optimization problem that is routinely solved for a variety of industrial purposes. It models the optimal scheduling of multiple sequences of tasks, each under a fixed order of operations, in which individual tasks require exclusive access to a predetermined resource for a specified processing time. The problem is NP-hard and computationally challenging even for medium-sized instances. Motivated by the increased stochasticity in production chains, this paper explores a deep learning approach to deliver efficient and accurate approximations to the JSP. In particular, this paper proposes the design of a deep neural network architecture to exploit the problem structure, its integration with Lagrangian duality to capture the problem constraints, and a post-processing optimization, to guarantee solution feasibility. The resulting method, called JSP-DNN, is evaluated on hard JSP instances from the JSPLIB benchmark library and is shown to produce JSP approximations of high quality at negligible computational costs.

poster session 6 @ blue 4, poster session 10 @ blue 4, poster session 6, poster session 10

Mixed-integer programming (MIP) technology offers a generic way of formulating and solving combinatorial optimization problems. While generally reliable, state-of-the-art MIP solvers base many crucial decisions on hand-crafted heuristics, largely ignoring common patterns within a given instance distribution of the problem of interest. Here, we propose MIP-GNN, a general framework for enhancing such solvers with data-driven insights. By encoding the variable-constraint interactions of a given mixed-integer linear program (MILP) as a bipartite graph, we leverage state-of-the-art graph neural network architectures to predict variable biases, i.e., component-wise averages of (near) optimal solutions, indicating how likely a variable will be set to 0 or 1 in (near) optimal solutions of binary MILPs. In turn, the predicted biases stemming from a single, once-trained model are used to guide the solver, replacing heuristic components. We integrate MIP-GNN into a state-of-the-art MIP solver, applying it to tasks such as node selection and warm-starting, showing significant improvements compared to the default setting of the solver on two classes of challenging binary MILPs.

poster session 6 @ blue 4, poster session 10 @ blue 4, oral session 10 @ blue 4, poster session 6, poster session 10, oral session 10

Since Bitcoin, blockchain has attracted the attention of researchers. The consensus mechanism at the center of blockchain is often criticized for wasting a large amount of computing power for meaningless hashing. At the same time, state-of-the-art models in deep learning require increasing computing power to be trained. Proof of Learning (PoL) is dedicated to using the originally wasted computing power to train neural networks. Most of the previous PoL consensus mechanisms are based on two methods, recomputation or performance metrics. However, in practical scenarios, these methods both do not satisfy all properties necessary to build a large-scale blockchain, such as certainty, constant verification, therefore are still far away from being practical. In this paper, we observe that the opacity of deep learning models is similar to the pre-image resistance of hash functions and can naturally be used to build PoL. Based on our observation, we propose a method called Directed Guiding Gradient. Using this method, our proposed PoL consensus mechanism has a similar structure to the widely used Proof of Work (PoW), allowing us to build practical blockchain on it and train neutral networks simultaneously. In experiments, we build a blockchain on top of our proposed PoL consensus mechanism and results show that our PoL works well.

poster session 6 @ blue 4, poster session 10 @ blue 4, poster session 6, poster session 10

Finding high-quality solutions to mixed-integer linear programming problems (MILPs) is of great importance for many practical applications. In this respect, the refinement heuristic local branching (LB) has been proposed to produce improving solutions and has been highly influential for the development of local search methods in MILP. The algorithm iteratively explores a sequence of solution neighborhoods defined by the so-called local branching constraint, namely, a linear inequality limiting the distance from a reference solution. For a LB algorithm, the choice of the neighborhood size is critical to performance. Although it was initialized by a conservative value in the original LB scheme, our new observation is that the "best" size is strongly dependent on the particular MILP instance. In this work, we investigate the relation between the size of the search neighborhood and the behavior of the underlying LB algorithm, and we devise a leaning-based framework for guiding the neighborhood search of the LB heuristic. The framework consists of a two-phase strategy. For the first phase, a scaled regression model is trained to predict the size of the LB neighborhood at the first iteration through a regression task. In the second phase, we leverage reinforcement learning and devise a reinforced neighborhood search strategy to dynamically adapt the size at the subsequent iterations. We computationally show that the neighborhood size can indeed be learned, leading to improved performances and that the overall algorithm generalizes well both with respect to the instance size and, remarkably, across instances.

poster session 6 @ blue 4, poster session 10 @ blue 4, oral session 10 @ blue 4, poster session 6, poster session 10, oral session 10

Relational Graph Convolutional Networks (RGCNs) are commonly used on Knowledge Graphs (KGs) to perform black box link prediction. Several algorithms have been proposed to explain their predictions. Evaluating performance of explanation methods for link prediction is difficult without ground truth explanations. Furthermore, there can be multiple explanations for a given prediction in a KG. No dataset exists where observations have multiple ground truth explanations to compare against. Additionally, no standard scoring metrics exist to compare predicted explanations against multiple ground truth explanations. We propose and evaluate a method, including a dataset, to benchmark explanation methods on the task of explainable link prediction using RGCNs.

poster session 6 @ blue 4, poster session 10 @ blue 4, poster session 6, poster session 10

Current Heterogeneous Network Embedding (HNE) models can be roughly divided into two types, i.e., relation-aware and metapath-aware models. However, they either fail to represent the non-pairwise relations in heterogeneous graph, or only capable of capturing local information around target node. In this paper, we propose a metapath based multilevel graph attention networks (MMAN) to jointly learn node embeddings on two substructures, i.e., metapath based graphs and hypergraphs extracted from original heterogeneous graph. Extensive experiments on three benchmark datasets for node classification and node clustering demonstrate the superiority of MMAN over the state-of-the-art works.

poster session 6 @ blue 4, poster session 10 @ blue 4, poster session 6, poster session 10

Neural Architecture Search (NAS) algorithms automate the task of finding optimal deep learning architectures given an initial search space of possible operations. Developing these search spaces is usually a manual affair with pre-optimized search spaces being more efficient, rather than searching from scratch. In this paper we present a new framework called Neural Architecture Type System (NeuralArTS) that categorizes the infinite set of network operations in a structured type system. We further demonstrate how NeuralArTS can be applied to convolutional layers and propose several future directions.

poster session 6 @ blue 4, poster session 10 @ blue 4, poster session 6, poster session 10

We use integer programming (IP) and constraint programming (CP) to search for sets of mutually orthogonal latin squares (MOLS). We improve the performance of the solvers by formulating an extended symmetry breaking method and provide an alternative CP encoding which performs much better in practice. Using state-of-the-art solvers we are able to quickly find pairs of MOLS (or prove their nonexistence) in all orders up to and including eleven. We also analyze the effectiveness of using CP and IP solvers to search for triples of MOLS and estimate the running time of using this approach to resolve the longstanding open problem of determining the existence of a triple of MOLS of order ten.

poster session 6 @ blue 4, poster session 10 @ blue 4, poster session 6, poster session 10

Multi-class classifier training using traditional meta-algorithms such as the popular One-vs-One (OvO) method may not always work well under cost-sensitive setups. Also, during inference, OvO becomes computationally challenging for higher class counts K as O(K^2) is its time complexity. In this paper, we present Opt-OvO, an optimized (resource-friendly) version of the One-vs-One algorithm to enable high-performance multi-class ML classifier training and inference directly on microcontroller units (MCUs). Opt-OvO enables billions of tiny IoT devices to self learn/train (offline) after their deployment, using live data from a wide range of IoT use-cases. We demonstrate Opt-OvO by performing live ML model training on 4 popular MCU boards using datasets of varying class counts, sizes, and feature dimensions. The most exciting finding was, on the 3 $ ESP32 chip, Opt-OvO trained a multi-class ML classifier using a dataset of class count 50 and performed unit inference in super real-time of 6.2 ms.

poster session 6 @ blue 4, poster session 10 @ blue 4, poster session 6, poster session 10

We consider applications involving a large set of instances of projecting points to polytopes. We develop an intuition guided by theoretical and empirical analysis to show that when these instances follow certain structures, a large majority of the projections lie on vertices of the polytopes. To do these projections efficiently we derive a vertex-oriented incremental algorithm to project a point onto any arbitrary polytope, as well as give specific algorithms to cater to simplex projection and polytopes where the unit box is cut by planes. Such settings are especially useful in web-scale applications such as optimal matching or allocation problems. Several such problems in internet marketplaces (e-commerce, ride-sharing, food delivery, professional services, advertising, etc.), can be formulated as Linear Programs (LP) with such polytope constraints that require a projection step in the overall optimization process. We show that in the very recent work \cite{basu2020}, the polytopic projection is the most expensive step and our efficient projection algorithms help in gaining massive improvements in performance.

poster session 6 @ blue 4, poster session 10 @ blue 4, poster session 6, poster session 10

Machine learning systems based on minimizing average error have been shown to perform inconsistently across notable subsets of the data, which is not exposed by a low average error for the entire dataset. In consequential social and economic applications, where data represent people, this can lead to discrimination of underrepresented gender and ethnic groups. Distributionally Robust Optimization (DRO) seemingly addresses this problem by minimizing the worst expected risk across subpopulations. We establish theoretical results that clarify the relation between DRO and the optimization of the same loss averaged on an adequately weighted training dataset. A practical implication of our results is that neither DRO nor curating the training set should be construed as a complete solution for bias mitigation.

poster session 6 @ blue 4, poster session 10 @ blue 4, poster session 6, poster session 10

The paper proposes a probabilistic generalization of the well-known Strong Backdoor Set~(SBS) concept applied to the Boolean Satisfiability Problem (SAT). We call a set of Boolean variables $B$ a $\rho$-backdoor, if for a fraction $\rho$ of possible assignments of variables from $B$, assigning their values to variables in a Boolean formula in Conjunctive Normal Form (CNF) results in polynomially solvable formulas. Clearly, a $\rho$-backdoor with $\rho=1$ is an SBS. For a given set $B$ it is possible to efficiently construct an $(\varepsilon, \delta)$-approximation of parameter $\rho$ using the Monte Carlo method. Thus, we define an $(\varepsilon, \delta)$-SBS as such a set $B$ for which the estimation of the parameter $\rho$ deviates from 1 by no more than $\varepsilon$ with probability no less than $1-\delta$. We consider the problems of finding the minimum SBS and the minimum $(\varepsilon, \delta)$-SBS. To solve the former, one can use the algorithm described by R.~Williams, C.~Gomes and B.~Selman in 2003. In the paper we propose a new probabilistic algorithm to solve the latter, and show that the asymptotic estimation of the worst case complexity of the proposed algorithm is significantly smaller than that of the algorithm by Williams~et~al. For practical applications, we suggest a metaheuristic optimization algorithm based on the penalty function method to seek the minimal $(\varepsilon, \delta)$-SBS. Results of computational experiments show that the use of $(\varepsilon, \delta)$-SBSes found by the proposed algorithm allows speeding up solving of test problems related to equivalence checking and hard crafted and combinatorial benchmarks compared to state-of-the-art SAT solvers.

poster session 6 @ blue 4, poster session 10 @ blue 4, oral session 6 @ blue 4, poster session 6, poster session 10, oral session 6

The growing interest in explainable artificial intelligence(XAI) for critical decision-making motivates the need for interpretable machine learning (ML) models. In fact, due to their structure (especially with small sizes), these models are inherently understandable by humans. Recently, several exact methods for computing such models are proposed to overcome weaknesses of traditional heuristic methods by providing more compact models or better prediction quality. Despite their compressed representation of Boolean functions, Binary decision diagrams (BDDs) did not gain enough interest as other interpretable ML models. In this paper, we first propose SAT-based models for learning optimal BDDs (in terms of the number of features) that classify all input examples. Then, we lift the encoding to a MaxSAT model to learn optimal BDDs give limited depths, that maximize the number of examples correctly classified. Finally, we tackle the fragmentation problem by introducing a method to merge compatible subtrees for the BDDs found via the MaxSAT model. Our empirical study shows clear benefits of the proposed approach in better prediction performance compared to the existing heuristic approach, and better interpretability and lighter en-coding size compared to the state-of-the-art approaches.

poster session 6 @ blue 4, poster session 10 @ blue 4, oral session 6 @ blue 4, poster session 6, poster session 10, oral session 6

The simple temporal problem (STP) is one of the most influential reasoning formalisms for representing temporal information in AI. We study the problem of resolving inconsistency of data encoded in the STP. We prove that the problem of identifying a maximally large consistent subset of data is NP-hard. In practical instances, it is reasonable to assume that the amount of erroneous data is small. We therefore parameterize by the number of constraints that need to be removed to achieve consistency. Using tools from parameterized complexity we design fixed-parameter tractable algorithms for two large fragments of the STP. Our main algorithmic results employ reductions to the Directed Subset Feedback Arc Set problem and iterative compression combined with an efficient algorithm for the Edge Multicut problem. We complement our algorithmic results with hardness results that rule out fixed-parameter tractable algorithms for all remaining non-trivial fragments of the STP (under standard complexity-theoretic assumptions). Together, our results give a full classification of the classical and parameterized complexity of the problem.

poster session 6 @ blue 4, poster session 10 @ blue 4, poster session 6, poster session 10

Many planning, scheduling or multi-dimensional packing problems involve the design of subtle logical combinations of temporal or spatial constraints. On the one hand, the precise modelling of these constraints, which are formulated in various relation algebras, entails a number of possible logical combinations and requires expertise in constraint-based modelling. On the other hand, active constraint acquisition (CA) has been used successfully to support non-experienced users in learning conjunctive constraint networks through the generation of a sequence of queries. In this paper, we propose GEACQ, which stands for Generic Qualitative Constraint Acquisition, an active CA method that learns qualitative constraints via the concept of qualitative queries. GEACQ combines qualitative queries with time-bounded path consistency (PC) and background knowledge propagation to acquire the qualitative constraints of any scheduling or packing problem. We prove soundness, completeness and termination of GEACQ by exploiting the jointly exhaustive and pairwise disjoint property of qualitative calculus and we give an experimental evaluation that shows (i) the efficiency of our approach in learning temporal constraints and, (ii) the use of GEACQ on real scheduling instances.

poster session 6 @ blue 4, poster session 10 @ blue 4, oral session 10 @ blue 4, poster session 6, poster session 10, oral session 10

Finding diverse solutions in combinatorial problems recently has received considerable attention (Baste et al. 2020, Fomin et al. 2020, Hanaka et al. 2021). In this paper we study the following type of problems: given an integer $k$, the problem asks for $k$ solutions such that the sum of pairwise (weighted) Hamming distances between these solutions is maximized. Such solutions are called \emph{diverse solutions}. We present a polynomial-time algorithm for finding diverse shortest $st$-paths in weighted directed graphs. Moreover, we study the diverse version of other classical combinatorial problems such as diverse weighted matroid bases, diverse weighted arborescences, and diverse bipartite matchings. We show that these problems can be solved in polynomial time as well. To evaluate the practical performance of our algorithm for finding diverse shortest $st$-paths, we conduct a computational experiment with synthetic and real-world instances. The experiment shows that our algorithm successfully computes diverse solutions within reasonable computational time.

poster session 6 @ blue 4, poster session 10 @ blue 4, oral session 6 @ blue 4, poster session 6, poster session 10, oral session 6

Popular first-order stochastic optimization methods for deep neural networks (DNNs) are usually either accelerated schemes (e.g. stochastic gradient descent (SGD) with momentum) or adaptive step-size methods (e.g. Adam/AdaMax, AdaBelief). In many contexts, including image classification with DNNs, adaptive methods tend to generalize poorly compared to SGD, i.e. get stuck in non-robust local minima; however, SGD typically converges slower. We analyze possible reasons for this behavior by modeling gradient updates as vectors of random variables and comparing them to probabilistic bounds to identify "meaningful" updates. Through experiments, we observe that only layers close to the output have "definitely non-random" update behavior. In the future, the tools developed here may be useful in rigorously quantifying and analyzing intuitions about why some optimizers and particular DNN architectures perform better than others.

poster session 6 @ blue 4, poster session 10 @ blue 4, poster session 6, poster session 10

The number of cores on graphical computing units (GPUs) is reaching thousands nowadays, whereas the clock speed of processors stagnates. Unfortunately, constraint programming solvers do not take advantage yet of GPU parallelism. One reason is that constraint solvers were primarily designed within the mental frame of sequential computation. To solve this issue, we take a step back and contribute to a simple, intrinsically parallel, lock-free and formally correct programming language based on concurrent constraint programming. We then re-examine parallel constraint solving on GPUs within this formalism, and develop Turbo, a simple constraint solver entirely programmed on GPUs. Turbo validates the correctness of our approach and compares positively to a parallel CPU-based solver.

poster session 6 @ blue 4, poster session 10 @ blue 4, poster session 6, poster session 10