Paper uses integer programming for non-convex boosting in classification.
problem Improving classification performance using non-convex optimization.
method Non-convex boosting via integer programming.
result Results comparable to or better than state-of-the-art.
The paper uses clustering and integer programming to optimize stock selection for investment funds.
problem Maximizing profits and minimizing risk in stock markets.
method Data-oriented analysis and clustering techniques with integer programming.
result Reconstructed NASDAQ 100 index fund example demonstrates effectiveness.
Optimizes intervention design for causal discovery using integer programming.
problem Identifying causal structures from observational data due to confounding variables.
method Uses integer programming to design minimal intervention sets for causal structure identifiability.
result Provides exact and modular solutions adaptable to various experimental settings and constraints.
We study the problem of instance segmentation in biological images with crowded and compact cells. We formulate this task as an integer program where variables correspond to cells and constraints enforce that cells do not overlap. To solve this integer program, we propose a column generation formulation where the prici…
Transformers improve solving mixed-integer programs, especially CLSP.
problem Solving Capacitated Lot Sizing Problem (CLSP) with mixed-integer programming.
method Employing transformer models to predict binary variables in CLSP.
result Transformer model outperforms CPLEX and LSTM in solving CLSP.
Paper proposes algorithms for BMF using integer programming.
problem Approximating binary input matrix as product of two smaller binary factors.
method Alternating optimization strategy using integer programming to solve subproblems and combine solutions.
result Proposed algorithms outperform state of the art on medium-scale problems.
The crosscap number of a knot is an invariant describing the non-orientable surface of smallest genus that the knot bounds. Unlike knot genus (its orientable counterpart), crosscap numbers are difficult to compute and no general algorithm is known. We present three methods for computing crosscap number that offer varyi…
New LNS framework improves integer program solving.
problem Solving large-scale integer linear programs efficiently.
method Large neighborhood search with imitation and reinforcement learning.
result Framework significantly outperforms commercial solvers.
Mixed integer programming identifies critical neurons in neural networks.
problem Identifying neurons critical for network performance and generalization.
method Developed a mixed integer program (MIP) to assign importance scores to neurons, guiding pruning decisions.
result The method identifies multiple 'lucky' sub-networks resulting in optimized architectures that generalize across datasets.
This dissertation uses ILP to learn Bayesian network structures efficiently.
problem Learning the structure of Bayesian networks from data.
method Integer Linear Programming formulation with cluster constraints and cutting planes.
result The approach finds feasible solutions for Bayesian network structures efficiently.
New MIP approach for efficient change-point detection.
problem Offline multiple change-point detection in data streams.
method Mixed-integer programming (MIP) for globally optimal PWL fitting.
result Provable tighter relaxations for segment assignment variables.
A hybrid algorithm combines optimization and enumeration for symbolic regression.
problem Finding any function from a set of operators without prior specification.
method Mixed-integer nonlinear optimization with explicit enumeration and constraints.
result The hybrid algorithm is competitive with state-of-the-art methods.
Paper introduces DP methods for high-dimensional variable selection.
problem Sparse variable selection in high-dimensional learning.
method Pure differentially private estimators using Integer Programming.
result Achieves state-of-the-art empirical support recovery.
New method learns BN structures from data efficiently.
problem Learning sparse DAG structure of BN from continuous data.
method Consistent second-order conic integer programming with early stopping criterion.
result Near-optimal solutions to medium-size problems within reasonable time.
MEC-IP uses IP to efficiently find MECs in BNs from observational data.
problem Discovering Markov Equivalent Classes (MECs) in Bayesian Networks (BNs) efficiently.
method Clique-focusing strategy and EMSG for MEC discovery via Integer Programming.
result Significant reduction in computational time and improved accuracy.
We define a pseudo-inverse for line graphs using linear integer programming.
problem Not all graphs have a corresponding root graph, making the line graph operation non-invertible.
method Propose a linear integer program to edit the smallest number of edges in the line graph to recover a root graph.
result The pseudo-inverse operation is well-behaved and works in practice as shown by empirical experiments.
ExDBN learns dynamic Bayesian networks using mixed-integer programming.
problem Learning dynamic causal relationships from time series data.
method Score-based learning algorithm using mixed-integer quadratic programming with branch-and-cut method.
result The proposed method produces more accurate results than state-of-the-art approaches.
Adaptive IP approach optimizes intervention design for causal graph recovery.
problem Designing efficient interventions to recover causal relationships from data.
method Iterative integer programming approach for optimizing information gain.
result Adaptive IP approach achieves full causal graph recovery with fewer interventions.
Low-rank approximations of data matrices are an important dimensionality reduction tool in machine learning and regression analysis. We consider the case of categorical variables, where it can be formulated as the problem of finding low-rank approximations to Boolean matrices. In this paper we give what is to the best …
Optimizes marketing strategies with practical constraints.
problem Adjusting marketing activities with minimum and maximum changes.
method Formulated as a mixed integer nonlinear program (MINLP), reformulated for computational efficiency.
result Significant improvements in solution process for realistic problems.
The paper develops mixed-integer formulations for neural networks using partitioning.
problem Optimizing trained ReLU neural networks with balanced model size and tightness.
method Partitioning node inputs into groups, forming the convex hull via disjunctive programming.
result The proposed formulations outperform existing ones, especially with fewer partitions.
The Slope Conjecture relates a quantum knot invariant, (the degree of the colored Jones polynomial of a knot) with a classical one (boundary slopes of incompressible surfaces in the knot complement). The degree of the colored Jones polynomial can be computed by a suitable (almost tight) state sum and the solution of a …
This paper shows how to hedge financial risks with integer investments.
problem Evaluating the minimal super-hedging price with integer-valued strategies for arbitrary payoffs.
method Formulated a dynamic programming principle to evaluate the minimal super-hedging price with integer-valued strategies for continuous piecewise affine terminal claims.
result It is possible to evaluate the minimal super-hedging price with integer-valued strategies for discrete-time, arbitrary Ω.
New algorithm completes nonnegative tensors with fewer samples and faster convergence.
problem Tensor completion tension between sample complexity and computational complexity.
method Integer programming and Blended Conditional Gradients algorithm.
result Achieves information-theoretic sample complexity rate with practical convergence.
New MIP methods improve training of integer-valued neural networks.
problem Training integer-valued neural networks with limited data and resources.
method Formulated new MIP models to optimize training efficiency and handle more data.
result Significantly outperforms previous state-of-the-art methods in accuracy, training time, and data usage.
ReLU networks trained with MILPs match deep learning accuracy.
problem Training deep neural networks efficiently.
method Iterative training with Mixed Integer Linear Programs (MILPs).
result ReLU networks can be trained with MILPs achieving similar accuracy to deep learning methods.
Paper designs optimal ECOCs using IP for robust multiclass classification.
problem Designing robust ECOCs for multiclass classification.
method Integer Programming formulation to minimize codebooks with desirable error-correcting properties, leveraging graph-theoretic structure and edge clique covers.
result IP-generated codebooks achieve high nominal and robust adversarial accuracy.
Optimizes risk assessment tools using mixed-integer programming.
problem Challenges in healthcare risk assessment due to label scarcity and asymmetric misclassification costs.
method Jointly optimizes scoring weights and category thresholds via mixed-integer programming (MIP).
result Prevents label-scarce category collapse and achieves more accurate risk categorization.
This paper proposes new search algorithms for counterfactual explanations based upon mixed integer programming. We are concerned with complex data in which variables may take any value from a contiguous range or an additional set of discrete states. We propose a novel set of constraints that we refer to as a "mixed pol…
Optimal binning method for numeric targets using mathematical programming.
problem Optimizing the discretization of numeric variables for classification.
method Mathematical programming formulation for binary, continuous, and multi-class targets with constraints.
result Convex mixed-integer programming formulations for all target types.
A new portfolio optimization model minimizes maximum drawdown, offering faster and more robust solutions.
problem Optimizing portfolios during financial distress, especially during crises.
method Linearization of Markowitz model based on maximum drawdown, with a Mixed-Integer Linear Programming variation.
result 200 times faster solving time with a more profitable and robust solution.
We use a new combinatorial technique to prove the optimal interior partial regularity result for Lp-vectorfields with integer fluxes minimizing the Lp-energy. More precisely, we prove that the minimal vectorfields are Hölder outside a set which is locally finite inside the domain. The results continue the program start…
New method learns DAGs from noisy data without identifiability assumptions.
problem Learning DAGs from non-identifiable Gaussian models with heteroscedastic noise.
method Mixed-integer programming framework for medium-sized problems.
result Asymptotically optimal solution with early stopping criterion.
Decision trees have been a very popular class of predictive models for decades due to their interpretability and good performance on categorical features. However, they are not always robust and tend to overfit the data. Additionally, if allowed to grow large, they lose interpretability. In this paper, we present a mix…
We improve optimization for data with varying variance.
problem Optimizing data with varying variance.
method Generalized learning and optimization frameworks for data-driven optimization.
result Asymptotic and finite sample guarantees for stochastic programs.
New MIP algorithms improve sparse classifier learning times.
problem Sparse classifier learning at large scales.
method Developed exact and approximate MIP algorithms for ℓ0-regularized classification. result Significantly improved statistical performance compared to existing methods.
The paper develops algorithms for Boolean matrix factorization using IP and heuristics.
problem Approximating binary input matrices as products of smaller binary factors.
method Alternating optimization with integer programming and greedy/local-search heuristics.
result Proposed methods improve scalability and performance compared to existing techniques.
Paper proposes a novel optimization method for disaggregating smart meter data.
problem Energy disaggregation, inferring appliance-specific energy consumption from aggregate meter data.
method Two-stage optimization approach: first phase uses mixed integer programming, second phase binary quadratic optimization with penalty terms and appliance constraints.
result Proposed method successfully reconstructs appliance signatures, overcoming previous optimization-based methods' limitations.
Optimizes financial auditor schedules to reduce time and costs.
problem Efficiently scheduling financial auditors with multiple constraints.
method Used Integer Linear Programming and compared two exact formulations.
result Multi-commodity network flow formulation is 24 times faster.
ExDAG solves DAG learning problems with low structural Hamming distance.
problem Learning DAGs with low structural Hamming distance under identifiability assumptions.
method Mixed-integer quadratic programming (MIQP) with branch-and-bound-and-cut algorithm and lazy constraints.
result ExDAG guarantees global convergence and provides a real-time quality assessment.
The paper analyzes financial networks with default charges and defines a model using fixpoint problems.
problem Modeling systemic risk in interbank networks with crossholdings and default charges.
method Mixed integer-linear programming and Gaussian elimination algorithm for computing clearing pairs.
result Developed methods to compute maximal and minimal clearing pairs.
We consider the problem of learning decision rules for prediction with feature budget constraint. In particular, we are interested in pruning an ensemble of decision trees to reduce expected feature cost while maintaining high prediction accuracy for any test example. We propose a novel 0-1 integer program formulation …
This work analyzes machine learning for Lagrangian Relaxation in MILP.
problem Improving efficiency in solving large-scale MILP problems.
method Data-driven Algorithm Design approach to learn Lagrangian multipliers.
result Stochastic Gradient Ascent achieves the minimax optimal rate for learning multipliers.
We propose to prune a random forest (RF) for resource-constrained prediction. We first construct a RF and then prune it to optimize expected feature cost & accuracy. We pose pruning RFs as a novel 0-1 integer program with linear constraints that encourages feature re-use. We establish total unimodularity of the constra…
VNA solves large portfolio optimization problems efficiently.
problem Large-scale portfolio optimization under real-world constraints.
method Mapped to Ising-like Hamiltonian and solved with VNA.
result Identifies near-optimal solutions for over 2,000 assets.
This paper presents an acceleration framework for packing linear programming problems where the amount of data available is limited, i.e., where the number of constraints m is small compared to the variable dimension n. The framework can be used as a black box to speed up linear programming solvers dramatically, by two…
PNNs improve personalized healthcare policies using mixed integer programming.
problem Learning treatment policies for patients with limited data.
method Prescriptive networks (PNNs) trained with mixed integer programming.
result PNNs outperform existing methods in reducing peak blood pressure.
We study the problem of learning sequential decision-making policies in settings with multiple state-action representations. Such settings naturally arise in many domains, such as planning (e.g., multiple integer programming formulations) and various combinatorial optimization problems (e.g., those with both integer pr…