We study the problem of minimizing a convex function on the integer lattice when the function cannot be evaluated at noninteger points. We propose a new underestimator that does not require access to (sub)gradients of the objective but, rather, uses secant linear functions that interpolate the objective function at previously evaluated points. These linear mappings … Read more
The Golomb ruler problem is defined as follows: Given a positive integer n, locate n marks on a ruler such that the distance between any two distinct pair of marks are different from each other and the total length of the ruler is minimized. The Golomb ruler problem has applications in information theory, astronomy and … Read more
Mathematical programming formulation to identify the optimal value function of a negative Markov decision process (MDP) is non-convex, non-smooth, and computationally intractable. Also note that other well-known solution methods of MDP do not work properly for a negative MDP. More specifically, the policy iteration diverges, and the value iteration converges but does not provide an … Read more
Conflict learning algorithms are an important component of modern MIP and CP solvers. But strong conflict information is typically gained by depth-first search. While this is the natural mode for CP solving, it is not for MIP solving. Rapid Learning is a hybrid CP/MIP approach where CP search is applied at the root to learn … Read more
This paper is concerned with the cross-validation criterion for best subset selection in a linear regression model. In contrast with the use of statistical criteria (e.g., Mallows’ $C_p$, AIC, BIC, and various information criteria), the cross-validation only requires the mild assumptions, namely, samples are identically distributed, and training and validation samples are independent. For this … Read more
In this paper, we first present a new extended formulation of the Capacitated Concentrator Location Problem (CCLP) using the notion of cardinality of terminals assigned to a concentrator location. The disaggregated formulation consists of O(mn2) variables and constraints, where m denotes the number of concentrators and n the number of terminals. An immediate benefit of … Read more
We present a set of integer programs (IPs) for the Steiner tree problem with the property that the best solution obtained by solving all, provides an optimal Steiner tree. Each IP is polynomial in the size of the underlying graph and our main result is that the linear programming (LP) relaxation of each IP is … Read more
The development of practically well-behaving integer programming formulations is an important aspect of solving linear optimization problems over a set $X \subseteq \{0,1\}^n$. In practice, one is often interested in strong integer formulations with additional properties, e.g., bounded coefficients to avoid numerical instabilities. This article presents a lower bound on the size of coefficients in … Read more
We propose a novel way of applying cutting plane techniques to two-stage mixed-integer stochastic programs. Instead of using cutting planes that are always valid, our idea is to apply inexact cutting planes to the second-stage feasible regions that may cut away feasible integer second-stage solutions for some scenarios and may be overly conservative for others. … Read more
In this paper, we consider polytopes P that are contained in the unit hypercube. We provide conditions on the set of 0,1 vectors not contained in P that guarantee that P has a small Chvatal rank. Our conditions are in terms of the subgraph induced by these infeasible 0,1 vertices in the skeleton graph of … Read more