User Tools

Site Tools


Sidebar


Wiki

Info / Resources

Guides

Software

Sample Pages

Quick Navigation

info:tech_report_example.tex

This is an old revision of the document!


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

\usepackage{ifthen} %\usepackage{float} \usepackage{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}

\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{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

}{}

\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}

\section{Introduction} \label{sec:introduction}

Optimization problems arise in many fields … \end{document} </text>

info/tech_report_example.tex.1458148906.txt.gz · Last modified: 1998/12/03 12:11 (external edit)