# Lehigh ISE / COR@L Lab Wiki

### Sidebar

#### Sample Pages

info:tech_report_example

This is an old revision of the document!

\def\coralreport{1} %\documentclass{./llncs2e/llncs} \documentclass{article}

\usepackage{ifthen} %\usepackage{float} \usepackage[funcfont=italic,full]{./complexity/complexity} \usepackage{algorithm} % for algorithm environment \usepackage{algpseudocode} % for algorithmic environment

 %\usepackage[pdftex]{graphicx} for pdflatex
%\usepackage{graphicx} for latex

\usepackage{amsmath} \usepackage{amssymb} \usepackage{graphicx} \usepackage[authoryear]{natbib}

% for tiles and keywords \usepackage{authblk} \usepackage{geometry} \usepackage{fullpage} \newtheorem{theorem}{Theorem} \newtheorem{claim}{Claim} \newtheorem{definition}{Definition}


\setlength{\evensidemargin}{0in} \setlength{\oddsidemargin}{0in} \setlength{\parindent}{0in} \setlength{\parskip}{0.06in}

\ifthenelse{\coralreport = 1}{ \usepackage{./isetechreport/isetechreport} \def\reportyear{15T} % The report number is the same one used in the ISE tech report series \def\reportno{001} % This is the revision number (increment for each revision) \def\revisionno{0} % This is the date f the original report \def\originaldate{March 13, 2015} % This is the date of the latest revision \def\revisiondate{March 13, 2015} % Set these variables according to whether this should be a CORAL or CVCR % report \coralfalse \cvcrfalse \isetrue

}{}

%TODO(aykut): % → fix path problem of isetechreport.sty

\begin{document}

\title{On the Complexity of Inverse MILP}

\ifthenelse{\coralreport = 1}{

\author{Aykut Bulut\thanks{E-mail: \texttt{aykut@lehigh.edu}}}
\author{Ted K. Ralphs\thanks{E-mail: \texttt{ted@lehigh.edu}}}
\affil{Department of Industrial and Systems Engineering, Lehigh University, USA}
\titlepage

}{

\author{Aykut Bulut}
\author{Ted K. Ralphs}
\affil{COR@L Lab, Department of Industrial and Systems Engineering, Lehigh University, USA}
\date{\today}

}

\maketitle

\begin{abstract} Inverse optimization problems determine problem parameters that are closest to the estimates and will make a given solution optimum. In this study we work inverse \textbf{m}ixed \textbf{i}nteger \textbf{l}inear \textbf{p}roblems (MILP) where we seek the objective function coefficients. This is the inverse problem \cite{AhujaSeptember2001} studied for linear programs (LP). They show that inverse LP can be solved in polynomial time under mild conditions. We extend their result for the MILP case. We prove that the decision version of the inverse MILP is $\coNP$–complete. We also propose a cutting plane algorithm for solving inverse MILPs for practical purposes.

\ifthenelse{\coralreport = 0}{ \bigskip\noindent {\bf Keywords:} Inverse optimization, mixed integer linear program, computational complexity, polynomial hierarchy }{} \end{abstract}