Author name cluster

Jimmy Lee

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

11 papers

1 author row

NeurIPS Conference 2023 Conference Paper

Two-Stage Predict+Optimize for MILPs with Unknown Parameters in Constraints

Xinyi Hu
Jasper Lee
Jimmy Lee

Consider the setting of constrained optimization, with some parameters unknown at solving time and requiring prediction from relevant features. Predict+Optimize is a recent framework for end-to-end training supervised learning models for such predictions, incorporating information about the optimization problem in the training process in order to yield better predictions in terms of the quality of the predicted solution under the true parameters. Almost all prior works have focused on the special case where the unknowns appear only in the optimization objective and not the constraints. Hu et al. proposed the first adaptation of Predict+Optimize to handle unknowns appearing in constraints, but the framework has somewhat ad-hoc elements, and they provided a training algorithm only for covering and packing linear programs. In this work, we give a new simpler and more powerful framework called Two-Stage Predict+Optimize, which we believe should be the canonical framework for the Predict+Optimize setting. We also give a training algorithm usable for all mixed integer linear programs, vastly generalizing the applicability of the framework. Experimental results demonstrate the superior prediction performance of our training framework over all classical and state-of-the-art methods.

PDF Details

NeurIPS Conference 2022 Conference Paper

Branch & Learn for Recursively and Iteratively Solvable Problems in Predict+Optimize

Xinyi Hu
Jasper Lee
Jimmy Lee
Allen Z. Zhong

This paper proposes Branch & Learn, a framework for Predict+Optimize to tackle optimization problems containing parameters that are unknown at the time of solving. Given an optimization problem solvable by a recursive algorithm satisfying simple conditions, we show how a corresponding learning algorithm can be constructed directly and methodically from the recursive algorithm. Our framework applies also to iterative algorithms by viewing them as a degenerate form of recursion. Extensive experimentation shows better performance for our proposal over classical and state of the art approaches.

PDF Details

IJCAI Conference 2020 Conference Paper

Automatic Dominance Breaking for a Class of Constraint Optimization Problems

Jimmy Lee
Allen Zhong

Exploiting dominance relations in many Constraint Optimization Problems can drastically speed up the solving process in practice. Identification and utilization of dominance relations, however, usually require human expertise. We present a theoretical framework for a useful class of constraint optimization problems to detect dominance automatically and formulate the generation of the associated dominance breaking nogoods as constraint satisfaction. By controlling the length and quantity of the nogoods, our method can generate dominance break- ing nogoods of varying strengths. Experimentation confirms runtime improvements of up to three orders of magnitude against manual methods.

PDF Details DOI

AAAI Conference 2020 Conference Paper

Finding Good Subtrees for Constraint Optimization Problems Using Frequent Pattern Mining

Hongbo Li
Jimmy Lee
He Mi
Minghao Yin

Making good decisions at the top of a search tree is important for ﬁnding good solutions early in constraint optimization. In this paper, we propose a method employing frequent pattern mining (FPM), a classic datamining technique, to ﬁnd good subtrees for solving constraint optimization problems. We demonstrate that applying FPM in a small number of random high-quality feasible solutions enables us to identify subtrees containing optimal solutions in more than 55% of problem instances for four real world benchmark problems. The method works as a plugin that can be combined with any search strategy for branch-and-bound search. Exploring the identiﬁed subtrees ﬁrst, the method brings substantial improvements for four efﬁcient search strategies in both total runtime and runtime of ﬁnding optimal solutions.

PDF Details

IJCAI Conference 2019 Conference Paper

DoubleLex Revisited and Beyond

Xuming Huang
Jimmy Lee

The paper proposes Maximum Residue (MR) as a notion to evaluate the strength of a symmetry breaking method. We give a proof to improve the best known DoubleLex MR upper bound from m! n! - (m! +n! ) to min(m! ,n! ) for an m x n matrix model. Our result implies that DoubleLex works well on matrix models where min(m, n) is relatively small. We further study the MR bounds of SwapNext and SwapAny, which are extensions to DoubleLex breaking further a small number of composition symmetries. Such theoretical comparisons suggest general principles on selecting Lex-based symmetry breaking methods based on the dimensions of the matrix models. Our experiments confirm the theoretical predictions as well as efficiency of these methods.

PDF Details

AAAI Conference 2016 Conference Paper

Breaking More Composition Symmetries Using Search Heuristics

Jimmy Lee
Zichen Zhu

The pruning power of partial symmetry breaking depends on the given subset of symmetries to break as well as the interactions among symmetry breaking constraints. In the context of Partial Symmetry Breaking During Search (ParSBDS), the search order determines the set of symmetry breaking constraints to add and thus also makes an impact on node and solution pruning. In this paper, we give the ﬁrst formal characterization of the pruning behavior of ParSBDS and its improved variants. Introducing the notion of Dominance- Completeness (DC-ness), we show that ParSBDS and variants eliminate the symmetry group of the given subset of symmetries if the resultant search tree is DC, and give an example scenario. Unfortunately, building a DC tree is not always possible. We propose two search heuristics with the aim of having more nodes dominated and thus also pruned during search. Extensive experimentation demonstrates how the proposed heuristics and their combination can drastically reduce the solution set size, search space and runtime when compared against the state-of-the-art static and dynamic symmetry breaking methods.

PDF Details

AAAI Conference 2016 Conference Paper

Increasing Nogoods in Restart-Based Search

Jimmy Lee
Christian Schulte
Zichen Zhu

Restarts are an important technique to make search more robust. This paper is concerned with how to maintain and propagate nogoods recorded from restarts efﬁciently. It builds on reduced nld-nogoods introduced for restarts and increasing nogoods introduced for symmetry breaking. The paper shows that reduced nld-nogoods extracted from a single restart are in fact increasing, which can thus beneﬁt from the efﬁcient propagation algorithm of the incNGs global constraint. We present a lighter weight ﬁltering algorithm for incNGs in the context of restart-based search using dynamic event sets (dynamic subscriptions). We show formally that the lightweight version enforces GAC on each nogood while reducing the number of subscribed decisions. The paper also introduces an efﬁcient approximation to nogood minimization such that all shortened reduced nld-nogoods from the same restart are also increasing and can be propagated with the new ﬁltering algorithm. Experimental results conﬁrm that our lightweight ﬁltering algorithm and approximated nogood minimization successfully trade a slight loss in pruning for considerably better efﬁciency, and hence compare favorably against existing state-of-the-art techniques.

PDF Details

AAAI Conference 2014 Conference Paper

Boosting SBDS for Partial Symmetry Breaking in Constraint Programming

Jimmy Lee
Zichen Zhu

The paper proposes a dynamic method, Recursive SBDS (ReSBDS), for efficient partial symmetry breaking. We first demonstrate how (partial) Symmetry Breaking During Search (SBDS) misses important pruning opportunities when given only a subset of symmetries to break. The investigation pinpoints the culprit and in turn suggests rectification. The main idea is to add extra conditional constraints during search recursively to prune also symmetric nodes of some pruned subtrees. Thus, ReSBDS can break extra symmetry compositions, but is carefully designed to break only the ones that are easy to identify and inexpensive to break. We present theorems to guarantee the soundness and termination of our approach, and compare our method with popular static and dynamic methods. When the variable (value) heuristic is static, ReSBDS is also complete in eliminating all interchangeable variables (values) given only the generator symmetries. Extensive experimentations confirm the efficiency of ReSBDS, when compared against state of the art methods.

PDF Details

AAAI Conference 2012 Conference Paper

Polynomially Decomposable Global Cost Functions in Weighted Constraint Satisfaction

Jimmy Lee
Ka Lun Leung
Yi Wu

In maintaining consistencies, such as GAC*, FDGAC* and weak EDGAC*, for global cost functions, Weighted CSP (WCSP) solvers rely on the projection and extension operations, which entail the computation of the cost functions’ minima. Tractability of this minimum computation is essential for efficient execution. Since projections/extensions modify the cost functions, an important issue is tractable projection-safety, concerning whether minimum cost computation remains tractable after projections/extensions. In this paper, we prove that tractable projection-safety is always possible for projections/extensions to/from the nullary cost function (W∅), and always impossible for projections/extensions to/from n-ary cost functions for n ≥ 2. When n = 1, the answer is indefinite. We give a simple negative example, while Lee and Leung’s flow-based projectionsafe cost functions are also tractable projection-safe. We propose polynomially decomposable cost functions, which are amenable to tractable minimum computation. We further prove that the polynomial decomposability property is unaffected by projections/extensions to/from unary cost functions. Thus, polynomially decomposable cost functions are tractable projection-safe. We show that the SOFT AMONG, SOFT REGULAR, SOFT GRAMMAR and MAX WEIGHT/MIN WEIGHT are polynomially decomposable. They are embedded in a WCSP solver for extensive experiments to confirm the feasibility and efficiency of our proposal.

PDF Details

AAAI Conference 2011 Conference Paper

A Comparison of Lex Bounds for Multiset Variables in Constraint Programming

Yat Law
Jimmy Lee
May Hiu Woo
Toby Walsh

Set and multiset variables in constraint programming have typically been represented using subset bounds. However, this is a weak representation that neglects potentially useful information about a set such as its cardinality. For set variables, the length-lex (LL) representation successfully provides information about the length (cardinality) and position in the lexicographic ordering. For multiset variables, where elements can be repeated, we consider richer representations that take into account additional information. We study eight different representations in which we maintain bounds according to one of the eight different orderings: length- (co)lex (LL/LC), variety-(co)lex (VL/VC), length-variety- (co)lex (LVL/LVC), and variety-length-(co)lex (VLL/VLC) orderings. These representations integrate together information about the cardinality, variety (number of distinct elements in the multiset), and position in some total ordering. Theoretical and empirical comparisons of expressiveness and compactness of the eight representations suggest that length-variety-(co)lex (LVL/LVC) and variety-length-(co)lex (VLL/VLC) usually give tighter bounds after constraint propagation. We implement the eight representations and evaluate them against the subset bounds representation with cardinality and variety reasoning. Results demonstrate that they offer signiﬁcantly better pruning and runtime.

PDF Details

AAAI Conference 2010 Conference Paper

A Stronger Consistency for Soft Global Constraints in Weighted Constraint Satisfaction

Jimmy Lee
K. Leung

Weighted Constraint Satisfaction is made practical by powerful consistency techniques, such as AC*, FDAC* and EDAC*, which reduce search space effectively and efficiently during search, but they are designed for only binary and ternary constraints. To allow soft global constraints, usually of high arity, to enjoy the same benefits, Lee and Leung give polynomial time algorithms to enforce generalized AC* (GAC*) and FDAC* (FDGAC*) for projection-safe soft non-binary constraints. Generalizing the stronger EDAC* is less straightforward. In this paper, we first reveal the oscillation problem when enforcing EDAC* on constraints sharing more than one variable. To avoid oscillation, we propose a weak version of EDAC* and generalize it to weak EDGAC* for non-binary constraints. Weak EDGAC* is stronger than FDGAC* and GAC*, but weaker than VAC and soft kconsistency for k > 2. We also show that weak EDGAC* can be enforced in polynomial time for projection-safe constraints. Extensive experimentation confirms the efficiency of our proposal.

PDF Details