MPC 2025 - Issue 1
This paper focuses on the description and computation of the B-differential of the
componentwise minimum of two affine vector functions. This issue arises in the
reformulation of the linear complementarity problem with the Min C-function. The
question has many equivalent formulations and we identify some of them in linear
algebra, convex analysis and discrete geometry. These formulations are used to state
some properties of the B-differential, like its symmetry, condition for its complete-
ness, its connectivity, bounds on its cardinality, etc. The set to specify has a finite
number of elements, which may grow exponentially with the range space dimension
of the functions, so that its description is most often algorithmic. We first present
an incremental-recursive approach avoiding to solve any optimization subproblem,
unlike several previous approaches. It is based on the notion of matroid circuit and the
related introduced concept of stem vector. Next, we propose modifications, adapted
to the problem at stake, of an algorithm introduced by Rada and ˇCerný (SIAM J Dis-
cret Math 32(1):455-473, 2018, https://doi.org/10.1137/15M1027930) to determine
the cells of an arrangement in the space of hyperplanes having a point in common.
Measured in CPU time on the considered test-problems, the mean acceleration ratios
of the proposed algorithms, with respect to the one of Rada and ˇCerný, are in the range
15..31, and this speed-up can exceed 100, depending on the problem, the approach
and the chosen linear optimization and matroid solvers.
In this paper we consider regression problems subject to noise in the operator or design matrix. This characterization appropriately models many physical phenomena with uncertainty in the regressors. Although the problem has been studied extensively for ordinary/total least squares, and via models that implicitly or explicitly assume Gaussianity, less attention has been paid to improving estimation for regression problems under general independent component-wise uncertainty in the design matrix. To address difficulties encountered when dealing with distributions of sums of random variables, we rely on the saddle point method to estimate densities and form an approximate log-likelihood to maximize. We show that the proposed method performs favorably against other classical methods.
In this paper we introduce an open-source software package written in C++ for efficiently finding solutions to quadratic programming problems with linear complementarity constraints. These problems arise in a wide range of applications in engineering and economics, and they are challenging to solve due to their structural violation of standard constraint qualifications, and highly nonconvex, nonsmooth feasible sets. This work extends a previously presented algorithm based on a sequential convex programming approach applied to a standard penalty reformulation. We examine the behavior of local convergence and introduce new algorithmic features. Competitive performance profiles are presented in comparison to state-of-the-art solvers and solution variants in both existing and new benchmarks.
We describe a diving heuristic framework based on constraint propagation for mixed integer linear programs. The proposed approach is an extension of the common fix-and-propagate scheme, with the addition of solution repairing after each step. The repair logic is loosely based on the WalkSAT strategy for boolean satisfiability. Different strategies for variable ranking and value selection, as well as other options, yield different diving heuristics. The overall method is relatively inexpensive, as it is basically LP-free: the full linear programming relaxation is solved only at the beginning (and only for the ranking strategies that make use of it), while additional, typically much smaller, LPs are only used to compute values for the continuous variables (if any), once at the bottom of a dive. While individual strategies are not very robust in finding feasible solutions on a heterogeneous testbed, a portfolio approach proved quite effective. In particular, it could consistently find feasible solutions in 189 out of 240 instances from the public MIPLIB 2017 benchmark testbed, in a matter of a few seconds of runtime. The framework has also been implemented inside the commercial MIP solver Xpress and shown to give a small performance improvement in time to optimality on a large internal heterogeneous testbed.
This paper considers a single machine identical-jobs order scheduling problem with
a position-dependent learning effect (SIOSLE) to minimize the total tardiness. A
learning effect is common in the identical-jobs order manufacturing, such as clothing,
bicycles, shoes, and so on, but its impact on the order scheduling problem has
not been studied, especially for orders with different numbers of the same type of
jobs. A mixed integer programming (MIP) model is first formulated for SIOSLE and
serves as a benchmark. A new branch-and-bound algorithm was developed to handle
computational complexity based on the Dominance, Split, Elimination, and Decomposition
rules revised from the traditional job scheduling problem and new lower
and upper bounds. Numerical experiments demonstrate that the proposed branch-andbound
algorithm is computationally better than the performance of using Gurobi, a
popular commercial solver, to solve the MIP. The experiments for large-sized problems
found that the proposed branch-and-bound algorithm can solve instances with
up to 120 orders. The algorithm is more efficient for instances with a strong or weak
learning effect, with tight or loose due dates, or with heterogeneous due dates. The
effectiveness of the Dominance, Split, Elimination, and Decomposition rules varies
with parameter settings. In addition, the proposed branch-and-bound algorithm can
yield better solutions than traditional meta-heuristic algorithms butmay require longer
run time for large instances.