Optimization ( scipy.optimize ) #

The scipy.optimize package provides several commonly used optimization algorithms. A detailed listing is available: scipy.optimize (can also be found by help(scipy.optimize) ).

Unconstrained minimization of multivariate scalar functions ( minimize ) #

The minimize function provides a common interface to unconstrained and constrained minimization algorithms for multivariate scalar functions in scipy.optimize . To demonstrate the minimization function, consider the problem of minimizing the Rosenbrock function of \(N\) variables:

The minimum value of this function is 0 which is achieved when \(x_{i}=1.\)

Note that the Rosenbrock function and its derivatives are included in scipy.optimize . The implementations shown in the following sections provide examples of how to define an objective function as well as its jacobian and hessian functions. Objective functions in scipy.optimize expect a numpy array as their first parameter which is to be optimized and must return a float value. The exact calling signature must be f(x, *args) where x represents a numpy array and args a tuple of additional arguments supplied to the objective function.

Nelder-Mead Simplex algorithm ( method='Nelder-Mead' ) #

In the example below, the minimize routine is used with the Nelder-Mead simplex algorithm (selected through the method parameter):

The simplex algorithm is probably the simplest way to minimize a fairly well-behaved function. It requires only function evaluations and is a good choice for simple minimization problems. However, because it does not use any gradient evaluations, it may take longer to find the minimum.

Another optimization algorithm that needs only function calls to find the minimum is Powell ’s method available by setting method='powell' in minimize .

To demonstrate how to supply additional arguments to an objective function, let us minimize the Rosenbrock function with an additional scaling factor a and an offset b :

Again using the minimize routine this can be solved by the following code block for the example parameters a=0.5 and b=1 .

As an alternative to using the args parameter of minimize , simply wrap the objective function in a new function that accepts only x . This approach is also useful when it is necessary to pass additional parameters to the objective function as keyword arguments.

Another alternative is to use functools.partial .

Broyden-Fletcher-Goldfarb-Shanno algorithm ( method='BFGS' ) #

In order to converge more quickly to the solution, this routine uses the gradient of the objective function. If the gradient is not given by the user, then it is estimated using first-differences. The Broyden-Fletcher-Goldfarb-Shanno (BFGS) method typically requires fewer function calls than the simplex algorithm even when the gradient must be estimated.

To demonstrate this algorithm, the Rosenbrock function is again used. The gradient of the Rosenbrock function is the vector:

This expression is valid for the interior derivatives. Special cases are

A Python function which computes this gradient is constructed by the code-segment:

This gradient information is specified in the minimize function through the jac parameter as illustrated below.

Avoiding Redundant Calculation #

It is common for the objective function and its gradient to share parts of the calculation. For instance, consider the following problem.

Here, expensive is called 12 times: six times in the objective function and six times from the gradient. One way of reducing redundant calculations is to create a single function that returns both the objective function and the gradient.

When we call minimize, we specify jac==True to indicate that the provided function returns both the objective function and its gradient. While convenient, not all scipy.optimize functions support this feature, and moreover, it is only for sharing calculations between the function and its gradient, whereas in some problems we will want to share calculations with the Hessian (second derivative of the objective function) and constraints. A more general approach is to memoize the expensive parts of the calculation. In simple situations, this can be accomplished with the functools.lru_cache wrapper.

Newton-Conjugate-Gradient algorithm ( method='Newton-CG' ) #

Newton-Conjugate Gradient algorithm is a modified Newton’s method and uses a conjugate gradient algorithm to (approximately) invert the local Hessian [NW] . Newton’s method is based on fitting the function locally to a quadratic form:

where \(\mathbf{H}\left(\mathbf{x}_{0}\right)\) is a matrix of second-derivatives (the Hessian). If the Hessian is positive definite then the local minimum of this function can be found by setting the gradient of the quadratic form to zero, resulting in

The inverse of the Hessian is evaluated using the conjugate-gradient method. An example of employing this method to minimizing the Rosenbrock function is given below. To take full advantage of the Newton-CG method, a function which computes the Hessian must be provided. The Hessian matrix itself does not need to be constructed, only a vector which is the product of the Hessian with an arbitrary vector needs to be available to the minimization routine. As a result, the user can provide either a function to compute the Hessian matrix, or a function to compute the product of the Hessian with an arbitrary vector.

Full Hessian example: #

The Hessian of the Rosenbrock function is

if \(i,j\in\left[1,N-2\right]\) with \(i,j\in\left[0,N-1\right]\) defining the \(N\times N\) matrix. Other non-zero entries of the matrix are

For example, the Hessian when \(N=5\) is

The code which computes this Hessian along with the code to minimize the function using Newton-CG method is shown in the following example:

Hessian product example: #

For larger minimization problems, storing the entire Hessian matrix can consume considerable time and memory. The Newton-CG algorithm only needs the product of the Hessian times an arbitrary vector. As a result, the user can supply code to compute this product rather than the full Hessian by giving a hess function which take the minimization vector as the first argument and the arbitrary vector as the second argument (along with extra arguments passed to the function to be minimized). If possible, using Newton-CG with the Hessian product option is probably the fastest way to minimize the function.

In this case, the product of the Rosenbrock Hessian with an arbitrary vector is not difficult to compute. If \(\mathbf{p}\) is the arbitrary vector, then \(\mathbf{H}\left(\mathbf{x}\right)\mathbf{p}\) has elements:

Code which makes use of this Hessian product to minimize the Rosenbrock function using minimize follows:

According to [NW] p. 170 the Newton-CG algorithm can be inefficient when the Hessian is ill-conditioned because of the poor quality search directions provided by the method in those situations. The method trust-ncg , according to the authors, deals more effectively with this problematic situation and will be described next.

Trust-Region Newton-Conjugate-Gradient Algorithm ( method='trust-ncg' ) #

The Newton-CG method is a line search method: it finds a direction of search minimizing a quadratic approximation of the function and then uses a line search algorithm to find the (nearly) optimal step size in that direction. An alternative approach is to, first, fix the step size limit \(\Delta\) and then find the optimal step \(\mathbf{p}\) inside the given trust-radius by solving the following quadratic subproblem:

The solution is then updated \(\mathbf{x}_{k+1} = \mathbf{x}_{k} + \mathbf{p}\) and the trust-radius \(\Delta\) is adjusted according to the degree of agreement of the quadratic model with the real function. This family of methods is known as trust-region methods. The trust-ncg algorithm is a trust-region method that uses a conjugate gradient algorithm to solve the trust-region subproblem [NW] .

Trust-Region Truncated Generalized Lanczos / Conjugate Gradient Algorithm ( method='trust-krylov' ) #

Similar to the trust-ncg method, the trust-krylov method is a method suitable for large-scale problems as it uses the hessian only as linear operator by means of matrix-vector products. It solves the quadratic subproblem more accurately than the trust-ncg method.

This method wraps the [TRLIB] implementation of the [GLTR] method solving exactly a trust-region subproblem restricted to a truncated Krylov subspace. For indefinite problems it is usually better to use this method as it reduces the number of nonlinear iterations at the expense of few more matrix-vector products per subproblem solve in comparison to the trust-ncg method.

F. Lenders, C. Kirches, A. Potschka: “trlib: A vector-free implementation of the GLTR method for iterative solution of the trust region problem”, arXiv:1611.04718

N. Gould, S. Lucidi, M. Roma, P. Toint: “Solving the Trust-Region Subproblem using the Lanczos Method”, SIAM J. Optim., 9(2), 504–525, (1999). DOI:10.1137/S1052623497322735

Trust-Region Nearly Exact Algorithm ( method='trust-exact' ) #

All methods Newton-CG , trust-ncg and trust-krylov are suitable for dealing with large-scale problems (problems with thousands of variables). That is because the conjugate gradient algorithm approximately solve the trust-region subproblem (or invert the Hessian) by iterations without the explicit Hessian factorization. Since only the product of the Hessian with an arbitrary vector is needed, the algorithm is specially suited for dealing with sparse Hessians, allowing low storage requirements and significant time savings for those sparse problems.

For medium-size problems, for which the storage and factorization cost of the Hessian are not critical, it is possible to obtain a solution within fewer iteration by solving the trust-region subproblems almost exactly. To achieve that, a certain nonlinear equations is solved iteratively for each quadratic subproblem [CGT] . This solution requires usually 3 or 4 Cholesky factorizations of the Hessian matrix. As the result, the method converges in fewer number of iterations and takes fewer evaluations of the objective function than the other implemented trust-region methods. The Hessian product option is not supported by this algorithm. An example using the Rosenbrock function follows:

J. Nocedal, S.J. Wright “Numerical optimization.” 2nd edition. Springer Science (2006).

Conn, A. R., Gould, N. I., & Toint, P. L. “Trust region methods”. Siam. (2000). pp. 169-200.

Constrained minimization of multivariate scalar functions ( minimize ) #

The minimize function provides algorithms for constrained minimization, namely 'trust-constr' , 'SLSQP' and 'COBYLA' . They require the constraints to be defined using slightly different structures. The method 'trust-constr' requires the constraints to be defined as a sequence of objects LinearConstraint and NonlinearConstraint . Methods 'SLSQP' and 'COBYLA' , on the other hand, require constraints to be defined as a sequence of dictionaries, with keys type , fun and jac .

As an example let us consider the constrained minimization of the Rosenbrock function:

This optimization problem has the unique solution \([x_0, x_1] = [0.4149,~ 0.1701]\) , for which only the first and fourth constraints are active.

Trust-Region Constrained Algorithm ( method='trust-constr' ) #

The trust-region constrained method deals with constrained minimization problems of the form:

When \(c^l_j = c^u_j\) the method reads the \(j\) -th constraint as an equality constraint and deals with it accordingly. Besides that, one-sided constraint can be specified by setting the upper or lower bound to np.inf with the appropriate sign.

The implementation is based on [EQSQP] for equality-constraint problems and on [TRIP] for problems with inequality constraints. Both are trust-region type algorithms suitable for large-scale problems.

Defining Bounds Constraints: #

The bound constraints \(0 \leq x_0 \leq 1\) and \(-0.5 \leq x_1 \leq 2.0\) are defined using a Bounds object.

Defining Linear Constraints: #

The constraints \(x_0 + 2 x_1 \leq 1\) and \(2 x_0 + x_1 = 1\) can be written in the linear constraint standard format:

and defined using a LinearConstraint object.

Defining Nonlinear Constraints: #

The nonlinear constraint:

with Jacobian matrix:

and linear combination of the Hessians:

is defined using a NonlinearConstraint object.

Alternatively, it is also possible to define the Hessian \(H(x, v)\) as a sparse matrix,

or as a LinearOperator object.

When the evaluation of the Hessian \(H(x, v)\) is difficult to implement or computationally infeasible, one may use HessianUpdateStrategy . Currently available strategies are BFGS and SR1 .

Alternatively, the Hessian may be approximated using finite differences.

The Jacobian of the constraints can be approximated by finite differences as well. In this case, however, the Hessian cannot be computed with finite differences and needs to be provided by the user or defined using HessianUpdateStrategy .

Solving the Optimization Problem: #

The optimization problem is solved using:

When needed, the objective function Hessian can be defined using a LinearOperator object,

or a Hessian-vector product through the parameter hessp .

Alternatively, the first and second derivatives of the objective function can be approximated. For instance, the Hessian can be approximated with SR1 quasi-Newton approximation and the gradient with finite differences.

Byrd, Richard H., Mary E. Hribar, and Jorge Nocedal. 1999. An interior point algorithm for large-scale nonlinear programming. SIAM Journal on Optimization 9.4: 877-900.

Lalee, Marucha, Jorge Nocedal, and Todd Plantega. 1998. On the implementation of an algorithm for large-scale equality constrained optimization. SIAM Journal on Optimization 8.3: 682-706.

Sequential Least SQuares Programming (SLSQP) Algorithm ( method='SLSQP' ) #

The SLSQP method deals with constrained minimization problems of the form:

Where \(\mathcal{E}\) or \(\mathcal{I}\) are sets of indices containing equality and inequality constraints.

Both linear and nonlinear constraints are defined as dictionaries with keys type , fun and jac .

And the optimization problem is solved with:

Most of the options available for the method 'trust-constr' are not available for 'SLSQP' .

Global optimization #

Global optimization aims to find the global minimum of a function within given bounds, in the presence of potentially many local minima. Typically, global minimizers efficiently search the parameter space, while using a local minimizer (e.g., minimize ) under the hood. SciPy contains a number of good global optimizers. Here, we’ll use those on the same objective function, namely the (aptly named) eggholder function:

This function looks like an egg carton:

"A 3-D plot shown from a three-quarter view. The function is very noisy with dozens of valleys and peaks. There is no clear min or max discernible from this view and it's not possible to see all the local peaks and valleys from this view."

We now use the global optimizers to obtain the minimum and the function value at the minimum. We’ll store the results in a dictionary so we can compare different optimization results later.

All optimizers return an OptimizeResult , which in addition to the solution contains information on the number of function evaluations, whether the optimization was successful, and more. For brevity, we won’t show the full output of the other optimizers:

shgo has a second method, which returns all local minima rather than only what it thinks is the global minimum:

We’ll now plot all found minima on a heatmap of the function:

"This X-Y plot is a heatmap with the Z value denoted with the lowest points as black and the highest values as white. The image resembles a chess board rotated 45 degrees but heavily smoothed. A red dot is located at many of the minima on the grid resulting from the SHGO optimizer. SHGO shows the global minima as a red X in the top right. A local minima found with dual annealing is a white circle marker in the top left. A different local minima found with basinhopping is a yellow marker in the top center. The code is plotting the differential evolution result as a cyan circle, but it is not visible on the plot. At a glance it's not clear which of these valleys is the true global minima."

Least-squares minimization ( least_squares ) #

SciPy is capable of solving robustified bound-constrained nonlinear least-squares problems:

Here \(f_i(\mathbf{x})\) are smooth functions from \(\mathbb{R}^n\) to \(\mathbb{R}\) , we refer to them as residuals. The purpose of a scalar-valued function \(\rho(\cdot)\) is to reduce the influence of outlier residuals and contribute to robustness of the solution, we refer to it as a loss function. A linear loss function gives a standard least-squares problem. Additionally, constraints in a form of lower and upper bounds on some of \(x_j\) are allowed.

All methods specific to least-squares minimization utilize a \(m \times n\) matrix of partial derivatives called Jacobian and defined as \(J_{ij} = \partial f_i / \partial x_j\) . It is highly recommended to compute this matrix analytically and pass it to least_squares , otherwise, it will be estimated by finite differences, which takes a lot of additional time and can be very inaccurate in hard cases.

Function least_squares can be used for fitting a function \(\varphi(t; \mathbf{x})\) to empirical data \(\{(t_i, y_i), i = 0, \ldots, m-1\}\) . To do this, one should simply precompute residuals as \(f_i(\mathbf{x}) = w_i (\varphi(t_i; \mathbf{x}) - y_i)\) , where \(w_i\) are weights assigned to each observation.

Example of solving a fitting problem #

Here we consider an enzymatic reaction [ 1 ] . There are 11 residuals defined as

where \(y_i\) are measurement values and \(u_i\) are values of the independent variable. The unknown vector of parameters is \(\mathbf{x} = (x_0, x_1, x_2, x_3)^T\) . As was said previously, it is recommended to compute Jacobian matrix in a closed form:

We are going to use the “hard” starting point defined in [ 2 ] . To find a physically meaningful solution, avoid potential division by zero and assure convergence to the global minimum we impose constraints \(0 \leq x_j \leq 100, j = 0, 1, 2, 3\) .

The code below implements least-squares estimation of \(\mathbf{x}\) and finally plots the original data and the fitted model function:

"This code plots an X-Y time-series. The series starts in the lower left at (0, 0) and rapidly trends up to the maximum of 0.2 then flattens out. The fitted model is shown as a smooth orange trace and is well fit to the data."

Further examples #

Three interactive examples below illustrate usage of least_squares in greater detail.

Large-scale bundle adjustment in scipy demonstrates large-scale capabilities of least_squares and how to efficiently compute finite difference approximation of sparse Jacobian.

Robust nonlinear regression in scipy shows how to handle outliers with a robust loss function in a nonlinear regression.

Solving a discrete boundary-value problem in scipy examines how to solve a large system of equations and use bounds to achieve desired properties of the solution.

For the details about mathematical algorithms behind the implementation refer to documentation of least_squares .

Univariate function minimizers ( minimize_scalar ) #

Often only the minimum of an univariate function (i.e., a function that takes a scalar as input) is needed. In these circumstances, other optimization techniques have been developed that can work faster. These are accessible from the minimize_scalar function, which proposes several algorithms.

Unconstrained minimization ( method='brent' ) #

There are, actually, two methods that can be used to minimize an univariate function: brent and golden , but golden is included only for academic purposes and should rarely be used. These can be respectively selected through the method parameter in minimize_scalar . The brent method uses Brent’s algorithm for locating a minimum. Optimally, a bracket (the bracket parameter) should be given which contains the minimum desired. A bracket is a triple \(\left( a, b, c \right)\) such that \(f \left( a \right) > f \left( b \right) < f \left( c \right)\) and \(a < b < c\) . If this is not given, then alternatively two starting points can be chosen and a bracket will be found from these points using a simple marching algorithm. If these two starting points are not provided, 0 and 1 will be used (this may not be the right choice for your function and result in an unexpected minimum being returned).

Here is an example:

Bounded minimization ( method='bounded' ) #

Very often, there are constraints that can be placed on the solution space before minimization occurs. The bounded method in minimize_scalar is an example of a constrained minimization procedure that provides a rudimentary interval constraint for scalar functions. The interval constraint allows the minimization to occur only between two fixed endpoints, specified using the mandatory bounds parameter.

For example, to find the minimum of \(J_{1}\left( x \right)\) near \(x=5\) , minimize_scalar can be called using the interval \(\left[ 4, 7 \right]\) as a constraint. The result is \(x_{\textrm{min}}=5.3314\) :

Custom minimizers #

Sometimes, it may be useful to use a custom method as a (multivariate or univariate) minimizer, for example, when using some library wrappers of minimize (e.g., basinhopping ).

We can achieve that by, instead of passing a method name, passing a callable (either a function or an object implementing a __call__ method) as the method parameter.

Let us consider an (admittedly rather virtual) need to use a trivial custom multivariate minimization method that will just search the neighborhood in each dimension independently with a fixed step size:

This will work just as well in case of univariate optimization:

Root finding #

Scalar functions #.

If one has a single-variable equation, there are multiple different root finding algorithms that can be tried. Most of these algorithms require the endpoints of an interval in which a root is expected (because the function changes signs). In general, brentq is the best choice, but the other methods may be useful in certain circumstances or for academic purposes. When a bracket is not available, but one or more derivatives are available, then newton (or halley , secant ) may be applicable. This is especially the case if the function is defined on a subset of the complex plane, and the bracketing methods cannot be used.

Fixed-point solving #

A problem closely related to finding the zeros of a function is the problem of finding a fixed point of a function. A fixed point of a function is the point at which evaluation of the function returns the point: \(g\left(x\right)=x.\) Clearly, the fixed point of \(g\) is the root of \(f\left(x\right)=g\left(x\right)-x.\) Equivalently, the root of \(f\) is the fixed point of \(g\left(x\right)=f\left(x\right)+x.\) The routine fixed_point provides a simple iterative method using Aitkens sequence acceleration to estimate the fixed point of \(g\) given a starting point.

Sets of equations #

Finding a root of a set of non-linear equations can be achieved using the root function. Several methods are available, amongst which hybr (the default) and lm , which, respectively, use the hybrid method of Powell and the Levenberg-Marquardt method from MINPACK.

The following example considers the single-variable transcendental equation

a root of which can be found as follows:

Consider now a set of non-linear equations

We define the objective function so that it also returns the Jacobian and indicate this by setting the jac parameter to True . Also, the Levenberg-Marquardt solver is used here.

Root finding for large problems #

Methods hybr and lm in root cannot deal with a very large number of variables ( N ), as they need to calculate and invert a dense N x N Jacobian matrix on every Newton step. This becomes rather inefficient when N grows.

Consider, for instance, the following problem: we need to solve the following integrodifferential equation on the square \([0,1]\times[0,1]\) :

with the boundary condition \(P(x,1) = 1\) on the upper edge and \(P=0\) elsewhere on the boundary of the square. This can be done by approximating the continuous function P by its values on a grid, \(P_{n,m}\approx{}P(n h, m h)\) , with a small grid spacing h . The derivatives and integrals can then be approximated; for instance \(\partial_x^2 P(x,y)\approx{}(P(x+h,y) - 2 P(x,y) + P(x-h,y))/h^2\) . The problem is then equivalent to finding the root of some function residual(P) , where P is a vector of length \(N_x N_y\) .

Now, because \(N_x N_y\) can be large, methods hybr or lm in root will take a long time to solve this problem. The solution can, however, be found using one of the large-scale solvers, for example krylov , broyden2 , or anderson . These use what is known as the inexact Newton method, which instead of computing the Jacobian matrix exactly, forms an approximation for it.

The problem we have can now be solved as follows:

"This code generates a 2-D heatmap with Z values from 0 to 1. The graph resembles a smooth, dark blue-green, U shape, with an open yellow top. The right, bottom, and left edges have a value near zero and the top has a value close to 1. The center of the solution space has a value close to 0.8."

Still too slow? Preconditioning. #

When looking for the zero of the functions \(f_i({\bf x}) = 0\) , i = 1, 2, …, N , the krylov solver spends most of the time inverting the Jacobian matrix,

If you have an approximation for the inverse matrix \(M\approx{}J^{-1}\) , you can use it for preconditioning the linear-inversion problem. The idea is that instead of solving \(J{\bf s}={\bf y}\) one solves \(MJ{\bf s}=M{\bf y}\) : since matrix \(MJ\) is “closer” to the identity matrix than \(J\) is, the equation should be easier for the Krylov method to deal with.

The matrix M can be passed to root with method krylov as an option options['jac_options']['inner_M'] . It can be a (sparse) matrix or a scipy.sparse.linalg.LinearOperator instance.

For the problem in the previous section, we note that the function to solve consists of two parts: the first one is the application of the Laplace operator, \([\partial_x^2 + \partial_y^2] P\) , and the second is the integral. We can actually easily compute the Jacobian corresponding to the Laplace operator part: we know that in 1-D

so that the whole 2-D operator is represented by

The matrix \(J_2\) of the Jacobian corresponding to the integral is more difficult to calculate, and since all of it entries are nonzero, it will be difficult to invert. \(J_1\) on the other hand is a relatively simple matrix, and can be inverted by scipy.sparse.linalg.splu (or the inverse can be approximated by scipy.sparse.linalg.spilu ). So we are content to take \(M\approx{}J_1^{-1}\) and hope for the best.

In the example below, we use the preconditioner \(M=J_1^{-1}\) .

Resulting run, first without preconditioning:

and then with preconditioning:

Using a preconditioner reduced the number of evaluations of the residual function by a factor of 4 . For problems where the residual is expensive to compute, good preconditioning can be crucial — it can even decide whether the problem is solvable in practice or not.

Preconditioning is an art, science, and industry. Here, we were lucky in making a simple choice that worked reasonably well, but there is a lot more depth to this topic than is shown here.

Linear programming ( linprog ) #

The function linprog can minimize a linear objective function subject to linear equality and inequality constraints. This kind of problem is well known as linear programming. Linear programming solves problems of the following form:

where \(x\) is a vector of decision variables; \(c\) , \(b_{ub}\) , \(b_{eq}\) , \(l\) , and \(u\) are vectors; and \(A_{ub}\) and \(A_{eq}\) are matrices.

In this tutorial, we will try to solve a typical linear programming problem using linprog .

Linear programming example #

Consider the following simple linear programming problem:

We need some mathematical manipulations to convert the target problem to the form accepted by linprog .

First of all, let’s consider the objective function. We want to maximize the objective function, but linprog can only accept a minimization problem. This is easily remedied by converting the maximize \(29x_1 + 45x_2\) to minimizing \(-29x_1 -45x_2\) . Also, \(x_3, x_4\) are not shown in the objective function. That means the weights corresponding with \(x_3, x_4\) are zero. So, the objective function can be converted to:

If we define the vector of decision variables \(x = [x_1, x_2, x_3, x_4]^T\) , the objective weights vector \(c\) of linprog in this problem should be

Next, let’s consider the two inequality constraints. The first one is a “less than” inequality, so it is already in the form accepted by linprog . The second one is a “greater than” inequality, so we need to multiply both sides by \(-1\) to convert it to a “less than” inequality. Explicitly showing zero coefficients, we have:

These equations can be converted to matrix form:

Next, let’s consider the two equality constraints. Showing zero weights explicitly, these are:

Lastly, let’s consider the separate inequality constraints on individual decision variables, which are known as “box constraints” or “simple bounds”. These constraints can be applied using the bounds argument of linprog . As noted in the linprog documentation, the default value of bounds is (0, None) , meaning that the lower bound on each decision variable is 0, and the upper bound on each decision variable is infinity: all the decision variables are non-negative. Our bounds are different, so we will need to specify the lower and upper bound on each decision variable as a tuple and group these tuples into a list.

Finally, we can solve the transformed problem using linprog .

The result states that our problem is infeasible, meaning that there is no solution vector that satisfies all the constraints. That doesn’t necessarily mean we did anything wrong; some problems truly are infeasible. Suppose, however, that we were to decide that our bound constraint on \(x_1\) was too tight and that it could be loosened to \(0 \leq x_1 \leq 6\) . After adjusting our code x1_bounds = (0, 6) to reflect the change and executing it again:

The result shows the optimization was successful. We can check the objective value ( result.fun ) is same as \(c^Tx\) :

We can also check that all constraints are satisfied within reasonable tolerances:

Assignment problems #

Linear sum assignment problem example #.

Consider the problem of selecting students for a swimming medley relay team. We have a table showing times for each swimming style of five students:

We need to choose a student for each of the four swimming styles such that the total relay time is minimized. This is a typical linear sum assignment problem. We can use linear_sum_assignment to solve it.

The linear sum assignment problem is one of the most famous combinatorial optimization problems. Given a “cost matrix” \(C\) , the problem is to choose

exactly one element from each row

without choosing more than one element from any column

such that the sum of the chosen elements is minimized

In other words, we need to assign each row to one column such that the sum of the corresponding entries is minimized.

Formally, let \(X\) be a boolean matrix where \(X[i,j] = 1\) iff row \(i\) is assigned to column \(j\) . Then the optimal assignment has cost

The first step is to define the cost matrix. In this example, we want to assign each swimming style to a student. linear_sum_assignment is able to assign each row of a cost matrix to a column. Therefore, to form the cost matrix, the table above needs to be transposed so that the rows correspond with swimming styles and the columns correspond with students:

We can solve the assignment problem with linear_sum_assignment :

The row_ind and col_ind are optimal assigned matrix indexes of the cost matrix:

The optimal assignment is:

The optimal total medley time is:

Note that this result is not the same as the sum of the minimum times for each swimming style:

because student “C” is the best swimmer in both “breaststroke” and “butterfly” style. We cannot assign student “C” to both styles, so we assigned student C to the “breaststroke” style and D to the “butterfly” style to minimize the total time.

Some further reading and related software, such as Newton-Krylov [KK] , PETSc [PP] , and PyAMG [AMG] :

D.A. Knoll and D.E. Keyes, “Jacobian-free Newton-Krylov methods”, J. Comp. Phys. 193, 357 (2004). DOI:10.1016/j.jcp.2003.08.010

PETSc https://www.mcs.anl.gov/petsc/ and its Python bindings https://bitbucket.org/petsc/petsc4py/

PyAMG (algebraic multigrid preconditioners/solvers) https://github.com/pyamg/pyamg/issues

Mixed integer linear programming #

Knapsack problem example #.

The knapsack problem is a well known combinatorial optimization problem. Given a set of items, each with a size and a value, the problem is to choose the items that maximize the total value under the condition that the total size is below a certain threshold.

Formally, let

\(x_i\) be a boolean variable that indicates whether item \(i\) is included in the knapsack,

\(n\) be the total number of items,

\(v_i\) be the value of item \(i\) ,

\(s_i\) be the size of item \(i\) , and

\(C\) be the capacity of the knapsack.

Then the problem is:

Although the objective function and inequality constraints are linear in the decision variables \(x_i\) , this differs from a typical linear programming problem in that the decision variables can only assume integer values. Specifically, our decision variables can only be \(0\) or \(1\) , so this is known as a binary integer linear program (BILP). Such a problem falls within the larger class of mixed integer linear programs (MILPs), which we we can solve with milp .

In our example, there are 8 items to choose from, and the size and value of each is specified as follows.

We need to constrain our eight decision variables to be binary. We do so by adding a Bounds : constraint to ensure that they lie between \(0\) and \(1\) , and we apply “integrality” constraints to ensure that they are either \(0\) or \(1\) .

The knapsack capacity constraint is specified using LinearConstraint .

If we are following the usual rules of linear algebra, the input A should be a two-dimensional matrix, and the lower and upper bounds lb and ub should be one-dimensional vectors, but LinearConstraint is forgiving as long as the inputs can be broadcast to consistent shapes.

Using the variables defined above, we can solve the knapsack problem using milp . Note that milp minimizes the objective function, but we want to maximize the total value, so we set c to be negative of the values.

Let’s check the result:

This means that we should select the items 1, 2, 4, 5, 6 to optimize the total value under the size constraint. Note that this is different from we would have obtained had we solved the linear programming relaxation (without integrality constraints) and attempted to round the decision variables.

If we were to round this solution up to array([1., 1., 1., 1., 1., 1., 0., 0.]) , our knapsack would be over the capacity constraint, whereas if we were to round down to array([1., 1., 1., 1., 0., 1., 0., 0.]) , we would have a sub-optimal solution.

For more MILP tutorials, see the Jupyter notebooks on SciPy Cookbooks:

Compressed Sensing l1 program

Compressed Sensing l0 program

exact 1.2.1

pip install exact Copy PIP instructions

Released: Jul 19, 2023

A Python interface to the Exact integer linear programming solver

Project links

View statistics for this project via Libraries.io , or by using our public dataset on Google BigQuery

License: GNU Affero General Public License v3 (AGPL-3.0-only)

Author: Jo Devriendt

Requires: Python >=3.7.0, <4.0.0

Maintainers

Avatar for JoD from gravatar.com

Classifiers

  • OSI Approved :: GNU Affero General Public License v3
  • POSIX :: Linux
  • Python :: 3
  • Python :: 3.7
  • Python :: 3.8
  • Python :: 3.9
  • Python :: 3.10
  • Python :: 3.11

Project description

Exact solves decision and optimization problems formulated as integer linear programs. Under the hood, it converts integer variables to binary (0-1) variables and applies highly efficient propagation routines and strong cutting-planes / pseudo-Boolean conflict analysis.

Exact is a fork of RoundingSat and improves upon its predecessor in reliability, performance and ease-of-use. The name "Exact" reflects that the answers are fully sound, as approximate and floating-point calculations only occur in heuristic parts of the algorithm. As such, Exact can soundly be used for verification and theorem proving, where its envisioned ability to emit machine-checkable certificates of optimality and unsatisfiability should prove useful.

Stay updated

Follow @ExactSolver on Twitter and join the reddit community .

  • Native conflict analysis over binary linear constraints, constructing full-blown cutting planes proofs.
  • Highly efficient watched propagation routines.
  • Seamless use of arbitrary precision arithmetic when needed.
  • Hybrid linear (top-down) and core-guided (bottom-up) optimization.
  • Optional integration with the SoPlex LP solver .
  • Core solver also compiles on macOS and Windows .
  • Under development: Python interface with assumption solving and reuse of solver state (Linux only for now).
  • Under development: generation of certificates of optimality and unsatisfiability that can be automatically verified by VeriPB .

Python interface

Pypi package.

The easiest way is to use an x86_64 machine with Linux operating system. In that case, install this precompiled PyPi package , e.g., by running pip3 install exact .

Compile your own Python package

To use the Exact Python interface with optimal binaries for your machine (and the option to include SoPlex in the binary), compile as a shared library and install it with your package manager (e.g., pip ).

On Linux, this script should do the trick. On other systems, something similar should work. Make sure to have the Boost libraries installed (see dependencies).

Documentation

The header file Exact.hpp contains the C++ methods exposed to Python via cppyy as well as their description. This is probably the place to start to learn about Exact's Python usage.

Next, python/examples contains instructive, fully commented examples.

  • python/examples/knapsack_classic.py showcases how to solve an integer classic knapsack problem with Exact's Python interface.
  • python/examples/knapsack_implied.py elaborates on the first and showcases how to find the variable assignments implied by optimality, i.e., the variable assignments shared by all optimal solutions. A combination of the mechanics of assumption and solution invalidation allow to reuse the existing solver state (containing learned constraints) for optimal performance.
  • python/examples/knapsack_propagate.py elaborates on the second and showcases the builtin propagate method, which returns implied variable bounds under given assumptions.
  • python/examples/ramsey.py tries to compute the infamous Ramsey numbers .
  • python/examples/graph_coloring/graph_coloring.py tries to find the chromatic number of a graph. If you can get Exact to prove the provided graph cannot be colored with 6 colors, contact @JoD ;)

Command line usage

Exact takes as input an integer linear program and outputs a(n optimal) solution or reports that none exists. Either pipe the program

or pass the file as a parameter

Use the flag --help to display a list of runtime parameters.

Exact supports five input formats (described in more detail in InputFormats.md ):

  • .opb pseudo-Boolean PBO (only linear objective and constraints)
  • .cnf DIMACS Conjunctive Normal Form (CNF)
  • .wcnf Weighted Conjunctive Normal Form (WCNF)
  • .mps Mathematical Programming System (MPS) via the optional CoinUtils library
  • .lp Linear Program (LP) via the optional CoinUtils library

Note that .mps and .lp allow rational variables, which are not supported by Exact. Additionally, these formats permit floating point values, which may lead to tricky issues . Rewrite constraints with fractional values to integral ones by multiplying with the lowest common multiple of the denominators.

By default, Exact decides on the format based on the filename extension, but this can be overridden with the --format option.

Compilation

In the root directory of Exact:

For a debug build:

For more builds, similar build directories can be created.

For installing system-wide or to the CMAKE_INSTALL_PREFIX root, use make install .

Dependencies

  • C++17 (i.e., a reasonably recent C++ compiler)
  • Boost library. On a Debian/Ubuntu system, install with sudo apt install libboost-dev .
  • Optionally: CoinUtils library to parse MPS and LP file formats. Use CMake option -Dcoinutils=ON after installing the library .
  • Optionally: SoPlex LP solver (see below).

Exact supports an integration with the LP solver SoPlex to improve its search routine. For this, checkout SoPlex from its git repository as a submodule, compile it in some separate directory, and configure the right CMake options when compiling Exact.

By default, the following commands in Exact's root directory should work with a freshly checked out repository:

The CMake options soplex_src and soplex_build allow to look for SoPlex in a different location.

Exact is licensed under the AGPLv3 . If this would hinder your intended usage, please contact @JoD.

The current set of benchmarks which is used to assess performance is available here .

If you use Exact, please cite this repository and the RoundingSat origin paper (which focuses on cutting planes conflict analysis): [EN18] J. Elffers, J. Nordström. Divide and Conquer: Towards Faster Pseudo-Boolean Solving. IJCAI 2018

When relevant, please cite the following papers as well.

Integration with SoPlex: [DGN20] J. Devriendt, A. Gleixner, J. Nordström. Learn to Relax: Integrating 0-1 Integer Linear Programming with Pseudo-Boolean Conflict-Driven Search. CPAIOR 2020 / Constraints journal

Watched propagation: [D20] J. Devriendt. Watched Propagation for 0-1 Integer Linear Constraints. CP 2020

Core-guided optimization: [DGDNS21] J. Devriendt, S. Gocht, E. Demirović, J. Nordström, P. J. Stuckey. Cutting to the Core of Pseudo-Boolean Optimization: Combining Core-Guided Search with Cutting Planes Reasoning. AAAI 2021

Project details

Release history release notifications | rss feed.

Jul 19, 2023

Jun 26, 2023

Jun 13, 2023

Jun 5, 2023

May 29, 2023

Oct 1, 2022

Apr 20, 2022

Apr 19, 2022

Sep 20, 2021

Aug 24, 2021

Aug 23, 2021

Aug 18, 2021

Aug 17, 2021

Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages .

Source Distributions

Built distribution.

Uploaded Jul 19, 2023 py3

Hashes for exact-1.2.1-py3-none-manylinux_2_27_x86_64.manylinux_2_28_x86_64.whl

  • português (Brasil)

Supported by

binary integer programming solver python

themodernscientist

Data scientist, biophysicist, mac-unix zealot, pythonista, binary integer programming with python.

My research is focused on biomolecular NMR and, as such, often involves transferring resonance assignments from one multidimensional NMR spectrum to another. In theory this should be a simple task, but it can be extremely time consuming due to small variations in the sample used to acquire the data or in the way the data were acquired.

The good news, however, is that it is possible to automate this process using an optimization. Optimization problems, such as aligning x-ray crystallographic models of homologous proteins, are often encountered in structural biology. In the case of a structural alignment, the transformed structure can occupy any set of coordinates, provided the shape of the molecule itself is not changed. The transfer of resonance assignments is different in that individual resonances are either matched with each other or not. The transformation from one set of data onto another is effectively discrete (more specifically, it is binary). This type of optimization is known as “binary integer programming.”

When I attempted to write a script to perform this type of optimization using python, I found some excellent background reading but very little information on how to implement such a calculation. Being someone who learns by example, I thought it would be useful to share how I setup a simple binary integer programming calculation using two different python libraries 2 that interact with open source solvers written in ANSI C. 1

This notebook demonstrates how to use python to interface with two open source packages for binary integer programming, GLPK and lp_solve . These packages are demonstrated using two python libraries, CVXOPT , which interacts with GLPK, and lp_solve's own python interface. An example for matching five x,y -coordinate pairs from two different data sets is shown for each library.

Setup notes and module import ¶

CVXOPT must be installed with GLPK support and lp_solve with python bindings must be installed. GLPK, lp_solve (without python interface), and CVXOPT are available via MacPorts . I have created a GitHub repository with the MacPorts configuration files necessary to install lp_solve with its python bindings. Alternatively, the python functionality for lp_solve could be installed in a separate repository with virtualenv . The import statements below assume that GLPK and CVXOPT have been installed as provided by MacPorts and the modified lp_solve from GitHub has been installed within MacPorts as well. Finally, numpy is required for working with arrays. Matplotlib is required only if plotting the results of the optimization is desired.

Create two data sets ¶

The first data set contains five x,y -coordinate pairs where the first column is x - and the second column is y -data.

The second data set is similar to the first but has random noise added to it. The order of the points is also shuffled so the optimization solution isn't trivial.

Add some names for the data points and shuffle them in the same way for the second data set. This will be useful later when determining if the peaks were correctly matched.

Calculate the distance between each pair of data points ¶

The goal of the optimization is to minimize the sum of the distance between each set of matched points. Thus, the cartesian distance must be calculated for each point in data1 and the set of points in data2 . The simplest way to do this is with a distance matrix containing all peaks from data1 along one axis and those from data2 along the second axis.

In the above line, n_data1 and n_data2 are the number of points in data1 and data2 , respectively.

Setup the binary integer programming problem ¶

In addition to calculating the distance matrix, the optimization requires setting constraints to ensure that each point in one data set is paired with at most one point in the corresponding data set. This is accomplished using the following two constraints:

$\matrix{A} \space \times \space \matrix{X} \space = \space \matrix{b}$

$\matrix{C} \space \times \space \matrix{X} \space \leq \space \matrix{d}$

where $\matrix{A}$ and $\matrix{C}$ are binary (all values are either 0 or 1 ) matrices whose first dimensions are n_data1 and n_data2 , respectively, and both second dimensions are the product of the two data set sizes, n_data1 $\times$ n_data2 . $\matrix{b}$ and $\matrix{d}$ are column vectors of length n_data1 and n_data2 , respectively, whose value is 1 everywhere. Given these constraints, the goal of the optimization is to find a matrix $\matrix{X}$ that minimizes the target function:

$\matrix{f} \space \times \space \matrix{X}$

where $\matrix{f}$ is the distance matrix calculated above, except that it has been "flattened": converted to a column vector of length n_data1 $\times$ n_data2 . $\matrix{X}$ is a flattened form of the binary-valued transformation matrix, where the position of the ones in this matrix maps data2 onto data1 .

An in-depth discussion of integer programming theory is beyond both the scope of this post and the extent of my optimization knowledge, but I'd like to provide further explanation of how I think about the target (minimized) function and constraint equations. In the target function, $\matrix{X}$ selects the set of distances in $\matrix{f}$ that correspond to matched points so that the sum of these values can be determined and minimized. In the first constraint equation, matrix $\matrix{A}$ ensures there is only a single 1 value in each "row" of $\matrix{X}$, so each point in data1 is paired to exactly one point in data2 . Pretending for a moment that the inequality in the second constraint is actually an equality, this equation accomplishes the analogous goal of ensuring each point in data2 is paired to exactly one point in data1 . The inequality enables one of the data sets ( data2 as setup here) to have extra points that are not matched to any points in data1 .

These matrices are setup as follows:

Implementation using CVXOPT and GLPK ¶

Having setup the constraints above, the remaining steps for performing the optimization using CVXOPT are relatively simple. CVXOPT is capable of many types of optimization, thus the variable binVars is used to define the position of all elements in $\matrix{X}$ which are both integer and binary. (For this optimization, that is every element of $\matrix{X}$. Because $\matrix{f}$ is the same length as $\matrix{X}$ and is already defined, its length is used to determine binVars .) Also note that CVXOPT's integer programming function, ilp , does not accept numpy matrices and instead requires its own matrix function that is imported above. Lastly, all the functions use their own variable names, so they are listed as named arguments to eliminate confusion.

The variable output_cvxopt contains several variables, one of which indicates if the optimization converged and, if it did, another variable containing $\matrix{X}$. Normally, it's good practice to check that the optimization converged, but in this case it's known to work. The transformation matrix, X_cvxopt , is reshaped into a two-dimensional matrix so it can easily be used to determine the order of data2 data points that matches them with those in data1 .

Sanity check the optimization results ¶

It is incredibly easy to get dimensions transposed, particularly when matrices have to be flattened and reshaped. Thus, it is critical to check the results. In the above optimization, the peak labels should be identical for each point if the peaks are correctly matched.

Another, more graphical sanity check, involves plotting the data sets on two graphs and connecting the matched pairs.

Implementation using lp_solve ¶

The lp_solve wrapper requires all constraint functions to be entered as a single matrix, so $\matrix{A}$ and $\matrix{C}$ must be combined and, likewise, $\matrix{b}$ and $\matrix{d}$. The relationships ($\leq$, =, and $\geq$) are determined by a vector with a negative, zero, or positive value, respectively.

As with CVXOPT, a set of integers, binVars2 , is used set every value of $\matrix{X}$ to an integer. For lp_solve , the indexing for this set should start at 1 instead of 0 . To ensure that each of these integers is binary, a lower bound of 0 and upper bound of 1 has to be set as well.

Important : lp_solve maximizes the target function. To get the optimization to minimize the function, the value of $\matrix{f}$ must be negated.

The optimization is performed and then the transformation matrix $\matrix{X}$ and matched list are calculated as with CVXOPT.

The data could be checked graphically as well if desired.

This post was written in an IPython notebook, which can be downloaded here , or viewed statically here .

The two solvers, GLPK and lp_solve, are somewhat old and, it would seem, neither particularly fast or robust compared to more modern implementations , but they are well-tested and more than sufficient for my purposes.  ↩

I have used a third python library, OpenOpt , which also interfaces with GLPK. It is not demonstrated here as the syntax is similar that utilized by CVXOPT.  ↩

Implementation of a Integer Linear Programming Solver in Python

Introduction.

Integer linear programming problems are common in many domains. I recently found myself experimenting with formulating a probem as an integer programming problem, and I realized that I didn't really understand how the various solvers worked, so I set out to implement my own. This post is about the three pieces that need to be assembled to create one:

  • Expression trees and rewrite rules to provide a convenient interface.
  • Linear programming relaxation to get a non-integer solution (using scipy.optimize.linprog ).
  • Branch-and-bound to refine the relaxed soltion to an integer solution.

You can follow along at [cwpearson/csips][https://github.com/cwpearson/csips]

Problem Formulation

A linear programming problem is an optimization problem with the following form:

find \(\mathbf{x}\) to maximize $$ \mathbf{c}^T\mathbf{x} $$

$$\begin{aligned} A\mathbf{x} &\leq \mathbf{b} \cr 0 &\leq \mathbf{x} \cr \end{aligned}$$

For integer linear programming (ILP) , there is one additional constrait:

$$ \mathbf{x} \in \mathbb{Z} $$

In plain english, \(\mathbf{x}\) is a vector, where each entry represents a variable we want to find the optimal value for. \(\mathbf{c}\) is a vector with one weight for each entry of \(\mathbf{x}\). We're trying to maximize the dot product \(\mathbf{c}^T\mathbf{x}\); we're just summing up each each entry of entry of \(\mathbf{x}\) weighted by the corresponding entry of \(\mathbf{c}\). For example, if we seek to maximize the sum of the first two entries of \(\mathbf{x}\), the first two entries of \(\mathbf{c}\) will be \(1\) and the rest \(0\).

What about Minimizing instead of Maximizing? Just maximize \(-\mathbf{c}^T\mathbf{x}\) instead of maximizing \(\mathbf{c}^T\mathbf{x}\).

What if one of my variables needs to be negative? At first glance, it appears \(0 \leq \mathbf{x}\) will be a problem. However, we'll just construct \(A\) and \(\mathbf{b}\) so that all constraints are relative to \(-\mathbf{x}_i\) instead of \(\mathbf{x}_i\) for variable \(i\).

To specify our problem, we must specify \(A\), \(\mathbf{b}\), and \(\mathbf{c}^T\).

For simple problems it might be convenient enough to do this unassisted, for example (pdf) :

find \(x,y\) to maximize $$ 4x + 5y $$

$$\begin{aligned} x + 4y &\leq 10 \cr 3x - 4y &\leq 6 \cr 0 &\leq x,y \end{aligned}$$

We have two variables \(x\) and \(y\), so Our \(\mathbf{x}\) vector will be two entries, \(\mathbf{x}_0\) for \(x\) and \(\mathbf{x}_1\) for \(y\). Correspondingly, \(A\) will have two columns, one for each variable, and our \(\mathbf{c}\) will have two entries, one for each variable. We have two constraints, so our \(A\) will have two rows, one for each constraint.

How do we handle \(0 \leq x,y\)? We'll cover that later when we talk about scipy's linprog function to actually solve this.

User-friendly Interface

  • Implemented in expr.py

If your problem is complicated it can get clumsy to specify every constraint and objective in this form, since you'llneed to massage all your constraints so that all the variables are on the left and are \(\leq\) a constant on the right. It would be best to have the computer do this for you, and present a more natural interface akin to the following:

To do this, we'll introduce some python classes to represent nodes in an expression tree of our constraints. Then we'll overload the * , + , - , == , <= , and >= operators on those classes to allow those nodes to be composed into a tree from a natural expression.

For example, an implementation of scaling a variable by an integer:

Using part of the constraints above:

which represents variable x[0] multiplied by integer 3 . We can construct more complicated trees to support our expression grammar by extending these classes with additional operations (e.g. __leq__ , __sum__ , ...) and additional classes to represent summation expressions, less-or-equal equations, and so forth.

Conversion to Standard Form

  • Implemented at csips.py

Once each constraint (and the objective) are represented as expression trees, the challenge then becomes converting them into the standard form, e.g. all variables and scalar multiplications on the left-hand side (a row of \(A\)), and a single constant on the right-hand side (an entry of \(\mathbf{b}\)). We can use a few rewrite rules to transform our expression trees into what we want.

Distribution: $$ a \times (b + c) \rightarrow a \times b + a \times c $$

Fold: $$ a + b \rightarrow c $$

Move left $$ a \leq b + c \rightarrow a - b \leq c $$

Flip: $$ a \geq b \rightarrow -a \leq -b $$

By applying these rules, we can convert any of our expressions to one where a sum of scaled variables is on the left hand side of \(\leq\), and a single int is on the right hand side. Then it's a simple matter of generating an \(\mathbf{x}\) with one entry per unique variable, \(A\) from the scaling on those variables, and \(\mathbf{b}\) from the right-hand side.

Linear Program Relaxation

The way this is usually done is actually by initially ignoring the integer constraint ( \(\mathbf{x} \in \mathbb{Z}\) ), then going back and "fixing" the non-integer parts of your solution. When you ignore the integer constraint, you're doing what's called "linear programming relaxation" (LP relaxation) . Solving the LP relaxation will provide a (possibly non-integer) \(\mathbf{x}\).

We'll use scipy's linprog function to solve the LP relaxation.

Here's how linprog 's arguments map to our formulation

  • c : this is \(\mathbf{c}^T\)
  • A_ub : this is \(A\)
  • b_ub : this is \(\mathbf{b}\)

linprog also allows us to specify bounds on \(\mathbf{x}\) in a convenient form.

  • bounds : this allows us to provide bounds on \(\mathbf{x}\), e.g. providing the tuple (0, None) implements \(0 \leq \mathbf{x}\). This is not strictly necessary since we can directly express this constraint using A_ub and b_ub .

linprog also allows us to specify additional constraints in the form \(A\mathbf{x} = \mathbf{b}\). This is not strictly necessary, since for a variable \(i\) we could just say \(\mathbf{x}_i \leq c\) and \(-\mathbf{x}_i \leq -c\) in our original formulation to achieve \(\mathbf{x}_i = c\).

  • A_eq : \(A\) in optional \(A\mathbf{x} = \mathbf{b}\)
  • b_eq : \(\mathbf{b}\) in optional \(A\mathbf{x} = \mathbf{b}\)

linprog will dutifully report the optimal solution as \(x = 4\), \(y = 1.5\), and \(4x \times 5y = 23.5\). Of course, \(y = 1.5\) is not an integer, so we'll use "branch and bound" to refine towards an integer solution.

Branch and Bound

Branch and bound is a whole family of algorithms for solving discrete and combinatorial optimization problems. It represents the space of solutions in a tree, where the root node is all possible solutions. Each node branches into two child nodes each which represents two non-overlapping smaller subsets of the full solution space. As the tree is descended, the solution space will either shrink to 1 (a feasible solution) or 0 (no feasible solution). As we discover feasible solutions, we will keep track of the best one. At any point, we may be able to determine a bound on the best possible solution offered by a subset. If that bound is worse than the best solution so far, we can skip that entire subtree.

For our ILP problem, the algorithm looks like this:

  • Initialize the best objective observed so far to \(\inf\)
  • Find the LP relaxation solution
  • If the LP relaxation objective is worse than the best solution so far, discard it. The integer solution will be no better than the relaxation solution, so if the relaxation solution is worse, then the integer solution will be too.
  • Else, push that solution onto a stack
  • Take solution off the stack
  • If all \(\mathbf{x}\) entries are integers and the objective is the best so far, record it
  • Else, branch to produce two child nodes. If \(\mathbf{x}_i = c\) is non-integer, two subproblems, each with one additional constraint \(\mathbf{x}_i \leq \lfloor c \rfloor \) and \(\mathbf{x}_i \geq \lceil c \rceil \)
  • Report the solution with the best result so far.

Doing so for our example will converge on a solution of \(x = 2\), \(y = 2\), and \(4x \times 5y = 18\).

In 5.3, there are different ways to choose which non-integer variable to branch on. CSIPS branches on the first one or the most infeasible .

There are more sophisticated methods for solving the integer problem, such as branch-and-cut or branch-and-price. Unfortunately, these are difficult to investigate using scipy's linprog, as none of its solver methods make the tableau form accessible.

binary integer programming solver python

Member-only story

Integer Programming in Python: Solving Discrete Optimization Problems

Dr. Soumen Atta, Ph.D.

Dr. Soumen Atta, Ph.D.

Level Up Coding

D iscrete optimization problems involve finding the best solution from a finite set of possibilities. Integer programming is a powerful technique used to solve such problems when the variables are required to take integer values. In this tutorial, we will explore how to solve discrete optimization problems using integer programming techniques in Python.

Table of Contents

1. Understanding Integer Programming — Definition and Formulation — Integer Linear Programming (ILP) — Applications

2. Installing Required Libraries — Installing PuLP — Installing CBC Solver

3. Problem Formulation — Defining Decision Variables — Formulating the Objective Function — Specifying Constraints

4. Solving Integer Programming Problems with PuLP — Creating a Model — Adding Decision Variables — Adding the Objective Function — Adding Constraints — Solving the Model

5. Interpreting and Analyzing Results — Extracting Variable Values — Evaluating the Objective Function — Analyzing Sensitivity

6. Case Study: The Knapsack Problem — Problem Description — Formulating the Knapsack Problem — Implementing the Knapsack Problem in Python — Solving and Analyzing the Results

7. Conclusion

Get an email whenever dr. soumen atta, ph.d. publishes., get an email whenever dr. soumen atta, ph.d. publishes. by signing up, you will create a medium account if you don't….

soumenatta.medium.com

1. Understanding Integer Programming

Definition and formulation.

Integer programming is a mathematical optimization technique where the decision variables are constrained to take integer values. It is an extension of linear programming, which deals with continuous variables. In integer programming, the objective is to find the optimal solution that maximizes or minimizes a given objective function, subject to a set of constraints.

The general formulation of an integer programming problem can be represented as follows:

Minimize/Maximize c[1] * x[1] + c[2] * x[2] + … + c[n] * x[n]

a[11] * x[1] + a[12] * x[2] + … + a[1n] * x[n] <= b[1] a[21] * x[1] + a[22] * x[2] + … + a[2n] * x[n] <= b[2] . . . a[m1] * x[1] + a[m2] * x[2] + … + a[mn] * x[n] <= b[m]

  • x[1], x[2], ..., x[n] are the decision variables that must take integer values.
  • c[1], c[2], ..., c[n] are the coefficients of the objective function.
  • a[11], a[12], ..., a[mn] are the coefficients of the constraint matrix.
  • b[1], b[2], ..., b[m] are the right-hand side values of the constraints.

Integer Linear Programming (ILP)

Integer Linear Programming (ILP) is a specific type of integer programming where both the objective function and the constraints are linear. This means that the coefficients of the decision variables are multiplied by constants, and the variables are combined using addition and subtraction.

ILP has wide applications in various domains, such as operations research, supply chain management, scheduling, and resource allocation. Some common problems that can be solved using ILP include production planning, inventory management, employee scheduling, and facility location.

Applications

Integer programming techniques find application in numerous real-world problems. Here are a few examples:

  • Production Planning: Optimizing the production quantities of different products to maximize profit while considering resource constraints.
  • Vehicle Routing: Determining the optimal routes for a fleet of vehicles to minimize the total distance traveled while servicing multiple locations.
  • Bin Packing: Packing items of different sizes into a minimum number of bins while satisfying capacity constraints.
  • Project Scheduling: Scheduling tasks and allocating resources to complete a project within the shortest possible time.
  • Portfolio Optimization: Selecting a combination of investments to maximize returns while considering risk and constraints.
  • Cutting Stock Problem: Cutting large sheets of material into smaller pieces of specified sizes to minimize waste.

These are just a few examples, and integer programming techniques can be applied to a wide range of optimization problems.

Python API of DOcplex for solving linear programming problems

In this tutorial, we will learn how to write a model for linear programming problems (lpps) using python api and solve…, 2. installing required libraries.

Before we dive into solving integer programming problems in Python, we need to install the necessary libraries. In this tutorial, we will be using the PuLP library for modeling and the CBC solver as the backend solver. Here’s how you can install them:

Installing PuLP

PuLP is an open-source linear programming library in Python that provides a convenient way to define and solve optimization problems. To install PuLP, you can use the following command:

Installing CBC Solver

CBC (Coin-or branch and cut) is an open-source solver for mixed-integer programming problems. PuLP uses CBC as the default solver for integer programming problems. To install CBC, you can use the following command:

Once you have installed PuLP and CBC, you are ready to start solving integer programming problems in Python.

3. Problem Formulation

In this section, we will learn how to formulate an integer programming problem. We will define the decision variables, formulate the objective function, and specify the constraints.

Defining Decision Variables

The first step in formulating an integer programming problem is to define the decision variables. These variables represent the quantities or values that we want to determine. Decision variables are usually denoted by symbols like x , y , or z . In integer programming, decision variables are required to take integer values.

For example, let’s say we want to find the optimal number of units of two products to produce, denoted by x and y , respectively. We can define these variables as follows:

Here, pulp.LpVariable is used to create a decision variable. The first argument is the name of the variable, followed by optional arguments. We set lowBound=0 to specify that the variables should be non-negative.

Formulating the Objective Function

The objective function defines what we want to optimize, whether it is to maximize or minimize a certain quantity. The objective function is a linear combination of the decision variables, with coefficients representing the importance or contribution of each variable.

Let’s consider an example where we want to maximize the profit P based on the number of units produced x and y , with a profit per unit of p_x and p_y , respectively. The objective function can be formulated as follows:

Here, p_x and p_y are the profit per unit for products x and y , respectively. We multiply the profit per unit with the corresponding decision variable and sum them up to get the total profit.

Specifying Constraints

Constraints represent the limitations or restrictions on the decision variables. These can include resource constraints, capacity constraints, demand constraints, and any other conditions that must be satisfied.

Constraints can be formulated as linear inequalities or equalities involving the decision variables. Each constraint restricts the combination of variable values that are feasible.

Let’s consider an example where we have the following constraints:

  • The total production time available is limited to T hours.
  • The production of product x requires t_x hours per unit.
  • The production of product y requires t_y hours per unit.
  • There is a maximum limit on the number of units that can be produced for each product ( M_x units for x and M_y units for y ).

We can formulate these constraints as follows:

The first constraint ensures that the total production time does not exceed the available time T . The second and third constraints restrict the number of units produced for each product.

Solving Linear Programming Problems (LPPs) Using PuLP and Python

In this tutorial, we will learn how to solve linear programming problems (lpps) using pulp and python. at first, we…, 4. solving integer programming problems with pulp.

Now that we understand how to formulate an integer programming problem, let’s see how to solve it using the PuLP library.

Creating a Model

To solve an integer programming problem using PuLP, we need to create a model object. The model will contain the decision variables, the objective function, and the constraints.

Here, we create a model object named "Integer_Programming_Problem" . We specify that it is a maximization problem using pulp.LpMaximize . If it were a minimization problem, we would use pulp.LpMinimize .

Adding Decision Variables

Next, we add the decision variables to the model using the model.addVariable() method. We also specify the lower bound and the variable type (integer in this case).

Adding the Objective Function

We add the objective function to the model using the model.setObjective() method. We pass the objective function expression and indicate whether we want to maximize or minimize the objective.

Adding Constraints

We add the constraints to the model using the model.addConstraint() method. We pass the constraint expressions and specify the inequality type ( <= , >= , or == ).

Solving the Model

Once we have defined the model, decision variables, objective function, and constraints, we can solve the model using the model.solve() method.

The solver will find the optimal solution that satisfies the constraints and either maximizes or minimizes the objective function.

Solving linear programming problems (LPPs) using Pyomo

In this tutorial, we learn how to solve linear programming problems (lpps) using pyomo. pyomo stands for python…, 5. interpreting and analyzing results.

After solving the integer programming problem, we need to interpret and analyze the results. This involves extracting the values of the decision variables, evaluating the objective function, and analyzing sensitivity.

Extracting Variable Values

To extract the values of the decision variables from the solved model, we can use the value() method on the decision variables.

Evaluating the Objective Function

We can evaluate the objective function using the decision variable values obtained from the solved model.

Analyzing Sensitivity

Sensitivity analysis helps us understand how changes in the problem parameters affect the optimal solution. PuLP provides a way to perform sensitivity analysis on the solved model.

To obtain the sensitivity analysis report, we can use the model.sensitivity() method.

The sensitivity report provides information about the range of values over which the coefficients of the objective function and the right-hand side values of the constraints can change without affecting the optimal solution.

How to use DOcplex in Compute Canada cluster

In this tutorial, we will learn how to use docplex in compute canada cluster. for this, we need to install the ibm ilog…, 6. case study: the knapsack problem.

To illustrate the process of solving an integer programming problem in Python, let’s consider a classic optimization problem known as the Knapsack Problem.

Problem Description

The Knapsack Problem involves selecting items to maximize the total value while respecting a weight constraint. We are given a set of items, each with a weight and a value. The goal is to determine the combination of items to include in the knapsack such that the total weight does not exceed a given limit, and the total value is maximized.

Formulating the Knapsack Problem

Let’s formulate the Knapsack Problem as an integer programming problem.

Decision Variables:

  • x[i] : Binary decision variable indicating whether item i is selected or not.

Objective Function:

  • Maximize the total value of the selected items:

Subject to:

  • The total weight of the selected items should not exceed the knapsack capacity:

Here, v[i] represents the value of item i , w[i] represents the weight of item i , and capacity represents the knapsack capacity.

Implementing the Knapsack Problem in Python

Let’s implement the Knapsack Problem using PuLP in Python.

Solving and Analyzing the Results

By running the above code, the program will print the selected items that maximize the total value while respecting the weight constraint.

This indicates that item1 , item3 , and item4 are the items selected to maximize the total value within the knapsack capacity.

You can further analyze the results by extracting the values of the decision variables, evaluating the objective function, and performing sensitivity analysis as described in the previous sections.

Solving the Traveling Salesman Problem using PuLP in Python

The traveling salesman problem (tsp) is a classic optimization problem in which a salesman must visit a set of cities….

In this tutorial, we have explored the concept of integer programming and how to solve discrete optimization problems using integer programming techniques in Python. We learned about the formulation of integer programming problems, including defining decision variables, formulating the objective function, and specifying constraints. We also saw how to use the PuLP library to create a model, add decision variables, objective functions, and constraints, and solve the model.

Additionally, we discussed how to interpret and analyze the results by extracting variable values, evaluating the objective function, and performing sensitivity analysis. Finally, we applied the concepts learned in a case study on the Knapsack Problem, where we formulated the problem, implemented it in Python using PuLP, and obtained the optimal solution.

Integer programming is a powerful tool for solving discrete optimization problems with integer variables. By leveraging the capabilities of Python libraries like PuLP, we can efficiently model and solve such problems. The ability to tackle real-world problems with discrete decisions opens up opportunities for optimization in various domains.

Now that you have a good understanding of integer programming in Python, you can apply these techniques to solve your own discrete optimization problems. Remember to carefully formulate the problem, define the decision variables, objective function, and constraints, and use the appropriate solver to find the optimal solution. Happy optimizing!

Join Medium with my referral link - Dr. Soumen Atta, Ph.D.

Read every story from the thousands of writers on medium. become a member now your membership fee directly supports…, nonlinear optimization made easy with python, nonlinear optimization is a branch of optimization that deals with finding the optimal values of a function subject to…, pyomo tutorial: introduction to optimization modeling in python, pyomo is a powerful optimization modeling language that allows users to easily create, solve, and analyze mathematical….

Thanks for being a part of our community! Before you go:

  • 👏 Clap for the story and follow the author 👉
  • 📰 View more content in the Level Up Coding publication
  • 💰 Free coding interview course ⇒ View Course
  • 🔔 Follow us: Twitter | LinkedIn | Newsletter

🚀👉 Join the Level Up talent collective and find an amazing job

Dr. Soumen Atta, Ph.D.

Written by Dr. Soumen Atta, Ph.D.

Assistant Professor, Center for Information Technologies and Applied Mathematics, School of Engineering and Management, University of Nova Gorica, Slovenia

More from Dr. Soumen Atta, Ph.D. and Level Up Coding

100 Terminologies Every Machine Learning Engineer Must Master

100 Terminologies Every Machine Learning Engineer Must Master

In the exciting field of machine learning, knowing the terminology is super important, whether you’re just starting out or you’ve been….

Jacob Bennett

Jacob Bennett

The 5 paid subscriptions I actually use in 2024 as a software engineer

Tools i use that are cheaper than netflix.

API Design 101: From Basics to Best Practices

Hayk Simonyan

API Design 101: From Basics to Best Practices

Api design, from the basics to best practices..

7 Proven Strategies to Boost Your Medium Article Read Count

7 Proven Strategies to Boost Your Medium Article Read Count

Medium is a popular online platform that allows writers to share their content with a wider audience. while the platform offers a great…, recommended from medium.

Linear programming: Theory and applications

Bruno Scalia C. F. Leite

Towards Data Science

Linear programming: Theory and applications

Linear optimization main concepts and implementation in python.

Summer's Joy

Summer's Joy

Constrained Optimization Using Genetic Algorithm in python

Genetic algorithm (ga) is a powerful population based metaheuristics and when designed properly, it can find promising local optima for….

binary integer programming solver python

Coding & Development

binary integer programming solver python

Predictive Modeling w/ Python

Principal Component Analysis for ML

Practical Guides to Machine Learning

binary integer programming solver python

Alper Ersin Balcı

Operations Research Bit

A Soft Introduction to Google OR-Tools

Today we are going to talk about or-tools. google or-tools is an acronym for operations research..

Capacitated Vehicle Routing Problem (CVRP) Optimization using Google-OR Tools and Python

Nagarjuna Chidarala

Capacitated Vehicle Routing Problem (CVRP) Optimization using Google-OR Tools and Python

Introduction.

Solving Travelling Salesman Problem With Variable Neighborhood Search

Ahmed Mrabet

Solving Travelling Salesman Problem With Variable Neighborhood Search

Finding an approximate solution to the travelling salesman problem using variable neighborhood search in a reasonable time..

Solving Linear Programming using Python PuLP

Avinash Navlani

Solving Linear Programming using Python PuLP

Learn how to use python pulp to solve linear programming problems..

Text to speech

Search code, repositories, users, issues, pull requests...

Provide feedback.

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly.

To see all available qualifiers, see our documentation .

  • Notifications

A Binary Integer Linear Solver written in Python using Gurobi that outputs a visual solution to any valid Kakuro puzzle

SebastianCharmot/Kakuro-Binary-Integer-Linear-Program-Solver

Folders and files, repository files navigation.

Logo

Binary Integer Linear Program (BILP) to Solve Kakuro Puzzles

A Python implementation of a BILP that solves any Kakuro puzzle and outputs a visual solution.

Getting Started

Initial population, fitness function, euclidean distance, crossover 1 - blending, crossover 2 - crossover point, crossover 3 - pixel-wise, mutation 1 - random shape, mutation 2 - adding a constant, experimentation, introduction to genetic algorithms.

In this section, I give a general overview of what a genetic algorithm is. Readers that are familiar with this concept can skip to the next section.

A genetic algorithm is an optimization tool inspired by Darwin's theory of evolution. The algorithm mimics the process of natural selection, which chooses the fittest individuals from a population to create offspring and populate future generations. 

A genetic algorithm consists of the main components below. Click on any of the triangles to read a definition of each.

  • Initial Population The genetic algorithm starts with a group of individuals, referred to as the initial population. Each individual is a solution for the target that we are optimizing for. Typically, the individuals of the initial population are created randomly, assuming no prior knowledge about the solution. Because the individuals of the initial population are created randomly, they are likely poor solutions. However, their sole purpose is to serve as the building blocks for future generations.
  • Fitness Function Once an initial population is created, the individuals are evaluated based on a fitness function. The fitness function is a metric that evaluates what our genetic algorithm is seeking to optimize. In the classic genetic algorithm example of binary strings with a target, this fitness function might be how many binary strings have the correct value. In this case, a higher fitness function is a string that is "more fit" and closer to the optimal value.
  • Selection Criteria The selection criteria determines which individuals from the population are chosen to be parents for the next generation. Typically, we want to select individuals with stronger fitness. However, if we only select individuals with very strong fitness, we will lose some biodiversity. In terms of our algorithm, we want to maintain a certain level of stochasticity within each population to avoid falling into local minima. The classic way parent selection is done is via tournament selection. In essence, X individuals are selected from the total population and the most fit individual from those X tournament participants is chosen to be the parent. We can see that the lower X is, the more stochasticity and biodiversity we introduce into our parent selection. Finding the optimal balance between selecting generally more fit individuals while also maintaining a diverse set of parents is one of the challenging but fun aspects of genetic algorithms.
  • Crossover The crossover methods we implement determine how the offspring are created once we have selected parents. Typically two parents are chosen to create offspring. The purpose of a crossover function is to try to combine the attributes of the two parents into a child that is more fit. In order to do so, a popular method is simply to take the first half of parent(1) and combine it with the second half of parent(2). A random "crossover point" can also be used, meaning that parent(1) is used up until the crossover point and then parent(2) is used after the crossover point. Regardless of how crossover is implemented, the hope is that the child will incorporate elements of both parents and have a higher fitness.
  • Mutation Mutations are relatively low probability operations that slightly alter an offspring. The purpose of mutations are to introduce stochasticity, which can help combat local optima.

Putting together these components, we have the foundation for a genetic algorithm. We combine them in the following order. First, an initial population is seeded. It's individuals are evaluated by the fitness function, and then our selection criteria chooses fit parents to crossover and populate the next population. Each time a child is produced, there is a potential it will mutate.

We can repeat the process of creating future generations for a set number of generations or until an optimal solution is achieved. 

Now that we have introduced a genetic algorithm, we can dive into my genetic algorithm that seeks to recreate an image.

Python

Using the following libraries:

  • Pillow (Image manipulation)
  • Matplotlib (Image display)
  • Numpy (Perform vectorized image manipulation and calculations)
  • Colour (Delta E color difference calculations)

The first step is installing the necessary libraries. This can be done by running the following:

Getting started with the genetica algorithm is as simple as instantiating a GP class from GP.py as the following:

The arguments of the run_gp method are (size of the initial population, number of generations to run) . For most of my experiments, an initial population of size 100 and 5,000 generations was enough to produce great results. By vectorizing the majority of the image manipulations, I am able to run those settings comfortably on my laptop with a run-time of several minutes.

Hyperparameters

When tuning hyperparameters, the variables of interest are the following:

  • Size of the initial population
  • The lower and upper bound on the number of random shapes
  • Whether to use Delta_E or Euclidean Distance
  • Altering the size of a tournament
  • Different probabilistic combinations
  • Varying the probability of a mutation occurring
  • Changing the probability of using mutation 1 versus mutation 2

We will now dive into the code to change each of the following hyperparameters.

Changing the size of the initial population can be done by the first argument passed into the GP class' GP.run_gp method.

Each individual is created by the Individual class found in Individual.py . When a random individual is created, it is given a random background color. Then, a random number of polygons of random sides with random color is added onto that background.

All of this is within the Individual's create_random_image_array method.

Below are examples of individuals created this way.

binary integer programming solver python

I experimented with two main fitness functions. The fitness function is found within the Individual class.

A relatively straightforward implementation where I take the Euclidean distance between the RGB values of two pixels. Then, I perform this operation across the entire image and take the mean. To use Euclidean distance:

However, Euclidean distance has one main disadvantage. It is the fact that our eyes do not perceive difference in RGB values according to Euclidan distance. The example below illustrates this.

binary integer programming solver python

In an attempt to quantify how human eyes detect differences in color, scientists devised the Delta_E metric.

Delta_E is a more robust measurement of color difference true to the human eye. It was developed by the International Commission on Illumination and is considered the standard color difference measurement tool. To use the Delta_E fitness function, we simply leverage the colour library in the following manner:

My experiments indicated that Delta_E generated better outputs virtually every single time.

I implemented tournament selection to select parents. I randomly sampled the population given a tournament size and selected the fittest individual to be the winner of the tournament.

To experiment with different tournament sizes, alter the tournament_size variable. I had the most success with a tournament size between 6-8% of the total population size.

I implemented 3 unique crossover functions and experimented with probabilistic blends of all 3. Below, I describe each crossover function and give an example.

In this functon, I assign opacity $x$ to $\text{parent} {1}$ and assign opacity $1-x$ to $\text{parent} {2}$. Then we overlay both of them to create the child. If $x$ is 0, a copy of $\text{parent} {1}$ is produced. If $x$ is 1, a copy of $\text{parent} {2}$ is produced.

To determine $x$ , I sample a uniform distribution where $x \in (0,1)$ . One advantage of not fixing $x = 0.5$ is that this introduces stochasticity to the crossover function and can produce different children given the same parents.

Below is an example of what this look like:

binary integer programming solver python

In this approach, we select a random row or column to be a crossover point. Everything up until that row or column is from $\text{parent} {1}$ and everything including and after that row or column is from $\text{parent} {2}$. Once again, this row or column is selected from a uniform distribution. The two examples below illustrate a row crossover point and a column crossover point respectively.

binary integer programming solver python

I assigned an equal chance for Crossover 2 to be done horizontally or vertically. It would be interesting to test diagonal crossover lines but for my experiments, I only used horizontal or vertical crossovers.

For this crossover function, each pixel in the child is selected randomly from either $\text{parent} {1}$ or $\text{parent} {2}$.

This technique performs well but ends up creating images that look granulated as you can see in the example below. As a result, I didn't utilize this crossover function much.

binary integer programming solver python

I developed 2 different mutation functions that would slightly modify an individual.

To perform this mutation, I superimpose a random number of shapes of random color onto an individual.

The result of this mutation can be seen below.

binary integer programming solver python

In this mutation, I select a random subset of pixels and add a constant to their RGB values.

The results of this kind of mutation can be seen in the figure below.

binary integer programming solver python

It's effects are relatively subtle and did not seem to be an effective mutation operation. It also introduces the effect of "pixelation" which I believe tend to decrease the visually appearance of individuals.

Given all this information about how the specific hyperparameters work, you can start to experiment with your own images. As a baseline, I will provide the hyperparameters that worked best for me:

  • Size of 100
  • Each with [3, 6] shapes of random color
  • Only Delta_E
  • Tournament size of 6
  • Using a probabilistic mix of 30% crossover 1 (blending) and 60% crossover 2 (crossover)
  • Using a 10% chance for mutation 1 (adding shape)
  • Anywhere between 5,000 and 10,000

binary integer programming solver python

  • Python 100.0%

A Basic Branch and Bound Solver in Python using Cvxpy

Jun 13, 2019 • philzook58

Branch and bound is a useful problem solving technique. The idea is, if you have a minimization problem you want to solve, maybe there is a way to relax the constraints to an easier problem. If so, the solution of the easier problem is a lower bound on the possible solution of the hard problem. If the solution of the easier problem just so happens to also obey the more constrained hard problem, then it must also be the solution to the hard problem. You can also use the lower bound coming from a relaxed problem to prune your search tree for the hard problem. If even the relaxed problem doesn’t beat the current best found, don’t bother going down that branch.

A standard place this paradigm occurs is in mixed integer programming. The relaxation of a binary constraint (either 0 or 1) can be all the values in between (any number between 0 and 1). If this relaxed problem can be expressed in a form amenable to a solver like a linear programming solver, you can use that to power the branch and bound search, also using returned solutions for possible heuristics.

I built a basic version of this that uses cvxpy as the relaxed problem solver. Cvxpy already has much much faster mixed integer solvers baked in (which is useful to make sure mine is returning correct results), but it was an interesting exercise. The real reason I’m toying around is I kind of want the ability to add custom branching heuristics or inspect and maintain the branch and bound search tree, which you’d need to get into the more complicated guts of the solvers bound to cvxpy to get at. Julia might be a better choice.

A somewhat similar (and better) project is https://github.com/oxfordcontrol/miosqp which doesn’t use cvxpy explicitly, but does have the branch and bound control in the python layer of the solver. There are also other projects that can use fairly arbitrary solvers like Bonmin

As a toy problem I’m using a knapsack problem where we have objects of different sizes and different values. We want to maximize the value while keeping the total size under the capacity of the bag. This can be phrased linearly like so: $ \max v \cdot x$ s.t. $ \sum_i s_i x_i<= capacity $, $ x \in {0,1}$. The basic heuristic I’m using is to branch on variables that are either 0 or 1 in even the relaxed solution. The alternative branch hopefully gets pruned fast.

This is at least solving the problem fairly quickly. It needs better heuristics and to be sped up, which is possible in lots of ways. I was not trying to avoid all performance optimizations. It takes maybe 5 seconds, whereas the cvxpy solver is almost instantaneous.

Edit : I should investigate the Parameter functionality of cvxpy. That would make a make faster version than the one above based on deepcopy. If you made the upper and lower vectors on the binary variables parameters, you could restrict the interval to 0/1 without rebuilding the problem or copying everything.

IMAGES

  1. Integer to Binary String in Python

    binary integer programming solver python

  2. Python 3 How to convert Integers to Binary

    binary integer programming solver python

  3. How to Convert an Integer to Binary in Python

    binary integer programming solver python

  4. Python

    binary integer programming solver python

  5. Python int to Binary

    binary integer programming solver python

  6. Convert binary to integer in python

    binary integer programming solver python

VIDEO

  1. Binary Integer Programming BIP

  2. Lecture 05 09 Various Uses of Binary Integer Programming Excel Solver

  3. Python Program to Read a Binary File

  4. Binary Python

  5. Lecture 05 07 Binary Integer Programming Excel Solver

  6. Integer and Binary Linear Programming

COMMENTS

  1. binary linear programming solver in Python

    3 Answers Sorted by: 7 Just to be rigorous, if the problem is a binary programming problem, then it is not a linear program. You can try CVXOPT. It has a integer programming function (see this ). To make your problem a binary program, you need to add the constrain 0 <= x <= 1.

  2. Hands On Integer (Binary) Linear Optimization using Python

    Hands On Integer (Binary) Linear Optimization using Python. ... This implies that the answer will not be a integer number between 0 and infinity, but the answer could be 0 or 1. Linear: ... Learn how to use Python PuLP to solve linear programming problems.

  3. scipy.optimize.linprog

    Linear programming: minimize a linear objective function subject to linear equality and inequality constraints. Linear programming solves problems of the following form: min x c T x such that A u b x ≤ b u b, A e q x = b e q, l ≤ x ≤ u,

  4. Integer Programming in Python

    Integer Programming (IP) problems are optimization problems where all of the variables are constrained to be integers. IP problems are useful mathematical models for how to best allocate one's resources. Let's say you're organizing a marketing campaign for a political candidate and you're deciding which constituents to send marketing materials to.

  5. Hands-On Linear Programming: Optimization With Python

    The Python ecosystem offers several comprehensive and powerful tools for linear programming. You can choose between simple and complex tools as well as between free and commercial ones. It all depends on your needs. In this tutorial, you'll learn: What linear programming is and why it's important

  6. Optimization (scipy.optimize)

    The minimize function provides a common interface to unconstrained and constrained minimization algorithms for multivariate scalar functions in scipy.optimize. To demonstrate the minimization function, consider the problem of minimizing the Rosenbrock function of N variables: f(x) = N − 1 ∑ i = 1100(xi + 1 − x2i)2 + (1 − xi)2.

  7. exact · PyPI

    Exact. Exact solves decision and optimization problems formulated as integer linear programs. Under the hood, it converts integer variables to binary (0-1) variables and applies highly efficient propagation routines and strong cutting-planes / pseudo-Boolean conflict analysis. Exact is a fork of RoundingSat and improves upon its predecessor in ...

  8. Binary Integer Programming With Python

    This notebook demonstrates how to use python to interface with two open source packages for binary integer programming, GLPK and lp_solve.These packages are demonstrated using two python libraries, CVXOPT, which interacts with GLPK, and lp_solve's own python interface.An example for matching five x,y-coordinate pairs from two different data sets is shown for each library.

  9. Implementation of a Integer Linear Programming Solver in Python

    csips.py. The way this is usually done is actually by initially ignoring the integer constraint ( \ (\mathbf {x} \in \mathbb {Z}\) ), then going back and "fixing" the non-integer parts of your solution. When you ignore the integer constraint, you're doing what's called "linear programming relaxation" (LP relaxation) .

  10. An introduction to mixed-integer linear programming: The knapsack

    Since version 1.9.0, scipy has a mixed integer linear programming solver. Hence, we can transform the relaxed knapsack problem into its integer version by parsing the integrality keyword argument to linprog. Full integer variables should be assigned with ones, whereas continuous variables should be assigned with zeros in the same shape as the ...

  11. Integer Programming in Python: Solving Discrete Optimization Problems

    D iscrete optimization problems involve finding the best solution from a finite set of possibilities. Integer programming is a powerful technique used to solve such problems when the variables are required to take integer values. In this tutorial, we will explore how to solve discrete optimization problems using integer programming techniques in Python.

  12. integer-linear-programming · GitHub Topics · GitHub

    A Binary Integer Linear Solver written in Python using Gurobi that outputs a visual solution to any valid Kakuro puzzle. kakuro-solver integer-linear-programming binary-integer-programming Updated Sep 14, 2022; Python; lucianoSF / KNP-TS Star 0. Code Issues Pull requests ...

  13. PDF Mixed Integer Linear Programming with Python

    The Python-MIP package provides tools for modeling and solvingMixed-Integer Linear Programming Problems(MIPs) [Wols98] in Python. The default installation includes theCOIN-OR Linear Pro-gramming Solver - CLP, which is currently thefastestopen source linear programming solver and the COIN-ORBranch-and-Cutsolver-CBC,ahighlyconfigurableMIPsolver.

  14. Linear programming and discrete optimization with Python using PuLP

    Linear and (mixed) integer programming are techniques to solve problems which can be formulated within the framework of discrete optimization.

  15. Gentle Introduction to Linear Programming by solving Kakuro ...

    1. This article seeks to strengthen your understanding of linear programming through a fun and practical example using Kakuro puzzles. We will go through how Binary Integer Linear Programming ...

  16. SebastianCharmot/Kakuro-Binary-Integer-Linear-Program-Solver

    GitHub - SebastianCharmot/Kakuro-Binary-Integer-Linear-Program-Solver: A Binary Integer Linear Solver written in Python using Gurobi that outputs a visual solution to any valid Kakuro puzzle SebastianCharmot / Kakuro-Binary-Integer-Linear-Program-Solver Public Notifications Fork 0 Star 1 Code Issues Pull requests Actions Projects Security Insights

  17. A Basic Branch and Bound Solver in Python using Cvxpy

    A standard place this paradigm occurs is in mixed integer programming. The relaxation of a binary constraint (either 0 or 1) can be all the values in between (any number between 0 and 1). If this relaxed problem can be expressed in a form amenable to a solver like a linear programming solver, you can use that to power the branch and bound ...

  18. python

    python - Integer Linear optimization with PuLP - Stack Overflow Integer Linear optimization with PuLP Ask Question Asked 6 years, 5 months ago Modified 6 years, 5 months ago Viewed 10k times 5 I have to solve an integer linear optimization with pulp. I solved the problem and get optimization value equal to 42.

  19. Python Mixed Integer Nonlinear Programming

    import numpy as np from gekko import GEKKO m = GEKKO () n = 100 # select one of the Special Ordered Set α = m.sos1 ( [0.5, 1, 2, 5]) # integer variables β = m.Array (m.Var,n,integer=True,lb=1,ub=5) # log transform δ = [m.log (b) for b in β] # matrix M = np.random.rand (n,n) # constraints Mδ = M.dot (δ) m.Equations ( [α*x>50 for x in Mδ]) # objec...

  20. How do you express binary literals in Python?

    How do you express an integer as a binary number with Python literals? I was easily able to find the answer for hex: >>> 0x12AF 4783 >>> 0x100 256 and octal: >>> 01267 695 >>> 0100 64 How do you use literals to express binary in Python? Summary of Answers Python 2.5 and earlier: can express binary using int ('01010101111',2) but not with a literal.