YALMIP Wiki

Logic programming

By using the nonlinear operator framework, logic and constraint programming was easily added to YALMIP. The logic programming module is not intended to be used for large or advanced logic programs, but is only implemented to help the user to add a small number of logic constraints to a standard model. Note that logic constraints leads to a problem with binary variables, hence mixed integer programming is needed to solve the problem. The logic functionality has not been tested much, and was mainly implemented to show the strength of nonlinear operators. A lot of features are still lacking, but they are typically easy to add. If you need it, make a feature request!

Simple logic constraints

As a first example, let us solve a simple satisfiability problem. Note the use of standard binary variables and the true? operator

Truth constrained conditions are appended just like any set of constraints

The true? operator essentially takes a variable x and returns the constraint x≥1. Hence, the following code is equivalent

To constrain an expression to be false, use the false? operator,

or simply add the corresponding numerical constraint (Notice that we use inequality instead of equality constraint. The reason is rather technical but it is recommended, since the convexity propagation algorithm used for expanding the nonlinear operators might fail otherwise)

Objective functions are allowed.

In addition to the operators AND (&), OR (|) and NOT (~), the operator implies(X,Y) is implemented. To force e to be true if f is true, we use implies.

An equivalent formulation is

Mixed logic and conic constraints

The first construction for creating mixed constraints is implies. The following trivial program ensures the symmetric matrix X to have eigenvalues larger than 1 if a or b is true. The result is a mixed integer semidefinite problem which will be solved using YALMIPs mixed integer solver BNB. Be warned, a lot of the functionality here is experimental. Please validate your results and report any oddities as usual.

The following construction ensures the variable x to be contained in a polytope if d is true

A related command is if-and-only-if, iff, i.e. logic equivalence. The following code forces the variable x to be contained in a polytope if y is contained in the polytope, and vice versa.

This functionality can be used to model various logic constraints. Consider for instance the constraint that a variable is in one of several polytopes.

The data and plot was generated with the following code (assuming MPT is installed)

We will now try to find a point x as far up in the figure as possible, but still in one of the polytope. First, we define 4 binary variables, each one describing whether we are in the corresponding polytope, and add the constraint that we are in at least one polytope.

To connect the binary variables with the polytopes, we use the iff operator.

Finally, we solve the problem by maximizing the second coordinate of x.

The iff is overloaded as equality, hence the following code generates the same problem.

We should mention that it is not necessary to use the iff operator in this problem, the implies operator suffice. The implies operator should be used when possible, since it for most cases is much more efficiently implemented (less number of additional binary variables) than the iff function. As a general comment, if you want to play it safe, stay away from iff as much as possible, and don't use implies with the first argument being anything other than a binary variable.

The iff operator is used internally to construct mixed constraints involving OR. With this functionality, we can solve the previous problem using a more intuitive code (albeit possibly inefficient since it will use iff instead of implies).

Improving the Big-M formulation

The conversion from logic constraints to mixed integer constraints is done in YALMIP using a standard big-M formulation. By default, YALMIP uses a big-M value of 10⁴, but it is recommended to add explicit variable constraints to improve this. By explicitly adding bounds on variables, YALMIP can exploit these bounds to compute a reasonably small big-M constant.

Adding bounds can significantly improve the strength of the relaxations and corresponding reduction of computation time. Hence, if you know, or can estimate, lower and upper bounds, let YALMIP know this. If you fail to add bounds, YALMIP will issue warnings.

Variable index variables

By combining the framework for nonlinear operators and logic programming, YALMIP allows variable indices. The following silly example picks out the two highest indices of elements in a vector p smaller than or equal to three.

You might wonder why we use the variable x, instead of writing p([i j]). The reason is simply due to limitations in MATLABs implementation of overloading indexing in double variables.

See also

nnz, alldifferent, sort, ismember Logic operators, Sudoku example