The piecewise linear optimization polytope: New inequalities and intersection with semi-continuous constraints

Ming Zhao; Ismael Regis De Farias

doi:10.1007/s10107-012-0517-z

The piecewise linear optimization polytope: New inequalities and intersection with semi-continuous constraints

Ming Zhao, Ismael Regis De Farias

Industrial Engineering

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

Abstract

We give new facets and valid inequalities for the separable piecewise linear optimization (SPLO) knapsack polytope. We also extend the inequalities to the case in which some of the variables are semi-continuous. Finally, we give computational results that demonstrate their efficiency in solving difficult instances of SPLO and SPLO with semi-continuous constraints.

Original language	English
Pages (from-to)	217-255
Number of pages	39
Journal	Mathematical Programming
Volume	141
Issue number	1-2
DOIs	https://doi.org/10.1007/s10107-012-0517-z
State	Published - Oct 2013

Keywords

Branch-and-cut
Knapsack problem
Mixed-integer programming
Piecewise linear optimization
Polyhedral method
Semi-continuous variables
Special ordered set

Access to Document

10.1007/s10107-012-0517-z

Link to publication in Scopus

Fingerprint Dive into the research topics of 'The piecewise linear optimization polytope: New inequalities and intersection with semi-continuous constraints'. Together they form a unique fingerprint.

Cite this

@article{dff9ec83215a4abe855479f97ea1e7f3,

title = "The piecewise linear optimization polytope: New inequalities and intersection with semi-continuous constraints",

abstract = "We give new facets and valid inequalities for the separable piecewise linear optimization (SPLO) knapsack polytope. We also extend the inequalities to the case in which some of the variables are semi-continuous. Finally, we give computational results that demonstrate their efficiency in solving difficult instances of SPLO and SPLO with semi-continuous constraints.",

keywords = "Branch-and-cut, Knapsack problem, Mixed-integer programming, Piecewise linear optimization, Polyhedral method, Semi-continuous variables, Special ordered set",

author = "Ming Zhao and {De Farias}, {Ismael Regis}",

year = "2013",

month = oct,

doi = "10.1007/s10107-012-0517-z",

language = "English",

volume = "141",

pages = "217--255",

journal = "Mathematical Programming",

issn = "0025-5610",

number = "1-2",

}

TY - JOUR

T1 - The piecewise linear optimization polytope

T2 - New inequalities and intersection with semi-continuous constraints

AU - Zhao, Ming

AU - De Farias, Ismael Regis

PY - 2013/10

Y1 - 2013/10

N2 - We give new facets and valid inequalities for the separable piecewise linear optimization (SPLO) knapsack polytope. We also extend the inequalities to the case in which some of the variables are semi-continuous. Finally, we give computational results that demonstrate their efficiency in solving difficult instances of SPLO and SPLO with semi-continuous constraints.

AB - We give new facets and valid inequalities for the separable piecewise linear optimization (SPLO) knapsack polytope. We also extend the inequalities to the case in which some of the variables are semi-continuous. Finally, we give computational results that demonstrate their efficiency in solving difficult instances of SPLO and SPLO with semi-continuous constraints.

KW - Branch-and-cut

KW - Knapsack problem

KW - Mixed-integer programming

KW - Piecewise linear optimization

KW - Polyhedral method

KW - Semi-continuous variables

KW - Special ordered set

UR - http://www.scopus.com/inward/record.url?scp=84884676023&partnerID=8YFLogxK

U2 - 10.1007/s10107-012-0517-z

DO - 10.1007/s10107-012-0517-z

M3 - Article

AN - SCOPUS:84884676023

VL - 141

SP - 217

EP - 255

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 1-2

ER -