User Tools

Site Tools



Info / Resources



Sample Pages

Quick Navigation

\usepackage{algorithm} % for algorithm environment
\usepackage{algpseudocode} % for algorithmic environment
   %\usepackage[pdftex]{graphicx} for pdflatex
   %\usepackage{graphicx} for latex
% for tiles and keywords
\algdef{SE}[DOWHILE]{Do}{doWhile}{\algorithmicdo}[1]{\algorithmicwhile\ #1}
% todo(aykut) this will create a problem with \P command of complexity package.
\ifthenelse{\coralreport = 1}{
% The report number is the same one used in the ISE tech report series
% This is the revision number (increment for each revision)
% 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
\title{On the Complexity of Inverse MILP}
\ifthenelse{\coralreport = 1}{
  \author{Aykut Bulut\thanks{E-mail: \texttt{}}}
  \author{Ted K. Ralphs\thanks{E-mail: \texttt{}}}
  \affil{Department of Industrial and Systems Engineering, Lehigh University, USA}
  \author{Aykut Bulut}
  \author{Ted K. Ralphs}
  \affil{COR@L Lab, Department of Industrial and Systems Engineering, Lehigh University, USA}
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}{
{\bf Keywords:} Inverse optimization, mixed integer linear program,
computational complexity, polynomial hierarchy
Optimization problems arise in many fields ...
info/tech_report_example.tex.txt · Last modified: 1998/12/03 12:11 (external edit)