With Piecewise Linear Objective Functions

Solving LP and MIP Models

with Piecewise Linear Objective Functions

Zonghao Gu

Gurobi Optimization Inc. Columbus, July 23, 2014

Overview

} Introduction } Piecewise linear (PWL) function

Convex and convex relaxation

} Modeling

Variables for pieces SOS2, binary formulations for non-convexity Direct handing

} Convex PWL objective

How to extend primal and dual simplex

} Non-convex PWL objective

How to extend branch-and-bound algorithm

} Possible future work

2

Introduction

3

Definition

A linear program with separable PWL objec4ve func4on is an op4miza4on problem of the form

n

Minimize c j( x j) j =1 n

Subject to aij x j = bi , i = 1,..., m j =1 l j x j u j , j = 1,..., n

Where c j ( x j) are piecewise linear, j = 1,..., n

4

Types

} Convex cj(xj)

Treated as LP

} Non-convex cj(xj)

Treated as MIP

5

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download