User Tools

Site Tools



This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
Previous revision
Next revision Both sides next revision
info:tech_report_example.tex [1998/12/03 12:11]
info:tech_report_example.tex [2016/03/16 13:21]
Line 1: Line 1:
 +\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}
 +  \titlepage
 +  \author{Aykut Bulut}
 +  \author{Ted K. Ralphs}
 +  \affil{COR@L Lab, Department of Industrial and Systems Engineering,​ Lehigh University, USA}
 +  \date{\today}
 +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)