Ningji Wei

GFORS: GPU-Accelerated First-Order Method with Randomized Sampling for Binary Integer Programs

  • Ningji Wei
  • Jiaming Liang
    • Categories 0-1 Programming, Constrained Nonlinear Optimization, Parallel Algorithms Tags , ,

    We present GFORS, a GPU-accelerated framework for large binary integer programs. It couples a first-order (PDHG-style) routine that guides the search in the continuous relaxation with a randomized, feasibility-aware sampling module that generates batched binary candidates. Both components are designed to run end-to-end on GPUs with minimal CPU–GPU synchronization. The framework establishes near-stationary-point guarantees for … Read more

    Set System Approximation for Binary Integer Programs: Reformulations and Applications

  • Ningji Wei
    • Categories 0-1 Programming, Cutting Plane Approaches, Integer Programming Tags , , , ,

    Covering and elimination inequalities are central to combinatorial optimization, yet their role has largely been studied in problem-specific settings or via no-good cuts. This paper introduces a unified perspective that treats these inequalities as primitives for set system approximation in binary integer programs (BIPs). We show that arbitrary set systems admit tight inner and outer … Read more

    Information Basis in Dynamic Robust Optimization

  • Ningji Wei
  • Peter Yun Zhang
    • Categories Robust Optimization Tags , , ,

    Dynamic robust optimization deals with sequential, multi-stage decisions in the face of uncertain, worst-case scenarios. To manage its complexity and the curse of dimensionality, decision rules simplify the search for an optimal policy. This paper explores a middle ground between two common decision rules: simple but imprecise constant policies, and accurate but less scalable affine … Read more

    On Supervalid Inequalities for Binary Interdiction Games

  • Ningji Wei
  • Jose L. Walteros
    • Categories Combinatorial Optimization, Cutting Plane Approaches, Integer Programming Tags , , ,

    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

    An Exact Approach for Solving Pickup-and-Delivery Traveling Salesman Problems with Neighborhoods

  • Cai Gao
  • Ningji Wei
  • Jose L. Walteros
    • Categories Nonlinear Optimization, Production and Logistics, Transportation Tags , , , ,

    This paper studies a variant of the traveling salesman problem called the pickup-and-delivery traveling salesman problem with neighborhoods that combines traditional pickup and delivery requirements with the flexibility of visiting the customers at locations within compact neighborhoods of arbitrary shape. We derive two optimality conditions for the problem, a local condition that verifies whether a … Read more

    Adjustability in Robust Linear Optimization

  • Ningji Wei
  • Peter Yun Zhang
    • Categories Robust Optimization Tags , ,

    We investigate the concept of adjustability — the difference in objective values between two types of dynamic robust optimization formulations: one where (static) decisions are made before uncertainty realization, and one where uncertainty is resolved before (adjustable) decisions. This difference reflects the value of information and decision timing in optimization under uncertainty, and is related … Read more

    Integer Programming Methods for Solving Binary Interdiction Games

  • Jose L. Walteros
  • Ningji Wei
    • Categories 0-1 Programming Tags , , , ,

    This paper studies a general class of interdiction problems in which the solution space of both the leader and follower are characterized by two discrete sets denoted the leader’s strategy set and the follower’s structure set. In this setting, the interaction between any strategy-structure pair is assumed to be binary, in the sense that the … Read more

    Integer Programming Formulations for Minimum Spanning Tree Interdiction

  • Foad Mahdavi Pajou
  • Jose L. Walteros
  • Ningji Wei
    • Categories Branch and Cut Algorithms, Integer Programming, Network Optimization Tags , , ,

    We consider a two-player interdiction problem staged over a graph where the leader’s objective is to minimize the cost of removing edges from the graph so that the follower’s objective, i.e., the weight of a minimum spanning tree in the residual graph, is increased up to a predefined level $r$. Standard approaches for graph interdiction … Read more