Open Journal of Mathematical Optimization

This is the home page of the Open Journal of Mathematical Optimization, an electronic journal of computer science and mathematics owned by its Editorial Board.

The Open Journal of Mathematical Optimization (OJMO) publishes original and high-quality articles dealing with every aspect of mathematical optimization, ranging from numerical and computational aspects to the theoretical questions related to mathematical optimization problems. The topics covered by the journal are classified into four areas:

1. Continuous Optimization
2. Discrete Optimization
3. Optimization under Uncertainty
4. Computational aspects and applications

The journal publishes high-quality articles in open access free of charge, meaning that neither the authors nor the readers have to pay to access the content of the published papers, thus adhering to the principles of Fair Open Access. The journal supports open data and open code whenever possible and authors are strongly encouraged to submit code and data sets along with their manuscript.

Memberships and Indexing

e-ISSN : 2777-5860

Gradient formulae for probability functions depending on a heterogenous family of constraints

Probability functions measure the degree of satisfaction of certain constraints that are impacted by decisions and uncertainty. Such functions appear in probability or chance constraints ensuring that the degree of satisfaction is sufficiently high. These constraints have become a very popular modelling tool and are indeed intuitively easy to understand. Optimization problems involving probabilistic constraints have thus arisen in many sectors of the industry, such as in the energy sector. Finding an efficient solution methodology is important and first order information of probability functions play a key role therein. In this work we are motivated by probability functions measuring the degree of satisfaction of a potentially heterogenous family of constraints. We suggest a framework wherein each individual such constraint can be analyzed structurally. Our framework then allows us to establish formulae for the generalized subdifferential of the probability function itself. In particular we formally establish a (sub)-gradient formulæ for probability functions depending on a family of non-convex quadratic inequalities. The latter situation is relevant for gas-network applications.

Available online:

The Referenced Vertex Ordering Problem: Theory, Applications, and Solution Methods

We introduce the referenced vertex ordering problem (revorder) as a combinatorial decision problem generalizing several vertex ordering problems that already appeared in the scientific literature under different guises. In other words, revorder is a generic problem with several possible extensions corresponding to various real-life applications. Given a simple undirected graph $G=\left(V,E\right)$, revorder basically asks whether the vertices of $G$ can be sorted in a way to guarantee that every vertex is adjacent to a minimal number of its predecessors in the order. Previous works show that revorder, as well as its optimization counterpart, denoted in our work as min revorder, are NP-hard. We give a survey of methods and algorithms that can be applied to the solution of min revorder, and we develop a new enumeration scheme for its solution. Our theoretical analysis of this scheme yields several pruning techniques aimed at the reduction of the number of enumeration nodes. We then discuss how upper and lower bounds can be computed during the enumeration to design a branch-and-bound algorithm. Finally, we validate our branch-and-bound algorithm by conducting a large set of computational experiments on instances coming from various real-life applications. Our results highlight that the newly introduced pruning techniques allow the computation of good-quality solutions (in comparison with other solver’s solutions) while reducing the overall computational cost. Our branch-and-bound outperforms other existing solution methods: among 180 instances with 60 vertices, it solves 179 instances to optimality whereas the best existing method is only able to solve 109 of them. Moreover, our tests show that our algorithm can solve medium-scale instances up to 500 vertices, which opens the perspective of handling new real-life problems. Our implementation of the branch-and-bound algorithm, together with all instances we have used, is publicly available on GitLabGitLab repository: https://gitlab.insa-rennes.fr/Jeremy.Omer/min-revorder.git.

Available online: