In this short paper, we argue that the standard approach adopted by modern mixed-integer linear programming solvers of using very little cutting plane generation in the branch-and-bound tree can be too conservative and lead to the loss of significant opportunities. Our observation is motivated by some relatively simple computational investigation on a couple of instances in the MIPlib 2010 collection for which the benefit of generating globally valid cuts in the tree is significant. History: This “Challenge” paper was invited by the Editor-in-Chief and based on the topics raised by the author at his plenary address at the 2022 INFORMS Computing Society Conference in Tampa, Florida.

Integer Linear Programming (ILP) formulations of multi-label Markov random fields (MRFs) models with global connectivity priors were investigated previously in computer vision. In these works, only Linear Programming (LP) relaxations [1] or simplified versions [2] of the problem were solved. This paper investigates the ILP of MRF with exact connectivity priors via a branch-and-cut method, which provably finds globally optimal solutions. It enforces connectivity priors iteratively by a cutting plane method, and provides feasible solutions with a guarantee on sub-optimality even if we terminate it earlier. The proposed ILP can be applied as a post-processing method on top of any existing multi-label segmentation approach. As it provides globally optimal solution, it can be used off-line to serve as quality check for any fast on-line algorithm. Furthermore, the scribble based model presented in this paper could be potentially used to generate ground-truth proposals for any deep learning based segmentation. We demonstrate the power and usefulness of our model by extensive experiments on the BSDS500 and PASCAL VOC dataset. The experiments show that our proposed model achieves great performance, yielding provably global optimum in most instances and that provably good optimization solutions also provide good segmentation accuracy, even with the limited computing time of few seconds.

Following the flurry of recent theoretical work on cutting planes from two-row mixed integer group relaxations of a linear programming tableau, we report on computational tests to evaluate the strength of two-row cuts based on lattice-free triangles having more than one integer point on one side. A heuristic procedure to generate such triangles (referred to in the literature as “type 2” triangles) is presented, and then the coefficients of the integer variables are tightened by lifting. To test the effectiveness of triangle cuts, we compare the gap closed using Gomory mixed integer cuts for one round, the gap closed in one round using all the triangle cuts generated by our heuristic, and the gap closed by a small number of two-row split cuts. Our tests are carried out on randomly generated instances designed to represent different problem features by varying the number of integer nonbasic variables, bounds, nonnegativity constraints, and density, as well as on the classical MIPLIB instances. The outcome of this computational analysis is some insight into key characteristics of MIP instances whose presence makes two-row triangle cuts computationally effective. In particular, it appears to be necessary that the tableau row pairs are dense, and more subjectively that the nonbasic continuous variables are “important.” Unfortunately these characteristics seem to be rarely present among real-life instances, and more specifically the tableau rows of the MIPLIB instances are far from dense.

The traveling salesman problem with time windows (TSPTW) is the problem of finding a minimum-cost path visiting a set of cities exactly once, where each city must be visited within a given time window. We present an extended formulation for the problem based on partitioning the time windows into subwindows that we call buckets. We present cutting planes for this formulation that are computationally more effective than the ones known in the literature because they exploit the division of the time windows into buckets. To obtain a good partition of the time windows, we propose an iterative linear programming (LP)-based procedure that may produce buckets of different sizes. The LP relaxation of this formulation yields strong lower bounds for the TSPTW and provides a good starting point for our branch-and-cut algorithm. We also present encouraging computational results on hard test problems from the literature, namely, asymmetric instances arising from a practical scheduling application, as well as randomly generated symmetric instances. In particular, we solve a number of previously unsolved benchmark instances.