Interior Point Method on Semi-definite Linear Complementarity Problems using the Nesterov-Todd (NT) Search Direction: Polynomial Complexity and Local Convergence

We consider in this paper an infeasible predictor-corrector primal-dual path following interior point algorithm using the Nesterov-Todd (NT) search direction to solve semi-definite linear complementarity problems. Global convergence and polynomial iteration complexity of the algorithm are established. Two sufficient conditions are also given for superlinear convergence of iterates generated by the algorithm. Preliminary numerical results … Read more

Tangencies and Polynomial Optimization

Given a polynomial function $f \colon \mathbb{R}^n \rightarrow \mathbb{R}$ and a unbounded basic closed semi-algebraic set $S \subset \mathbb{R}^n,$ in this paper we show that the conditions listed below are characterized exactly in terms of the so-called {\em tangency variety} of $f$ on $S$: (i) The $f$ is bounded from below on $S;$ (ii) The … Read more

Identifying the Optimal Value Function of a Negative Markov Decision Process: An Integer Programming Approach

Mathematical programming formulation to identify the optimal value function of a negative Markov decision process (MDP) is non-convex, non-smooth, and computationally intractable. Also note that other well-known solution methods of MDP do not work properly for a negative MDP. More specifically, the policy iteration diverges, and the value iteration converges but does not provide an … Read more

Minimum Color-Degree Perfect b -Matchings

The minimum color-degree perfect b-matching roblem (Col-BM) is a new extension of the perfect b-matching problem to edge-colored graphs. The objective of Col-BM is to minimize the maximum number of differently colored edges in a perfect b-matching that are incident to the same node. We show that Col-BM is NP-hard on bipartite graphs by a … Read more

Algorithms for the circle packing problem based on mixed-integer DC programming

Circle packing problems are a class of packing problems which attempt to pack a given set of circles into a container with no overlap. In this paper, we focus on the circle packing problem proposed by L{\’o}pez The problem is to pack circles of unequal size into a fixed size circular container, so as … Read more

Single cut and multicut SDDP with cut selection for multistage stochastic linear programs: convergence proof and numerical experiments

We introduce a variant of Multicut Decomposition Algorithms (MuDA), called CuSMuDA (Cut Selection for Multicut Decomposition Algorithms), for solving multistage stochastic linear programs that incorporates a class of cut selection strategies to choose the most relevant cuts of the approximate recourse functions. This class contains Level 1 and Limited Memory Level 1 cut selection strategies, … Read more

An Adaptive Sequential Sample Average Approximation Framework for Solving Two-stage Stochastic Programs

We present adaptive sequential SAA (sample average approximation) algorithms to solve large-scale two-stage stochastic linear programs. The iterative algorithm framework we propose is organized into \emph{outer} and \emph{inner} iterations as follows: during each outer iteration, a sample-path problem is implicitly generated using a sample of observations or “scenarios,” and solved only \emph{imprecisely}, to within a … Read more

Improved Flow-based Formulations for the Skiving Stock Problem

Thanks to the rapidly advancing development of (commercial) MILP software and hardware components, pseudo-polynomial formulations have been established as a powerful tool for solving cutting and packing problems in recent years. In this paper, we focus on the one-dimensional skiving stock problem (SSP), where a given inventory of small items has to be recomposed to … Read more

Optimal Residential Battery Storage Operations Using Robust Data-driven Dynamic Programming

In this paper, we consider the problem of operating a battery storage unit in a home with a rooftop solar photovoltaic (PV) system so as to minimize expected long-run electricity costs under uncertain electricity usage, PV generation, and electricity prices. Solving this dynamic program using standard techniques is computationally burdensome, and is often complicated by … Read more

Conflict-Driven Heuristics for Mixed Integer Programming

Two essential ingredients of modern mixed-integer programming (MIP) solvers are diving heuristics that simulate a partial depth-first search in a branch-and-bound search tree and conflict analysis of infeasible subproblems to learn valid constraints. So far, these techniques have mostly been studied independently: primal heuristics under the aspect of finding high-quality feasible solutions early during the … Read more