The Minimum Connectivity Inference (MCI) problem represents an NP-hard generalisation of the well-known minimum spanning tree problem and has been studied in different fields of research independently. Let an undirected complete graph and finitely many subsets (clusters) of its vertex set be given. Then, the MCI problem is to find a minimal subset of edges … Read more
It is folklore knowledge that nonconvex mixed-integer nonlinear optimization problems can be notoriously hard to solve in practice. In this paper we go one step further and drop analytical properties that are usually taken for granted in mixed-integer nonlinear optimization. First, we only assume Lipschitz continuity of the nonlinear functions and additionally consider multivariate implicit … Read more
We present a new exact method for bi-objective pure integer linear programming, the so-called Multi-Stage Exact Algorithm (MSEA). The method combines several existing exact and approximate algorithms in the literature to compute the entire nondominated frontier of any bi-objective pure integer linear program. Each algorithm available in MSEA has multiple versions in the literature. Hence, … Read more
Utility-based shortfall risk measure (SR) has received increasing attentions over the past few years for its potential to quantify more effectively the risk of large losses than conditional value at risk. In this paper we consider the case that the true loss function is unavailable either because it is difficult to be identified or the … Read more
In this paper, we use the parametric programming technique and pseudo metrics to study the quantitative stability of the two-stage stochastic linear programming problem with full random recourse. Under the simultaneous perturbation of the cost vector, coefficient matrix and right-hand side vector, we first establish the locally Lipschitz continuity of the optimal value function and … Read more
This paper provides the first meaningful documentation and analysis of an established technique which aims to obtain an approximate solution to linear programming problems prior to applying the primal simplex method. The underlying algorithm is a penalty method with naive approximate minimization in each iteration. During initial iterations an approach similar to augmented Lagrangian is … Read more
Contract carriers in the trucking industry are known to offer shippers a per mile rate that decreases stepwise as the shipper’s route lengthens, with a mileage band designated for each rate. While the use of quantity-based pricing discounts in supply chains has been well studied, there has been no research on how shippers should route … Read more
We consider the Robust Standard Quadratic Optimization Problem (RStQP), in which an uncertain (possibly indefinite) quadratic form is extremized over the standard simplex. Following most approaches, we model the uncertainty sets by ellipsoids, polyhedra, or spectrahedra, more precisely, by intersections of sub-cones of the copositive matrix cone. We show that the copositive relaxation gap of … Read more
We propose a combinatorial algorithm to compute the Hoffman constant of a system of linear equations and inequalities. The algorithm is based on a characterization of the Hoffman constant as the largest of a finite canonical collection of easy-to-compute Hoffman constants. Our algorithm and characterization extend to the more general context where some of the … Read more
We consider the NP-hard problem of minimizing a separable concave quadratic function over the integral points in a polyhedron, and we denote by D the largest absolute value of the subdeterminants of the constraint matrix. In this paper we give an algorithm that finds an epsilon-approximate solution for this problem by solving a number of … Read more