Training neural networks (NNs) using combinatorial optimization solvers has gained attention in recent years. In low-data settings, the use of state-of-the-art mixed integer linear programming solvers, for instance, has the potential to exactly train an NN while avoiding computing-intensive training and hyperparameter tuning and simultaneously training and sparsifying the network. We study the case of few-bit discrete-valued neural networks, both binarized neural networks (BNNs) whose values are restricted to ±1 and integer-valued neural networks (INNs) whose values lie in the range [Formula: see text]. Few-bit NNs receive increasing recognition because of their lightweight architecture and ability to run on low-power devices: for example, being implemented using Boolean operations. This paper proposes new methods to improve the training of BNNs and INNs. Our contribution is a multiobjective ensemble approach based on training a single NN for each possible pair of classes and applying a majority voting scheme to predict the final output. Our approach results in the training of robust sparsified networks whose output is not affected by small perturbations on the input and whose number of active weights is as small as possible. We empirically compare this BeMi approach with the current state of the art in solver-based NN training and with traditional gradient-based training, focusing on BNN learning in few-shot contexts. We compare the benefits and drawbacks of INNs versus BNNs, bringing new light to the distribution of weights over the [Formula: see text] interval. Finally, we compare multiobjective versus single-objective training of INNs, showing that robustness and network simplicity can be acquired simultaneously, thus obtaining better test performances. Although the previous state-of-the-art approaches achieve an average accuracy of [Formula: see text] on the Modified National Institute of Standards and Technology data set, the BeMi ensemble approach achieves an average accuracy of 68.4% when trained with 10 images per class and 81.8% when trained with 40 images per class while having up to 75.3% NN links removed. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms—Discrete. Funding: This research was partially supported by the European Union Horizon 2020 Research and Innovation Programme [Grant 952215]. The work of A. M. Bernardelli is supported by a PhD scholarship funded under the “Programma Operativo Nazionale Ricerca e Innovazione” 2014–2020. Supplemental Material: The software that supports the findings of this study is available within the paper as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2023.0281 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

In the context of the maximum stable set problem, rank inequalities impose that the cardinality of any set of vertices contained in a stable set be, at most, as large as the stability number of the subgraph induced by such a set. Rank inequalities are very general, as they subsume many classical inequalities such as clique, hole, antihole, web, and antiweb inequalities. In spite of their generality, the exact separation of rank inequalities has never been addressed without the introduction of topological restrictions on the induced subgraph and the tightness of their closure has never been investigated systematically. In this work, we propose a methodology for optimizing over the closure of all rank inequalities with a right-hand side no larger than a small constant without imposing any restrictions on the topology of the induced subgraph. Our method relies on the exact separation of a relaxation of rank inequalities, which we call relaxed k-rank inequalities, whose closure is as tight. We investigate the corresponding separation problem, a bilevel programming problem asking for a subgraph of maximum weight with a bound on its stability number, whose study could be of independent interest. We first prove that the problem is [Formula: see text]-hard and provide some insights on its polyhedral structure. We then propose two exact methods for its solution: a branch-and-cut algorithm (which relies on a family of faced-defining inequalities which we introduce in this paper) and a purely combinatorial branch-and-bound algorithm. Our computational results show that the closure of rank inequalities with a right-hand side no larger than a small constant can yield a bound that is stronger, in some cases, than Lovász’s Theta function, and substantially stronger than bounds obtained with standard inequalities that are valid for the stable set problem, including odd-cycle inequalities and wheel inequalities. Summary of Contribution: This paper proposes two original methods for solving a challenging cut-separation problem (of bilevel type) for a large class of inequalities valid for one of the key operations research problems, namely, the max stable set problem. An extensive set of experimental results validates the proposed methods. All the source code and data sets are available online on GitHub.

This paper presents a novel method to compute the exact Kantorovich-Wasserstein distance between a pair of $d$-dimensional histograms having $n$ bins each. We prove that this problem is equivalent to an uncapacitated minimum cost flow problem on a $(d+1)$-partite graph with $(d+1)n$ nodes and $dn^{\frac{d+1}{d}}$ arcs, whenever the cost is separable along the principal $d$-dimensional directions. We show numerically the benefits of our approach by computing the Kantorovich-Wasserstein distance of order 2 among two sets of instances: gray scale images and $d$-dimensional biomedical histograms. On these types of instances, our approach is competitive with state-of-the-art optimal transport algorithms.

In the context of finding the largest stable set of a graph, rank inequalities prescribe that a stable set can contain, from any induced subgraph of the original graph, at most as many vertices as the stability number of the former. Although these inequalities subsume many of the valid inequalities known for the problem, their exact separation has only been investigated in few special cases obtained by restricting the induced subgraph to a specific topology. In this work, we propose a different approach in which, rather than imposing topological restrictions on the induced subgraph, we assume the right-hand side of the inequality to be fixed to a given (but arbitrary) constant. We then study the arising separation problem, which corresponds to the problem of finding a maximum weight subgraph with a bounded stability number. After proving its hardness and giving some insights on its polyhedral structure, we propose an exact branch-and-cut method for its solution. Computational results show that the separation of topology-free rank inequalities with a fixed right-hand side yields a substantial improvement over the bound provided by the fractional clique polytope (which is obtained with rank inequalities where the induced subgraph is restricted to a clique), often better than that obtained with Lovász’s Theta function via semidefinite programming.

We consider two approaches for solving the classical minimum vertex coloring problem—that is, the problem of coloring the vertices of a graph so that adjacent vertices have different colors and minimizing the number of used colors—namely, constraint programming and column generation. Constraint programming is able to solve very efficiently many of the benchmarks but suffers from a lack of effective bounding methods. On the contrary, column generation provides tight lower bounds by solving the fractional vertex coloring problem exploited in a branch-and-price algorithm, as already proposed in the literature. The column generation approach is here enhanced by using constraint programming to solve the pricing subproblem and to compute heuristic solutions. Moreover, new techniques are introduced to improve the performance of the column generation approach in solving both the linear relaxation and the integer problem. We report extensive computational results applied to the benchmark instances: we are able to prove optimality of 11 new instances and to improve the best-known lower bounds on 17 other instances. Moreover, we extend the solution approaches to a generalization of the problem known as the minimum vertex graph multicoloring problem, where a given number of colors has to be assigned to each vertex.

A fundamental and computationally challenging optimization task in wireless networks is to maximize the number of simultaneous transmissions, subject to signal-to-noise-and-interference ratio (SINR) requirements at the receivers. The conventional approach guaranteeing global optimality is to solve an integer programming model with explicit SINR constraints. These constraints are however numerically very difficult. We develop a new integer programming algorithm based on a much more effective representation of the SINR constraints. Computational experiments demonstrate that the new approach performs significantly better in proving optimality.

Abstract This article presents a column generation approach to a resource allocation problem arising in managing Wireless Mesh Networks. The problem consists in routing the given demands over the network and to allocate time resource to pairs of nodes. Half‐duplex constraints are taken into account together with the aggregate interference due to simultaneous transmissions, which affects the signal quality. Different problems are considered, according to the assumptions on the transmission power and rate. The resource allocation problem can be formulated as a Mixed Integer Linear Programming (MILP) problem and dealt with a column generation‐based approach. The pricing problem, due to signal quality constraints, turns out to be computationally demanding. To tackle these difficulties, besides a classical mathematical programming approach, we have applied a hybrid column generation approach where the pricing subproblem is solved using Constraint Programming. Numerical results show that the two methods are comparable. The results of the column generation are then used to solve heuristically the problem. The obtained results provide very small gaps (between lower bounds and Heuristic solutions) for two of the three considered problems and reasonable gaps for the third problem. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

Abstract In the Maximum Cut with Limited Unbalance problem, we want to partition the vertices of a weighted graph into two sets of sizes differing at most by a given threshold B, so that the sum of the weights of the crossing edges is maximum. This problem has been introduced in (Galbiati and Maffioli, Theor Comput Sci 385 (2007), 78–87) where polynomial time randomized approximation algorithms are proposed and their performance guarantees are analyzed in the case of non‐negative integer weights. In this article, we present extensive computational experience with these algorithms on a large number of different graphs. We then extend the analysis of these algorithms to integer weights not restricted in sign, and continue the computational testing. It turns out that the approximation ratios obtained are always substantially better than those guaranteed by the theoretical analysis. © 2010 Wiley Periodicals, Inc. NETWORKS 2010

The fundamental role of autonomous agents in managing activities of space systems has emerged some years ago with the NASA's Remote Agent Experiment. However, the possible advantages of employing multiple agents to manage activities on a single space