This shows you the differences between two versions of the page.
Next revision | Previous revision | ||
info:tech_report_example [2015/03/29 13:13] aykutbulut created |
— (current) | ||
---|---|---|---|
Line 1: | Line 1: | ||
- | \def\coralreport{1} | ||
- | %\documentclass{./ | ||
- | \documentclass{article} | ||
- | |||
- | \usepackage{ifthen} | ||
- | %\usepackage{float} | ||
- | \usepackage[funcfont=italic, | ||
- | \usepackage{algorithm} % for algorithm environment | ||
- | \usepackage{algpseudocode} % for algorithmic environment | ||
- | | ||
- | | ||
- | \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} | ||
- | |||
- | |||
- | \renewcommand{\Re}{\mathbb{R}} | ||
- | \algdef{SE}[DOWHILE]{Do}{doWhile}{\algorithmicdo}[1]{\algorithmicwhile\ #1} | ||
- | % todo(aykut) this will create a problem with \P command of complexity package. | ||
- | \renewcommand{\P}{\mathcal{P}} | ||
- | |||
- | \setlength{\evensidemargin}{0in} | ||
- | \setlength{\oddsidemargin}{0in} | ||
- | \setlength{\parindent}{0in} | ||
- | \setlength{\parskip}{0.06in} | ||
- | |||
- | |||
- | \ifthenelse{\coralreport = 1}{ | ||
- | \usepackage{./ | ||
- | \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: | ||
- | \author{Ted K. Ralphs\thanks{E-mail: | ||
- | \affil{Department of Industrial and Systems Engineering, | ||
- | \titlepage | ||
- | }{ | ||
- | \author{Aykut Bulut} | ||
- | \author{Ted K. Ralphs} | ||
- | \affil{COR@L Lab, Department of Industrial and Systems Engineering, | ||
- | \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, | ||
- | computational complexity, polynomial hierarchy | ||
- | }{} | ||
- | \end{abstract} | ||