This article presents
BiqCrunch
, an exact solver for binary quadratic optimization problems.
BiqCrunch
is a branch-and-bound method that uses an original, efficient semidefinite-optimization-based ...bounding procedure. It has been successfully tested on a variety of well-known combinatorial optimization problems, such as Max-Cut, Max-
k
-Cluster, and Max-Independent-Set. The code is publicly available online; a web interface and many conversion tools are also provided.
We present BiqBin, an exact solver for linearly constrained binary quadratic problems. Our approach is based on an exact penalty method to first efficiently transform the original problem into an ...instance of Max-Cut, and then to solve the Max-Cut problem by a branch-and-bound algorithm. All the main ingredients are carefully developed using new semidefinite programming relaxations obtained by strengthening the existing relaxations with a set of hypermetric inequalities, applying the bundle method as the bounding routine and using new strategies for exploring the branch-and-bound tree.Furthermore, an efficient C implementation of a sequential and a parallel branch-and-bound algorithm is presented. The latter is based on a load coordinator-worker scheme using MPI for multi-node parallelization and is evaluated on a high-performance computer.The new solver is benchmarked against BiqCrunch, GUROBI, and SCIP on four families of (linearly constrained) binary quadratic problems. Numerical results demonstrate that BiqBin is a highly competitive solver. The serial version outperforms the other three solvers on the majority of the benchmark instances. We also evaluate the parallel solver and show that it has good scaling properties. The general audience can use it as an on-line service available at http://www.biqbin.eu.
Daily fantasy sports (DFS) is a multibillion-dollar industry with millions of annual users and widespread appeal among sports fans across a broad range of popular sports. Building on recent work, we ...provide a coherent framework for constructing DFS portfolios where we explicitly model the behavior of other DFS players. We formulate an optimization problem that accurately describes the DFS problem for a risk-neutral decision maker in both double-up and top-heavy payoff settings. Our formulation maximizes the expected reward subject to feasibility constraints, and we relate this formulation to mean-variance optimization and the outperformance of stochastic benchmarks. Using this connection, we show how the problem can be reduced to the problem of solving a series of binary quadratic programs. We also propose an algorithm for solving the problem where the decision maker can submit multiple entries to the DFS contest. This algorithm is motivated by submodularity properties of the objective function and by some new results on parimutuel betting. One of the contributions of our work is the introduction of a Dirichlet-multinomial data-generating process for modeling opponents’ team selections, and we estimate the parameters of this model via Dirichlet regressions. A further benefit to modeling opponents’ team selections is that it enables us to estimate the value, in a DFS setting, of both insider trading and collusion. We demonstrate the value of our framework by applying it to DFS contests during the 2017 National Football League season.
This paper was accepted by Baris Ata, stochastic models and simulation
.
The purpose of this paper is the approach of a mathematical model dedicated to planning the consecutive days off of a company’s employees. Companies must find a flexible work schedule between ...employees, always considering the satisfaction of work tasks as well as guaranteeing consecutive days off. The analysis is based on solving a quadratic programming problem with binary variables. The proposed method uses the properties of the circulant symmetric matrix in the researched model, which allows the transformation of the considered problems into an equivalent separable non-convex optimization problem. A practical continuous convex relaxation approach is proposed. DC Algorithm is used to solve relaxed problems. A solved numerical example is presented.
This paper describes a new instance library for quadratic programming (QP), i.e., the family of continuous and (mixed)-integer optimization problems where the objective function and/or the ...constraints are quadratic. QP is a very diverse class of problems, comprising sub-classes ranging from trivial to undecidable. This diversity is reflected in the variety of QP solution methods, ranging from entirely combinatorial approaches to completely continuous algorithms, including many methods for which both aspects are fundamental. Selecting a set of instances of QP that is at the same time not overwhelmingly onerous but sufficiently challenging for the different, interested communities is therefore important. We propose a simple taxonomy for QP instances leading to a systematic problem selection mechanism. We then briefly survey the field of QP, giving an overview of theory, methods and solvers. Finally, we describe how the library was put together, and detail its final contents.
We propose an entropy regularized splitting model using low-rank factorization for solving binary quadratic programming with linear inequality constraints. Different from the semidefinite programming ...relaxation model, our model preserves the rank-one constraint and aims to find high quality rank-one solutions directly. The factorization transforms the variables into low-rank matrices, while the entropy term enforces the low-rank property of the splitting variable . A customized alternating direction method of multipliers is utilized to solve the proposed model. Specifically, our method uses the augmented Lagrangian function to deal with inequality constraints, and solves one subproblem on the oblique manifold by a regularized Newton method. Numerical results on the multiple-input multiple-output detection problem, the maxcut problem and the quadratic
0
-
1
problem indicate that our proposed algorithm has advantage over the SDP methods.
Testing a given matrix for membership in the family of Bernoulli matrices is a long-standing problem; the many applications of Bernoulli vectors in computer science, finance, medicine, and operations ...research emphasize its practical relevance. After the three-variate case was covered by Chaganty and Joe (2006) by means of partial correlations, a novel approach towards this problem was taken by Fiebig et al. (2017) for low-dimensional settings, i.e., d≤6. The latter authors were the first to exploit the close relationship between the probabilistic world of Bernoulli matrices and the well-studied correlation and cut polytopes. Inspired by this approach, we use results from Deza and Laurent (1997), Embrechts et al. (2016), and Fiebig et al. (2017) in a pre-phase of a novel algorithm to check necessary as well as sufficient conditions, before actually testing a matrix for Bernoulli compatibility. In our main approach, however, we build upon an early attempt by Lee (1993) based on the vertex representation of the correlation polytope and directly solve the corresponding linear program. To deal appropriately with the issue of exponentially many primal variables, we propose a specifically tailored column generation method. A straightforward, yet novel, analysis of the arising subproblem of determining the most violated dual constraint in the column generation process leads to an exact algorithm for membership testing. Although the membership problem is known to be NP-complete, we observe very promising performance up to dimension d=40 on a broad variety of test problems. An important byproduct of the numerical solution is a representation for Bernoulli matrices with (only) d2 many vertices that gives rise to an efficient simulation routine.
Local binary pattern (LBP) and its variants have shown promising results in visual recognition applications. However, most existing approaches rely on a pre-defined structure to extract LBP features. ...We argue that the optimal LBP structure should be task-dependent and propose a new method to learn discriminative LBP structures. We formulate it as a point selection problem: Given a set of point candidates, the goal is to select an optimal subset to compose the LBP structure. In view of the problems of current feature selection algorithms, we propose a novel Maximal Joint Mutual Information criterion. Then, the point selection is converted into a binary quadratic programming problem and solved efficiently via the branch and bound algorithm. The proposed LBP structures demonstrate superior performance to the state-of-the-art approaches on classifying both spatial patterns in scene recognition and spatial-temporal patterns in dynamic texture recognition.
This paper considers the problem of radar target detection in compound Gaussian clutter background. Different from the existing detector design criteria, we firstly study the detection problem by ...introducing an auxiliary variable, as a consequence, the detection problem is recast into a binary quadratic programming (BQP) problem. Considering the binary nature of the auxiliary variable, we apply the relaxation algorithm to solve the BQP problem and propose a new detection scheme for the detection problem. Finally, simulation experiments are performed to verify the effectiveness of the proposed detector in comparison with several state-of-the-art detectors.
In this study, we deal with the problem of scheduling charging periods of electrical vehicles (EVs) to satisfy the users’ demands for energy consumption as well as to optimally utilize the available ...power. We assume three-phase EV charging stations, each equipped with two charging ports (links) that can serve up to two EVs in the scheduling period but not simultaneously. Considering such a specification, we propose an on–off scheduling scheme wherein control over an energy flow is achieved by flexibly switching the ports in each station on and off in a manner such as to satisfy the energy demand of each EV, flatten the high energy-consuming load on the whole farm, and to minimize the number of switching operations. To satisfy these needs, the on–off scheduling scheme is formulated in terms of a binary linear programming problem, which is then extended to a quadratic version to incorporate the smoothness constraints. Various algorithmic approaches are used for solving a binary quadratic programming problem, including the Frank–Wolfe algorithm and successive linear approximations. The numerical simulations demonstrate that the latter is scalable, efficient, and flexible in a charging procedure, and it shaves the load peak while maintaining smooth charging profiles.
PDF
