# 运筹系列86：MIP问题的建模tips

## 1. Either-or constraint

Either

3

x

1

+

2

x

2

18

3x_1+2x_2 le 18

3x1+2x218
or

x

1

+

4

x

2

16

x_1+4x_2 le 16

x1+4x216

3

x

1

+

2

x

2

18

+

M

y

3x_1+2x_2 le 18+My

3x1+2x218+My

x

1

+

4

x

2

16

+

M

(

1

y

)

x_1+4x_2 le 16+M(1-y)

x1+4x216+M(1y)

## 2. k out of N constraints must hold

y

1

y_1

y1

y

N

y_N

yN

f

1

(

.

.

.

)

d

1

f_1(...)le d_1

f1(...)d1

f

N

(

.

.

.

)

d

N

f_N(...)le d_N

fN(...)dN

f

1

(

.

.

.

)

d

1

+

M

y

1

f_1(...)le d_1+My_1

f1(...)d1+My1

f

N

(

.

.

.

)

d

N

+

M

y

N

f_N(...)le d_N+My_N

fN(...)dN+MyN

Σ

1

N

y

i

=

N

k

,

y

i

Sigma_1^N y_i=N-k, y_i

Σ1Nyi=Nk,yi binary.

## 3. functions with N possible values

f

(

x

)

(

d

1

,

.

.

.

,

d

N

)

f(x)in (d_1,...,d_N)

f(x)(d1,...,dN)

y

1

y_1

y1

y

N

y_N

yN

f

(

x

)

=

Σ

d

i

y

i

f(x)=Sigma d_iy_i

f(x)=Σdiyi

Σ

y

i

=

1

Sigma y_i=1

Σyi=1 (mutally exclusive alternatives)

## 4. fixed-charge problem

f

(

x

)

=

{

k

+

c

x

,

x

>

0

0

,

x

=

0

f(x)=begin {equation} begin{cases} k+cx, x>0\ 0,x=0\ end{cases} end {equation}

f(x)={k+cx,x>00,x=0

f

(

x

)

=

c

x

+

k

y

f(x)=cx+ky

f(x)=cx+ky

x

M

y

xle My

xMy

y

y

y binary.

## 5. 综合例子

x

1

,

x

2

,

x

3

x_1,x_2,x_3

x1,x2,x3最多只能有2个，因此添加

y

1

+

y

2

+

y

3

2

y_1+y_2+y_3le 2

y1+y2+y32的约束。

y

4

y_4

y4，最终模型为：

THE END

)">