Main Content

Mixed-integer linear programming (MILP)

Mixed-integer linear programming solver.

Finds the minimum of a problem specified by

$$\underset{x}{\mathrm{min}}{f}^{T}x\text{subjectto}\{\begin{array}{l}x(\text{intcon})\text{areintegers}\hfill \\ A\cdot x\le b\hfill \\ Aeq\cdot x=beq\hfill \\ lb\le x\le ub.\hfill \end{array}$$

*f*, *x*, intcon, *b*, *beq*, *lb*,
and *ub* are vectors, and *A* and *Aeq* are
matrices.

You can specify *f*, intcon, *lb*,
and *ub* as vectors or arrays. See Matrix Arguments.

**Note**

`intlinprog`

applies only to the solver-based approach. For a discussion
of the two optimization approaches, see First Choose Problem-Based or Solver-Based Approach.

uses a
`x`

= intlinprog(`problem`

)`problem`

structure to encapsulate all solver inputs. You
can import a `problem`

structure from an MPS file using
`mpsread`

. You can also create a
`problem`

structure from an
`OptimizationProblem`

object by using `prob2struct`

.

Often, some supposedly integer-valued components of the solution

`x(intCon)`

are not precisely integers.`intlinprog`

deems as integers all solution values within`IntegerTolerance`

of an integer.To round all supposed integers to be exactly integers, use the

`round`

function.x(intcon) = round(x(intcon));

**Caution**Rounding solutions can cause the solution to become infeasible. Check feasibility after rounding:

max(A*x - b) % See if entries are not too positive, so have small infeasibility max(abs(Aeq*x - beq)) % See if entries are near enough to zero max(x - ub) % Positive entries are violated bounds max(lb - x) % Positive entries are violated bounds

`intlinprog`

does not enforce that solution components be integer-valued when their absolute values exceed`2.1e9`

. When your solution has such components,`intlinprog`

warns you. If you receive this warning, check the solution to see whether supposedly integer-valued components of the solution are close to integers.`intlinprog`

does not allow components of the problem, such as coefficients in`f`

,`A`

, or`ub`

, to exceed`1e25`

in absolute value. If you try to run`intlinprog`

with such a problem,`intlinprog`

issues an error.

To specify binary variables, set the variables to be integers in

`intcon`

, and give them lower bounds of`0`

and upper bounds of`1`

.Save memory by specifying sparse linear constraint matrices

`A`

and`Aeq`

. However, you cannot use sparse matrices for`b`

and`beq`

.If you include an

`x0`

argument,`intlinprog`

uses that value in the`'rins'`

and guided diving heuristics until it finds a better integer-feasible point. So when you provide`x0`

, you can obtain good results by setting the`'Heuristics'`

option to`'rins-diving'`

or another setting that uses`'rins'`

.To provide logical indices for integer components, meaning a binary vector with

`1`

indicating an integer, convert to`intcon`

form using`find`

. For example,logicalindices = [1,0,0,1,1,0,0]; intcon = find(logicalindices)

intcon = 1 4 5

`intlinprog`

replaces`bintprog`

. To update old`bintprog`

code to use`intlinprog`

, make the following changes:Set

`intcon`

to`1:numVars`

, where`numVars`

is the number of variables in your problem.Set

`lb`

to`zeros(numVars,1)`

.Set

`ub`

to`ones(numVars,1)`

.Update any relevant options. Use

`optimoptions`

to create options for`intlinprog`

.Change your call to

`bintprog`

as follows:`[x,fval,exitflag,output] = bintprog(f,A,b,Aeq,Beq,x0,options) % Change your call to: [x,fval,exitflag,output] = intlinprog(f,intcon,A,b,Aeq,Beq,lb,ub,x0,options)`

The **Optimize** Live Editor task provides a visual interface for `intlinprog`

.

`linprog`

| `mpsread`

| Optimize | `optimoptions`

| `prob2struct`

- Mixed-Integer Linear Programming Basics: Solver-Based
- Factory, Warehouse, Sales Allocation Model: Solver-Based
- Traveling Salesman Problem: Solver-Based
- Solve Sudoku Puzzles Via Integer Programming: Solver-Based
- Mixed-Integer Quadratic Programming Portfolio Optimization: Solver-Based
- Optimal Dispatch of Power Generators: Solver-Based
- Mixed-Integer Linear Programming Algorithms
- Tuning Integer Linear Programming
- Solver-Based Optimization Problem Setup