CCChen Chen

Chen Chen

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Chen Chen has a total of 21 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Serial and parallel two-column probing for mixed-integer programming

    by Yongzheng Dai, Chen Chen

    Probing in mixed-integer programming (MIP) is a technique of temporarily fixing variables to discover implications that are useful to branch-and-cut solvers. Such fixing is typically performed one variable at a time—this paper develops instead a two-column probing scheme that instead fixes a pair of variables per iteration. Although the scheme involves more work per iteration compared to the one-column approach, stronger implied bounds as well as more conflicts identified may compensate. Indeed, our prototype implementation was awarded first prize at the MIP Workshop 2024 Computational Competition on novel presolving approaches. This paper presents the aforementioned (serial) prototype and additionally develops an efficient parallelization, leveraging hardware acceleration to further improve overall solve times. Compared to serial two-column probing, our parallel version sacrifices some strength per-pair probed in exchange for greatly increasing the total number of such probings; computational experiments demonstrate its promise.

  • Open Access

    A Network Partition Model with Application to Police Districting in Chile

    by Evelyn Arrey, Ramon Auad, Hernan Caceres, Chen Chen, Jordi Pereira

    Preventive security is a critical social priority for communities, and so effective resource deployment is key. This paper concerns the optimal design of patrol areas called police districts---namely, the problem of police districting, where an urban region is divided according to various attributes such as: equitable distribution of workload; district compactness; and connectivity between units within districts. In this study, we present a new, high-resolution formulation considering street-segment units. Much of the literature on districting focuses on coarser, area-based indicators (\eg neighbourhoods), but the variance in police workload on a street-by-street basis suggest substantial benefits from a finer-grained approach. However, our high resolution model can present a major computational challenge to state-of-the-art optimization algorithms. Consequently we develop a novel method to solve the problem, formulating it as a mixed integer linear programming model that divides the urban region into districts while achieving a balanced distribution of cumulative crime levels across these districts. While our model generates balanced districts, for the sake of computational tractability it does not enforce the desirable attributes of district compactness and connectivity. Thus we develop a three-phase heuristic to refine the solution from the mixed-integer programming model. For our case study, we present the case of the police department of Antofagasta, Chile, consisting of over 10,000 street segments.

  • Open Access

    Parallelized Conflict Graph Cut Generation

    by Yongzheng Dai, Chen Chen

    A conflict graph represents logical relations between binary variables, and effective use of the graph can significantly accelerate branch-and-cut solvers for mixed-integer programming (MIP). In this paper we develop efficient parallel conflict graph management: conflict detection; maximal clique generation; clique extension; and clique merging. We leverage parallel computing in order to intensify computational effort on the conflict graph, thereby generating a much larger pool of cutting planes than what can be practically achieved in serial. Computational experiments demonstrate that the expanded pool of cuts enabled by parallel computing lead to substantial reductions in total MIP solve time, especially for more challenging cases.


  • Open Access

    Nonnegative Tensor Completion via Integer Optimization

    by Caleb Bugg, Chen Chen, Anil Aswani

    Unlike matrix completion, tensor completion does not have an algorithm that is known to achieve the information-theoretic sample complexity rate. This paper develops a new algorithm for the special case of completion for nonnegative tensors. We prove that our algorithm converges in a linear (in numerical tolerance) number of oracle steps, while achieving the information-theoretic rate. Our approach is to define a new norm for nonnegative tensors using the gauge of a particular 0-1 polytope; integer linear programming can, in turn, be used to solve linear separation problems over this polytope. We combine this insight with a variant of the Frank-Wolfe algorithm to construct our numerical algorithm, and we demonstrate its effectiveness and scalability through computational experiments using a laptop on tensors with up to one-hundred million entries.

  • Open Access

    Outer-Product-Free Sets for Polynomial Optimization and Oracle-Based Cuts

    by Daniel Bienstock, Chen Chen, Gonzalo Muñoz

    This paper introduces cutting planes that involve minimal structural assumptions, enabling the generation of strong polyhedral relaxations for a broad class of problems. We consider valid inequalities for the set $S\cap P$, where $S$ is a closed set, and $P$ is a polyhedron. Given an oracle that provides the distance from a point to $S$, we construct a pure cutting plane algorithm which is shown to converge if the initial relaxation is a polyhedron. These cuts are generated from convex forbidden zones, or $S$-free sets, derived from the oracle. We also consider the special case of polynomial optimization. Accordingly we develop a theory of \emph{outer-product-free} sets, where $S$ is the set of real, symmetric matrices of the form $xx^T$. All maximal outer-product-free sets of full dimension are shown to be convex cones and we identify several families of such sets. These families are used to generate strengthened intersection cuts that can separate any infeasible extreme point of a linear programming relaxation efficiently. Computational experiments demonstrate the promise of our approach.

  • Open Access

    A Spatial Branch-and-Cut Method for Nonconvex QCQP with Bounded Complex Variables

    by Chen Chen, Alper Atamturk, Shmuel S. Oren

    We develop a spatial branch-and-cut approach for nonconvex Quadratically Constrained Quadratic Programs with bounded complex variables (CQCQP). Linear valid inequalities are added at each node of the search tree to strengthen semidefinite programming relaxations of CQCQP. These valid inequalities are derived from the convex hull description of a nonconvex set of $2 \times 2$ positive semidefinite Hermitian matrices subject to a rank-one constraint. We propose branching rules based on an alternative to the rank-one constraint that allows for local measurement of constraint violation. Closed-form bound tightening procedures are used to reduce the domain of the problem. We apply the algorithm to solve the Alternating Current Optimal Power Flow problem with complex variables as well as the Box-constrained Quadratic Programming problem with real variables.