History: QMIP and others
(Jan Wolf, Jan. 2017)
QLP / QIPi: In [194] a QLP formulation was used to model
problems from the domain of realtime scheduling [57], with the
goal to reduce the inflexibility of static scheduling in hard
realtime systems. One of the fundamental features of realtime
systems is the uncertain nature of execution times of tasks and
the presence of complex timing constraints among them. In
traditional models variable execution times are modeled through
fixed worstcase values and relationships are limited to those
that can be represented by precedence graphs [206]. Using QLPs
as modeling tool allows to schedule tasks with varying execution
times, represented by universally quantified variables, and
complex timing constraints among tasks described by linear
constraints.
In this context, a first polynomial time algorithm to solve
QLPs based on quantifier elimination techniques was proposed
in [108] for a restricted class of constraints [194], which
are a subset of totally unimodular constraint systems [197].
For arbitrary linear constraints the worstcase time complexity
of the proposed algorithm is double exponential [197, 125].
Subramani proposed a framework to formalize scheduling problems
in realtime systems using QLPs in [207]. There he focussed on
the variability in the execution times, complex relationships
between tasks using arbitrary linear constraints and different
scheduling schemes – static (98QLPs), costatic (89QLPs) or
parametric (alternating quantifier changes) – depending on the
information available when dispatching. A detailed introduction
to QLPs and methodologies to solve them are available in [209,
147, 88]. QIPs were studied in [210], where a number of special
cases where analyzed from the perspective of computational
complexity. In that paper the authors discussed conditions
under which QIPs can be relaxed to QLPs without altering the
solution space.
Research in this context was also supported by the Deutsche
Forschungsgemeinschaft (DFG). The DFG founded project
“Erweiterung mathemtische Optimierungsmethoden zur Lösung
PSPACEvollständiger Probleme mit Hilfe quantifizierter linearer
Programme” at TU Darmstadt dealt with the development of
algorithms to solve QIPs based on extended LP and QLPtechniques.
The DFG founded Collaborative Research Centre (SFB) 805
“Sonderforschungsbereich 805  Beherrschung von Unsicherheit
in lasttragenden Systemen des Maschinenbaus” at TU Darmstadt
deals with the control of uncertainty in mechanical systems.
In this context QMIPs have been used to model and optimize
process chains under uncertainty. Also in the context of game
modeling QIPs can be applied. In [89] the PSPACEcomplete
twoperson game Gomoku was modeled with the help of an QIP
formulation, in [147] the model was adopted to the PSPACEcomplete
twoperson game Connect6 resulting in a 0/1QIP that was
solved with an extended variant of the algorithm proposed in [88].
Recently, extensions of traditional QLPs were presented in [91],
where the standard quantification was extended to implications
of quantified linear systems, called quantified linear
implications (QLI). QLPs and QLIs that arise when universally
quantified variables are unbounded were studied in [185].
Whereas in the above citations the focus was on analyzing
various special cases of the general problem, with a view on
subclasses that are tractable, our focus lies on general QLPs
with two or multiple stages without any restrictions to the
quantification sequence or the constraint system. Furthermore,
our focus lies on QLP optimization problems, whereas the above
citations consider quantified decision problems in general.
Optimization Under Uncertainty has experienced rapid
development in both theory and practice from the very beginning
in the 1950s, starting with the seminal works of Beale [15],
Dantzig [72], Bellman [16] as well as Charnes and Cooper [65].
The particular importance of optimization under uncertainty was
also demonstrated in the seminal paper by BenTal and Nemirovski
[23], where they showed in a detailed computational study that
even a small perturbation of the problem data can make the
nominal optimal solution completely meaningless from a practical
viewpoint. We quote from their case study:
“In realworld applications of linear programming, one cannot
ignore the possibility that a small uncertainty in the data can
make the usual optimal solution completely meaningless from a
practical viewpoint.”
Due to limited computational capabilities in the past, decision
models often replaced those uncertainties with averages or best
estimates but recent computational advantages greatly expanded
the range of optimization techniques under uncertainty. Today
stochastic programming and robust optimization – two
fundamentally different approaches that address optimization
with data uncertainty – are the most prominent modeling paradigms
and presently the subject of intense research in this field.
The main difference lies in the type of uncertainty that is
handled by the two methodologies. Stochastic programming assumes
the uncertainty to follow a probability distribution, while
robust optimization in contrast is concerned with models that
contain deterministic setbased uncertainties [36]. In the
following we give a brief introduction to stochastic programming
and robust optimization and compare them with quantified linear
programming.
Stochastic Programming The approach for uncertainty
quantification used in stochastic programming (see, e.g.
[128, 174, 47, 189] and the references therein) is the
representation of random parameters in the input data (c, A, b)
by random variables. This approach has a long and active history
dating at least as far back as Dantzigs original paper [72] and
draws upon a variety of traditional operations research
techniques. During the last four decades a vast quantity of
literature on the subject has appeared (see, e.g. [218, 217] for
a stochastic programming bibliography maintained by Maarten van
der Vlerk). A variety of stochastic programming applications can
be found in [224]. The underlying optimization problem can be a
linear program, a (mixed) integer program, but also a nonlinear
program. Usually, stochastic programming models are furthermore
subdivided in recourse models and chance constraint models.
Recourse Models The more important and widely studied case, where
most of the applications reported in the literature belong to and
which has strong similarities to QLPs, is that of a stochastic
linear program with recourse, which first appeared in Beale [15]
and Dantzig [72]. These problems arise when some of the decision
variables must be taken before the outcomes of some (or all)
random events are known, and some after they become known.
Recourse variables represent decisions that can be made on a
“wait and see” basis, after the uncertainty is resolved, and
they allow to adapt a solution to the specific outcome observed.
Stochastic programming problems with recourse can be essentially
divided into twostage and multistage problems
(TSSLPs and MSSLPs). In the former, a set of initial decisions
are taken first, followed by a random event. After this, recourse
decisions, which are based on this event, are taken. The
multistage problem, accordingly consists of multiple stages,
with a random event occurring between each stage.
Chance Constraints Models The essence of recourse models
is that infeasibilities in the second or higher stages are
allowed and can be compensated at a certain penalty. In chance
constraint models, developed by Charnes and Cooper [65], the
focus lies on the reliability of the system in contrast. This
reliability is expressed as a minimum requirement on the
probability of satisfying constraints. The resulting program is
called a chanceconstrained stochastic program. Under certain
assumptions on the probability distribution (like e.g. Normal,
Cauchy, Uniform), chance constraints can be converted into a
deterministic equivalent form and then be treated as in a
traditional recourse problem as mentioned above. More details on
chanceconstrained stochastic programming can be found in [174].
Over the last 20 years, also stochastic programming with integer
or binary recourse variables has received tremendous research
attention in both application and algorithmic aspects. However,
compared to the continuous case of a TSSLP or MSSLP, relatively
little is known on theory and algorithms for linear mixedinteger
stochastic programming in general. Given that duality results do
not hold in general IP and MIP formulations, it is also difficult
to extend current algorithms for the linear case in order to
generate cutting planes, except when only the first stage
contains integer variables or other special cases. A survey of
developments can be found in [198, 199], a stochastic integer
programming bibliography with publications from the years
19962007 can be found at [217].
Compared to stochastic programming models, a QLP can be
interpreted as a worstcase MSSLP with fixed recourse and only
the righthand side being affected by uncertainties. The main
advantage of quantified linear and integer programming is that
uncertainty can be easily modeled without detailed knowledge of
the underling probability distribution. Furthermore, while SP
models minimize the expected value of an objective function with
respect to a set of scenarios, QLPs minimize an objective
function with respect to the possible worst case (maximum loss).
There is a recursive nodebased definition for QLPs, similar as
for MSSLPs, and it has been shown how a DEP of a QLP can be
constructed.
Robust Optimization In contrast to stochastic programming,
robust optimization is a more recent approach in the context of
optimization under uncertainty, in which the uncertainty model
is not stochastic, but rather deterministic and setbased.
Instead of seeking to immunize the solution in some probabilistic
sense to stochastic uncertainty, here the decisionmaker
constructs a solution that is valid for any realization of
uncertainty in a given set [36]. While applications of stochastic
programming have been reported over many years in the literature,
robust optimization appeared recently, with most research in the
past ten years (see, e.g. [24, 38, 42, 18, 36, 215] and the
references therein). The roots can be found in the field of
robust control and in the work of Soyster [204]. However, high
interest in both theoretical aspects and practical applications
started in the first place with the work of BenTal and Nemirovski
[20, 21], and ElGhaoui et al [109, 110] in the late 1990s.
The idea of robust optimization is to define a socalled
uncertanty set U for the uncertain parameters in the input
data (c, A, b) and then to require that the constraint system
should hold for any possible realization of the data from U. The
optimization problem modeling this requirement is called the
robust counterpart problem (RCP), an optimal solution of the RCP
is called robust optimal solution. The robust optimization
methodology can be applied to any optimization problem (e.g.
quadratically constrained quadratic programs (QCQPs) or
semidefinite programs (SDPs)), in which the uncertain data is
known to lie in a given uncertainty set. Though it is still a
relatively new approach, it has already proved very useful in
many applications. In [18] a list of problem classes for which
robust optimization is applicable is listed.
One might imagine that the addition of robustness to a general
optimization problem comes at the expense of a significantly
increased computational complexity, and indeed, the RCP of an
arbitrary convex optimization problem is in general intractable
[18]. Nevertheless, depending on the structure of the underlying
optimization problem and the uncertainty set U , the corresponding
RCP can be solved or at least be approximated in polynomial time
for many application cases [21]. BenTal and Nemirovski [22]
showed that the RCP of a linear optimization problem is
essentially always tractable for many practical uncertainty sets.
Due to the results in [18], in the case of robust linear
optimization, the objective and the righthand side of the
constraints can be assumed to be deterministic and w.l.o.g.
constraintwise uncertainty can be assumed. It hence suffices
to focus on single constraints of a special form. These are
referred as the subproblems which must be solved in order to
solve the entire RCP. Of course, a major modeling decision
concerns the choice of the uncertainty set U and the resulting
RCP might not longer be an LP [17]. In particular, the RCP of an
LP with a polyhedral uncertainty set becomes a linear programming
problem, while the RCP of an LP with an ellipsoidal uncertainty
set becomes a secondorder cone problem respectively [24]. Other
interesting results have been achieved recently, e.g. under very
natural assumptions, robust LPs can be formulated as semidefinite
programming problems and thus solved by a polynomial time
approximation scheme [21, 18]. Several attempts to extend the
ideas to discrete robust optimization have been e.g. made in
[37, 40, 39]. However, unlike the case of continuous robust
optimization, the conditions on the uncertainty sets are rather
restrictive to still ensure the efficient solvability of the RCP
as shown in [39]. Therefore, approximation techniques based on
piecewise linearization are currently the means of choice for
such problems [42].
While stochastic programming problems can result in large
deterministic linear models when considering many scenarios, the
RCP models grow only slightly when uncertainty is added in general
and therefore, they can often be solved efficiently. Another
crucial difference is that in the stochastic programming approach
constraints may be violated with a certain probability
(chanceconstraints) or at a given penalty (recourse model),
whereas robust optimization is associated with hard constraints,
which must be satisfied whatever the realization of the data
(c, A, b) in the uncertainty set U is [22]. Thus, in many cases a
singlestage robust optimization model tends to be to conservative
[11], especially in situations where some recourse decisions can
be made after the uncertainty is revealed. To address this issue,
twostage models – also called robust adjustable or adaptable
optimization – were proposed e.g. in [19]. However, twostage
problems are very challenging to compute, even formulations with
LP problems in both stages can be NPhard [19]. Nevertheless, in
many realworld problems, decisions and uncertainty are often
repeatedly interwoven over time and RO model are not capable to
handle this efficiently due to the difficulty in incorporating
multiple stages [215].
From the viewpoint of quantified linear and integer programming,
robust optimization problems can be viewed as QLPs with one
quantifier change (98), whereas in QLPs multiple quantifier
changes occur in general. However, from the viewpoint of robust
optimization, where arbitrary uncertainty sets may appear (though
not necessarily being tractable at all), the uncertainty set of
QLPs is a simple hyperrectangle.
Other LPbased solution techniques Apart from stochastic
programming and robust optimization as mentioned above, typical
solution approaches for problems that are affected by uncertainty
are sensitivity analysis [179], LPbased approximation techniques
[155], dynamic programming [16], and the exploration of
Markovchains [237] for example. Sensitivity analysis is a simple
classical method of addressing uncertainty, which is typically
applied as a postoptimization tool for quantifying the goodness
or robustness of a solution, e.g. the change in cost for small
perturbations in the underlying problem data. It is not
particularly helpful for generating solutions that are robust to
data changes in the sense of an a priori ensured feasibility when
the problem parameters vary within the prescribed uncertainty set
[234]. A further possibility to deal with these uncertainties is
an approximation where a given probability distribution is
aggregated to a single estimated number. Then, the optimum
concerning these estimated input data can be computed with the
help of traditional optimization tools. In some fields of
application, as e.g. the fleet assignment problem of airlines,
this procedure was successfully established [117]. In other
fields, like production planning and control, this technique
could not be successfully applied, although mathematical models
do exist [172]. Dynamic programming was developed by Richard
Bellman in the early1950s [16] and is a computational method to
deal with multistage decision processes in a dynamic environment.
In fact, decisionmaking under uncertainty was the original and
intended application of this technique [164]. Dynamic programming
usually refers to simplifying a decision by breaking it down into
a sequence of decision steps over time. It starts solving all
subproblems at the final stage and then uses the solution to
recursively compute solutions for higher stages until the original
problem at the root is solved eventually. For more information on
solution approaches in the context of optimization under
uncertainty we refer the reader to [193, 41] and the references
therein.
Quantification of Variables and Constraints The explicit
quantification of variables and constraints allows to express
many problems that cannot be modeled using classical modeling
paradigms. Quantifiers are a powerful tools to model uncertainty
or adversarial situations. For example, if a decision is based
on a value that is not exactly known in advance, one might look
for robust solutions that are valid for all possible values that
might occur. As the efforts of extending languages with
quantifiers have not only been made for linear programs in terms
of QLPs and QIPs, we give an overview in the following, where we
briefly sketch the achievements from other fields in this context.
Boolean Satisfiablility (SAT) and Constraint
Satisfaction (CSP)
Many realworld problems are combinatorial search problems that
can be represented in terms of decision variables and constraints.
Besides integer programming (IP), boolean satisfiability problems
(SAT) and constraint satisfaction problems (CSP) are very
successful frameworks that are used to model and solve these
problems.
The SAT problem is one of the most important and extensively
studied problems in computer science. Given a propositional
boolean formula, the SAT problem asks for an assignment of
variables such that the formula evaluates to true, or a proof that
no such assignment exists [10, 44]. SAT is one of the classic
problems in computer science, it is of theoretical interest
because it is the canonical NPcomplete problem [70] (cf.
Section 4.2 for details). Apart from its high theoretical
relevance, SAT has many practical applications as e.g. model
checking, design verification, or AI planning [152, 68].
Integer Programming (IP) generalizes the standard SAT problem,
by allowing the possible values for the variables to be chosen
from an arbitrary finite set, and allowing the constraints to be
arbitrary linear constraints rather than just clauses. Whereas
the solution approaches for IPs often rely on LPrelaxations
combined with branchandcut procedures to find optimal integer
solutions, the core of most modern SAT solvers is the
DavisPutnamLogemannLoveland (DPLL) algorithm [78, 77], which
is essentially a depthfirstsearch with some pruning techniques
like unit propagation [235], conflictdriven clause learning
[153], and back tracking [150].
The constraint satisfaction problem (CSP) also generalizes the
standard SAT problem, by allowing the possible values for the
variables to be chosen from an arbitrary finite set. Furthermore,
the constraints are allowed to to be arbitrary constraints rather
than just clauses or linear constraints and thus, CSP also
generalizes IP. The CSP problem consists of a set of variables,
each with a finite domain of values and a set of constraints on
subsets of these variables.
CSPs provide a general framework to express a wide variety of
combinatorial search problems and they play an important role in
many areas of computer science and artificial intelligence [52].
They also find their application in the Operations Research
community in the context of Location Planning, Scheduling, Car
Sequencing, Cutting Stock Problems, Vehicle Routing, Timetabeling,
Rostering and many more [54]. SAT, CSP and the IP feasibility
problem are three different paradigms to model and solve
combinatorial search problems, and as each of the problem
classes is NPcomplete, they can be reduced among each others in
polynomial time [225, 32, 238]. However, each paradigm has its
strengths and weaknesses. Due to their complementary strengths,
there is an increasing belief that hybrid methods may often
perform better than pure methods. An approach to integrate
techniques from constraint programming and (mixedinteger)
programming in order to exploit the strengths of both fields, is
the constraint integer programming framework SCIP [2, 4].
However, there are classes of problems containing uncertainty
that cannot be expressed within these frameworks. QCSPs and QSAT,
which are the quantified extensions of CSP and SAT and allow for
universally quantified variables, make it possible to model such
problems that contain uncertainty. As a result, these extensions
have been attracting significant interest in recent years. In the
following, we highlight the key ideas of both approaches and
specify their basic solution strategies.
Bibliography
[10] B. Aspvall, M. F. Plass, and R. E. Tarjan. A lineartime
algorithm for testing the truth of certain quantified boolean
formulas. Inf. Process. Lett., 8(3):121–123, 1979. Erratum:
Information Processing Letters 14(4): 195 (1982).
[11] A. Atamtürk and M. Zhang. Twostage robust network flow
and design under demand uncertainty. Operations Research,
55(4):662–673, 2007.
[15] E. M. L. Beale. On minimizing a convex function subject
to linear inequalities. J. Roy. Statist. Soc. Ser. B., 17,
1955.
[16] R. Bellman. Dynamic Programming. Princeton University
Press, Princeton, NJ, USA, 1. edition, 1957.
[17] A. BenTal, D. den Hertog, A. De Waegenaere, B. Melenberg,
and G. Rennen. Robust solutions of optimization problems
affected by uncertain probabilities. Manage. Sci.,
59(2):341–357, Feb. 2013.
[18] A. BenTal, L. El Ghaoui, and A. Nemirovski. Robust
optimization. Princeton University Press, 2009.
[19] A. BenTal, A. Goryashko, E. Guslitzer, and A. Nemirovski.
Adjustable robust solutions of uncertain linear programs.
Mathematical Programming, 99(2):351–376, Mar. 2004.
[20] A. BenTal and A. Nemirovski. Robust truss topology design
via semidefinite programming, research report 4/95. In
Optimization Laboratory, Faculty of Industrial Engineering and
Management, Technion The Israel Institute of Technology,
Technion City, Haifa 32000, 1995.
[21] A. BenTal and A. Nemirovski. Robust convex optimization.
Mathematics of Operations Research, 23:769–805, 1998.
[22] A. BenTal and A. Nemirovski. Robust solutions of
uncertain linear programs. Operations Research Letters,
25:1–13, 1999.
[23] A. BenTal and A. Nemirovski. Robust solutions of linear
programming problems contaminated with uncertain data.
Mathematical Programming, 88:411–424, 2000.
[24] A. BenTal and A. Nemirovski. Robust optimization 
methodology and applications. Mathematical Programming,
92(3):453–480, 2002.
[32] H. Bennaceur. A comparison between sat and csp techniques.
Constraints, 9(2):123–138, Apr. 2004.
[36] D. Bertsimas, D. B. Brown, and C. Caramanis. Theory and
applications of robust optimization. SIAM Rev., 53(3):464–501,
Aug. 2011.
[37] D. Bertsimas and M. Sim. Robust discrete optimization and
network flows. Mathematical Programming, 98(13):49–71, 2003.
[38] D. Bertsimas and M. Sim. The price of robustness.
OperationsResearch, 52(1):35–53,2004.
[39] D. Bertsimas and M. Sim. Robust Discrete Optimization
Under Ellipsoidal Uncertainty Sets. 2004.
[40] D. Bertsimas and A. Thiele. A robust optimization approach
to supply chain management. In IPCO, pages 86–100, 2004.
[41] D. Bertsimas and A. Thiele. Robust and DataDriven
Optimization: Modern DecisionMaking Under Uncertainty. In
Tutorials on Operations Research, INFORMS, 2006.
[42] H.G. Beyer and B. Sendhoff. Robust optimization A
comprehensive survey. Computer Methods in Applied Mechanics and
Engineering, 196:3190–3218, 2007.
[44] A. Biere, M. Heule, H. van Maaren, and T. Walsh, editors.
Handbook of Satisfiability, volume 185 of Frontiers in
Artificial Intelligence and Applications. IOS Press, 2009.
[47] J. R. Birge and F. Louveaux. Introduction to stochastic
programming. Springer series in operations research. Springer,
New York, 1997.
[52] F. Börner, A. A. Bulatov, H. Chen, P. Jeavons, and A. A.
Krokhin. The complexity of constraint satisfaction games and
qcsp. Inf. Comput., 207(9):923–944, 2009.
[54] S.C. Brailsford, C.N. Potts and B.M. Smith.
Constraintsatisfaction problems: Algorithms and applications.
European Journal of Operational Research, 119(3):557–581, 1999.
[57] P. Brucker. Scheduling Algorithms. Springer, Secaucus,
NJ, USA, 3rd edition, 2001.
[65] A. Charnes and W. W. Cooper. ChanceConstrained
programming. Management Science, 6(1):73–79, 1959.
[68] K. Claessen, N. Ee ́n, M. Sheeran, N. Sörensson ,A. Voronov,
K.Akesson. Satsolving in practice, with a tutorial example
from supervisory control. Discrete Event Dynamic Systems,
19(4):495–524, 2009.
[70] S. A. Cook. The complexity of theoremproving procedures.
In Proceedings of the third annual ACM symposium on Theory of
computing, STOC ’71, pages 151–158, New York, NY, USA, 1971. ACM.
[72] G. B. Dantzig. Linear programming under uncertainty.
Management Science, 1(34):197– 206, 1955.
[77] M. Davis, G. Logemann, and D. W. Loveland. A machine
program for theoremproving. Commun. ACM, 5(7):394–397, 1962.
[78] M. Davis and H. Putnam. A computing procedure for
quantification theory. Jounal of the ACM, 7(3):201–215, 1960.
[88] T. Ederer, U. Lorenz, A. Martin, and J. Wolf. Quantified
linear programs: a computational study. Proc. of the 11th Ann.
Europ. Symp. on Algorithms (ESA 2012), pp. 203–214, 2011,
Springer.
[89] T. Ederer, U. Lorenz, T. Opfer, and J. Wolf. Modeling
games with the help of quantified integer linear programs. In
ACG, pages 270–281, 2011.
[91] P. Eirinakis, S. Ruggieri, K. Subramani,and
P.J.Wojciechowski: Computational complexity of inclusion
queries over polyhedral sets. In ISAIM, 2012.
[108] R. Gerber, W. Pugh, and M. Saksena. Parametric
dispatching of hard realtime tasks. IEEE Transactions on
Computers, 44:471–479, 1995.
[109] L. E. Ghaoui and H. Lebret. Robust solutions to
leastsquares problems with uncertain data, 1997.
[110] L.E. Ghaoui, F. Oustry and H. Lebret. Robust solutions
to uncertain semidefinite programs. SIAM J. OPTIMIZATION,
9(1):33–52, 1998.
[117] S. Grothklags. Fleet assignment with connection dependent
ground times. In Proc. of the 11th Ann. Europ. Symp. on
Algorithms (ESA 2003), pages 667–678, 2003.
[125] T. Huynh, L. Joskowicz, C. Lassez, and J.L. Lassez.
Reasoning about linear constraints using parametric queries.
In FSTTCS, pages 1–20, 1990.
[128] P. Kall and S. Wallace. Stochastic programming.
WileyInterscience series in systems and optimization. Wiley,
1994.
[135] D.E. Knuth and R.W.Moore. An analysis of alphabeta
pruning. Artif.Intell.,6(4):293–326, 1975.
[147] U. Lorenz, A.Martin and J. Wolf. Polyhedral and
algorithmic properties of quantified linear programs. In Proc.
of the 18th Ann. Europ. Symp. on Algorithms (ESA 2011,
pages 512–523, 2010.
[150] S. Malik and L. Zhang. Boolean satisfiability from
theoretical hardness to practical success. Commun. ACM,
52(8):76–82, Aug. 2009.
[152] J. MarquesSilva. Practical applications of boolean
satisfiability. In Workshop on Discrete Event Systems (WODES).
IEEE Press, 2008.
[155] N. Megow and T. Vredeveld. Approximation results for
preemtive stochastic online scheduling. Proc. of the 14th Ann.
Europ. Symp. on Algorithms (ESA 2006, 2006).
[164] C. H. Papadimitriou. Games against nature. J. Comput.
Syst. Sci., 31(2):288–301, 1985.
[172] Y. Pochet and L. A. Wolsey. Production Planning by Mixed
Integer Programming (Springer Series in Operations Research
and Financial Engineering). Springer, Secaucus, NJ, USA, 2006.
[174] A. Prekopa. Stochastic Programming. Mathematics and Its
Applications. Springer, 1995.
[179] J. Renegar. Some perturbation theory for linear
programming. Mathematical Programming, 65:73–91, 1992.
[185] S. Ruggieri, P. Eirinakis, K. Subramani, and P. J.
Wojciechowski. On the complexity of quantified linear systems.
Theor. Comput. Sci., 518:128–134, 2014.
[189] A.Ruszczyn ́ski and A. Shapiro. Stochastic Programming.
Handbooks in operations research and management science.
Elsevier, 2003.
[193] N. V. Sahinidis. Optimization under uncertainty:
Stateoftheart and opportunities. Computers and Chemical
Engineering, 28:971–983, 2004.
[194] M. C. Saksena. Parametric Scheduling for Hard Realtime
Systems. PhD thesis, College Park, MD, USA, 1994.
[197] A. Schrijver. Theory of linear and integer programming.
John Wiley and Sons, Inc., New York, NY, USA, 1986.
[198] R. Schultz. Stochastic programming with integer variables.
Math. Progr.,97:285–309,2003.
[199] S. Sen. Algorithms for Stochastic MixedInteger
Programming Models. Handbooks in OR and MS.
[204] A. L. Soyster. Convex Programming with SetInclusive
Constraints and Applications to Inexact Linear Programming.
Operations Research, 21(5):1154–1157, 1973.
[206] K. Subramani. Parametric scheduling  algorithms and
complexity. In HiPC, pages 36–46, 2001.
[207] K. Subramani. A specification framework for realtime
scheduling. In SOFSEM, pages 195–207, 2002.
[209] K. Subramani. Analyzing selected quantified integer
programs. In IJCAR, pages 342–356, 2004.
[210] K.Subramani. Partially clair voyant scheduling for
aggregate constraints. JAMDS,9(4):225– 240, 2005.
[215] A. Thiele, C. Murat, and V. Gabrel. Recent advances in
robust optimization: An overview. European Journal of
Operational Research, 2013.
[217] M. H. van der Vlerk. Stochastic integer programming
bibliography. World Wide Web,
www.eco.rug.nl/mally/biblio/sip.html,
19962007. [Online;
ac cessed 1July2014].
[218] M. H. van der Vlerk. Stochastic programming bibliography.
World Wide Web, http:// www.eco.rug.nl/mally/spbib.html,
19962007. [Online; accessed 1July2014].
[224] S. W. Wallace and W. T. Ziemba. Applications of
Stochastic Programming. MPSSIAM Series on Optimization.
Society for Industrial and Applied Mathematics, 2005.
[225] T. Walsh. Sat v csp. In R. Dechter, editor, CP, volume
1894 of Lecture Notes in Computer Science, pages 441–456.
Springer, 2000.
[234] H.X. Yu and L. Jin. An brief introduction to robust
optimization approach. Int. J. Pure Appl. Math.,
74(1):121–124, 2012.
[235] R. Zabih and D. A. McAllester. A rearrangement search
strategy for determining propositional satisfiability. In H. E.
Shrobe, T. M. Mitchell, and R. G. Smith, editors, AAAI, pages
155–160. AAAI Press / The MIT Press, 1988.
[237] L. Zhang, H. Hermanns, F. Eisenbrand, and D. Jansen.
Flow faster: Efficient decision algorithms for probabilistic
simulations. Logical Methods in Computer Science, 4(4), 2008.
[238] N.F. Zhou, M. Tsuru, and E. Nobuyama. A comparison of cp,
ip, and sat solvers through a common interface. In Proceedings
of the 2012 IEEE 24th International Conference on Tools with
Artificial Intelligence  Volume 01, ICTAI ’12, pages 41–48,
Washington, DC, USA, 2012. IEEE Computer Society.

Downloads
Yasol for Mac OS
Yasol for Linux
Yasol for Windows
Instances
