New cuts and a branch-cut-and-price model for the Multi Vehicle Covering Tour Problem

\(\) The Multi-Vehicle Covering Tour Problem (m-CTP) involves a graph in which the set of vertices is partitioned into a depot and three distinct subsets representing customers, mandatory facilities, and optional facilities. Each customer is linked to a specific subset of optional facilities that define its coverage set. The goal is to determine a set … Read more

Using Disjunctive Cuts in a Branch-and-Cut Method to Solve Convex Integer Nonlinear Bilevel Problems

We present a branch-and-cut method for solving convex integer nonlinear bilevel problems, i.e., bilevel models with nonlinear but convex objective functions and constraints in both the upper and the lower level. To this end, we generalize the idea of using disjunctive cuts to cut off integer-feasible but bilevel-infeasible points. These cuts can be obtained by … Read more

Binary Integer Program Reformulation: A Set System Approximation Approach

This paper presents a generic reformulation framework for binary integer programs (BIPs) without imposing additional specifications for the objective function or constraints. To facilitate such generality, we introduce a set system approximation theory designed to identify the tightest inner and outer approximations for any binary solution space using special types of set systems. This development … Read more

On Rank-Monotone Graph Operations and Minimal Obstruction Graphs for the Lovász-Schrijver SDP Hierarchy

We study the lift-and-project rank of the stable set polytopes of graphs with respect to the Lovász-Schrijver SDP operator LS_+, with a particular focus on finding and characterizing the smallest graphs with a given LS_+-rank (the least number of iterations of the LS_+ operator on the fractional stable set polytope to compute the stable set … Read more

A hybrid branch-and-bound and interior-point algorithm for stochastic mixed-integer nonlinear second-order cone programming

One of the chief attractions of stochastic mixed-integer second-order cone programming is its diverse applications, especially in engineering (Alzalg and Alioui, {\em IEEE Access}, 10:3522-3547, 2022). The linear and nonlinear versions of this class of optimization problems are still unsolved yet. In this paper, we develop a hybrid optimization algorithm coupling branch-and-bound and primal-dual interior-point … Read more

Cutting planes from the simplex tableau for quadratically constrained optimization problems

We describe a method to generate cutting planes for quadratically constrained optimization problems. The method uses information from the simplex tableau of a linear relaxation of the problem in combination with McCormick estimators. The method is guaranteed to cut off a basic feasible solution of the linear relaxation that violates the quadratic constraints in the … Read more

Mixed-Integer Programming Approaches to Generalized Submodular Optimization and its Applications

Submodularity is an important concept in integer and combinatorial optimization. A classical submodular set function models the utility of selecting homogenous items from a single ground set, and such selections can be represented by binary variables. In practice, many problem contexts involve choosing heterogenous items from more than one ground set or selecting multiple copies … Read more

A Stochastic Benders Decomposition Scheme for Large-Scale Stochastic Network Design

Network design problems involve constructing edges in a transportation or supply chain network to minimize construction and daily operational costs. We study a stochastic version where operational costs are uncertain due to fluctuating demand and estimated as a sample average from historical data. This problem is computationally challenging, and instances with as few as  100 … Read more

Stable Set Polytopes with High Lift-and-Project Ranks for the Lovász-Schrijver SDP Operator

\(\) We study the lift-and-project rank of the stable set polytopes of graphs with respect to the Lovász-Schrijver SDP operator \( \text{LS}_+\), with a particular focus on a search for relatively small graphs with high \( \text{LS}_+\)-rank (the least number of iterations of the \( \text{LS}_+\) operator on the fractional stable set polytope to compute … Read more

On Supervalid Inequalities for Binary Interdiction Games

Supervalid inequalities are a specific type of constraints often used within the branch-and-cut framework to strengthen the linear relaxation of mixed-integer programs. These inequalities share the particular characteristic of potentially removing feasible integer solutions as long as they are already dominated by an incumbent solution. This paper focuses on supervalid inequalities for solving binary interdiction … Read more