On the extension complexity of scheduling
Hans Raj Tiwary Victor Verdugo Andreas Wiese

	Input:
	Output:
	
	
	
	

On the extension complexity of scheduling
		This work was partially supported by GA ČR project 17-09142S and FONDECYT Regular grant 1170223.
	 
    
	Hans Raj Tiwary Department of Applied Mathematics, Charles University. hansraj@kam.mff.cuni.cz
	Victor Verdugo Department of Mathematics, London School of Economics and Political Science. v.verdugo@lse.ac.uk
	Institute of Engineering Sciences, Universidad de O'Higgins. victor.verdugo@uoh.cl
	Andreas Wiese Department of Industrial Engineering, Universidad de Chile. awiese@dii.uchile.cl
	
    

===========================================================================================================================================================================================================================================================================================================================================================================================================


Linear programming is a powerful method in combinatorial optimization
with many applications in theory and practice. 
For solving a linear program quickly
it is desirable to have a formulation of small size for the given
problem. 
A useful approach for this is the construction of an extended formulation, which
is a linear program in a higher dimensional space whose projection yields the original linear program.
For many problems it is known that a small extended formulation cannot
exist. However, most of these problems are either 𝖭𝖯-hard (like TSP), or only
quite complicated polynomial time algorithms are known for them (like
for the matching problem). 
In this work we study the minimum makespan
problem on identical machines in which we want to assign a set of
n given jobs to m machines in order to minimize the maximum
load over the machines. 
We prove that the canonical formulation for this
problem has extension complexity 2^Ω(n/log n), even if
each job has size 1 or 2 and the optimal makespan is 2. 
This is a
case that a trivial greedy algorithm can solve optimally! 
For the
more powerful configuration integer program 
we even prove a lower bound of 2^Ω(n). 
On the other hand, we show that there is an abstraction
of the configuration integer program admitting an extended formulation of size f()·poly(n,m).
In addition, we give an O(log n)-approximate integral formulation of polynomial
size, even for arbitrary processing times and for the far more general
setting of unrelated machines. 








§ INTRODUCTION




















In order to solve a linear program quickly one is interested in a formulation
with as few variables and constraints as possible. A useful technique
for this are extended formulations.

A polytope Q is said
to be an extended formulation or extension of a
polytope P if P is a linear projection of Q. 
There are many examples
of polytopes P that require many constraints to be described but
that admit extended formulations that are much smaller. 
For instance,
the convex hull of all characteristic vectors of spanning trees in
a graph with n vertex needs 2^Ω(n) inequalities to be
described <cit.>, but it admits an extended
formulation of size O(n^3) <cit.>. The extension
complexity (P) of a polytope P is the minimum number of inequalities needed
to describe an extended formulation of it, see <cit.>
for surveys on the topic.
We study the classical scheduling problem of assigning jobs on identical
machines to minimize the makespan, also known as P||C_max in the scheduling literature. 
We are given a set J of n jobs and a set M of m identical machines
and every job j∈ J has a processing time p_j∈ℕ.
The goal is to assign each job on a machine in order to minimize the maximum load over the machines, 
where the load of a machine is the sum of the processing times of the jobs assigned to it.















 §.§ Our Contribution


A natural formulation for P||C_max, known as the assignment integer program, uses a variable x_ij
for each combination of a machine i and a job j, modelling whether
j is assigned to i. 
The makespan is then modeled by an additional
variable T.
Then, its linear relaxation is given by














min        T              
 
s.t.  ∑_i∈Mx_ij    =1             for all j∈J,


∑_j∈Jx_ijp_j      ≤T            for all i∈M,



x_ij     ≥0             for all i∈M, for all j∈J. 





Lower bounds on the extension complexity. We prove that there are instances with O(n) jobs and machines such
that the convex hull P_I of all integral solutions to the above
linear program has an extension complexity of 2^Ω(n/log n). 
The optimal
solutions form a face of P_I and our bound also holds for this
face and hence for all

polytopes containing it as a face. Our instances satisfy
that p_j∈{1,2} for each job j∈ J and the optimal makespan
is 2. 
Such instances can be solved optimally by a simple greedy algorithm in time O(n+m).
Our key insight is that there are faces of P_I in which
some jobs cannot be assigned to certain machines, e.g., defined via
equalities of the form x_ij=0. Hence, an extended formulation
of P_I also yields such a formulation for the polytope of any
instance of the restricted assignment problem in which we have
the same input as in P||C_max and additionally for each job
j there is a set of machines M_j such that j must be assigned
to a machine in M_j. 
Using a result in <cit.> we show that


there are 3-Bounded-2-SAT instances
such that the polytope describing all feasible solutions for them has extension
complexity 2^Ω(n/log n). 
This might be of independent interest, in particular since 2-SAT can be solved easily in polynomial time.

We reduce these instances to the
restricted assignment problem using a reduction from 3-Bounded-2-SAT
to the restricted assignment problem such that p_j∈{1,2}
for each job j∈ J and the optimal makespan is 2 <cit.>. 

Hence, the polytope of all optimal
solutions has extension complexity 2^Ω(n/log n). By
the above this also holds for the polytope of the corresponding instance
of P||C_max where we ignore the sets M_j. Moreover, we show that
this holds also for each subpolytope containing all optimal solutions.


Then we consider the variation of the above formulation in which we
omit the variable T and the second constraint. The set of integral
points is simply the set of all schedules and the resulting
(polynomial size) LP is integral. 
Note that hence in this space there
exists an integral linear program of small complexity containing all optimal schedules.
However, we show that if we restrict this polytope to the 
convex hull

of all
optimal schedules then resulting polytope again has extension
complexity 2^Ω(n/log n). We show that our bounds are almost
tight by giving an extended formulation of size 2^O(n)m for the
convex hull of all optimal solutions, also for arbitary processing
times and for the formulation in which the makespan T is a variable. 



Approximate schedules: Lower bound. For P||C_max there is a polynomial time (1+ϵ)-approximation algorithm known
and even an . Therefore,
one might wonder whether we can obtain 
a polynomial size extended
formulations that contains all optimal schedules and possibly also some α-approximate schedules, e.g., for α=1+ϵ.
We show that this is not possible for any α<3/2.

Even more, if we ask for a small polytope that contains all α-approximate schedules for some value α we show that this is 
does not exist for any α≤ m^1-ϵ with ϵ>0. Moreover, this is tight in the sense that the set
of all m-approximate schedules is simply the set of all schedules
which admits the polynomial size formulation mentioned above. 
 











Approximate schedules: Upper bound. Despite this negative result, we show that there is a polynomial
size formulation for a polytope that contains all optimal schedules
and some O(log n)-approximate schedules if the target makespan T is fixed. 
Our construction
works for arbitrary job processing times and even in the more complex
setting of unrelated machines, i.e., R||C_max, where for each
combination of a machine i and a job j there is a value p_ij∈ℕ∪{∞}
denoting the processing time of j when it is assigned to machine
i. 

Note that in this case even the setting where p_ij∈{1,2,∞}
is NP-hard [?]. 

Key to our extended formulation is to construct an instance of bipartite
matching in which there is a vertex for each job which can be matched
to vertices representing slots on the machines. 
Then we prove that in the space with the makespan T as a variable such a formulation cannot
exist which yields a separation between the two spaces even though they might appear very similar
at first glance.



Configuration integer program. Finally, we study the configuration integer program which is a popular approach
in scheduling, e.g., <cit.>, with connections
to bin packing, see e.g., <cit.>.
There is a variable y_iC for each combination
of a machine i and a configuration C∈(T) where (T),
contains all sets of jobs whose total processing size does not exceed
an upper bound T on the optimal makespan. While for large T
already the number of variables can be exponential, for constant T
this number is only polynomial and could potentially admit a small
extended formulation. However, we prove that already for the case
that p_j=1 for each job j and T=2 there are instances with
O(n) jobs and machines such that this linear program has extension complexity
2^Ω(n). 
To show this, we establish the maybe surprising
connection that there are such instances for which the corresponding polytope is an
extended formulation of the perfect matching polytope in a graph with
n vertices and the latter has extension complexity 2^Ω(n) <cit.>.


    min    0
    s.t.   ∑_i∈ M∑_C∈(T):j∈ Cy_iC    =1   ∀ j∈ J
       ∑_C∈(T)y_iC    =1   ∀ i∈ M
        y_iC   ∈{0,1}  ∀ i∈ M ∀ C∈(T)


On the other hand, there is an abstraction of the configuration integer program
which instead of assigning a configuration C∈(T) to each machine
i only assigns a pattern that describes how many jobs of
each size are assigned to i but without specifying the actual jobs.
We prove that in contrast to the configuration integer program this abstraction
admits an extended formulation of size O(f(T)·poly(n,m))
for some function f. 



 §.§ Related work


Lower bounds. There are many examples known of polytopes that
do not admit small extended formulations, i.e., formulations
of polynomial size. For instance, Yanakakis <cit.>

proved that for TSP there can be no such formulation that is symmetric,
i.e., stays invariant under permutation of cities. Recently, it became
an active field of research to prove such lower bounds. For instance,
Fiorini et al. <cit.> extended the above result
for TSP to arbitrary (possibly non-symmetric) formulations and Avis et al. <cit.>
showed that neither for 3-SAT, subset sum, 3D-matching, nor for MaxCut
for suspensions of cubic planar graphs,
there can be small extended formulations. Note that all these problems
are 𝖭𝖯-hard and hence a polynomial size extended formulation
for any of them would be very surprising. 


Easy problems with large extension complexity. There are only few problems
in 𝖯 for which the corresponding polytope is known to have large
extension complexity. The most famous example is probably the perfect
matching polytope for which Rothvoss showed in his celebrated result
that it has exponential extension complexity <cit.>.
While the matching problem is in 𝖯, the polynomial time algorithm
for it is highly complicated. 





Also, Rothvoss showed that there exists a family of matroids whose associated polytopes have exponential extension complexity <cit.>. 
This contrasts with the fact that we can optimize over any matroid in polynomial time using the greedy algorithm <cit.>.





prove that there are polytopes with large extension complexity that
correspond to a case of a scheduling 

study a scheduling problem and show that its polytope has large extension
complexity even in a special case that can be solved by a completely
trivial greedy algorithm.



Linear (or indeed convex) optimization of a polytope P can instead
be indirectly done by optimizing over an extended formulation of P.
Therefore having an extended formulation can be of interest if it
results in drastically reducing the number of inequalities. However,
in recent years super-polynomial lower bound on the extension complexity
of polytopes associated with many combinatorial problems have been
established. These bounds have been generalized to various settings,
such as convex extended formulations, approximation algorithms, parametrized
complexity etc. These results are too numerous for a comprehensive
listing, but we refer the interested readers to some of these papers
<cit.>.

Most of the superpolynomial lower bounds that are known for the extension
complexity of polytopes are about polytopes related to various NP-hard
problems <cit.>. The matching polytope is a remarkable exception
over which one can optimize in polynomial time but whose extension
complexity is superpolynomial <cit.>. However the problem of finding
a maximum weight matching in a graph is a very non-trivial problem
even if it is polynomial time solvable. In this article we give an
instance of another optimization problem that is easy to solve but
that have superpolynomial extension complexity. In fact our instances
form the simplest optimization problem that we are aware of that has
superpolynomial extension complexity.













































































































§ EXTENSION COMPLEXITY: LOWER BOUND


Suppose that we are given an instance (J,M) of P||C_max.
We consider the linear program defined by (<ref>)-(<ref>) in Section <ref>.   
Denote by P(J,M) the convex hull of all its integral solutions.
In the remainder of this section we prove the following theorem. 

For every n there exists an instance
(J,M) of P|p_j∈{1,2}|C_max with O(n) jobs, O(n)
machines, and (J,M)=2 such that xc(P(J,M))≥2^Ω(n/log n). 



Our high level approach is as follows. It follows easily from known
results that there are 2-SAT formulae Φ with O(n) variables
and clauses such that the extension complexity the polytope of all
satisfying assignments is at least 2^Ω(n/log n) [?].
We transform Φ to an equivalent 3-Bounded-2-SAT formula Φ',
i.e., in Φ' each variable appears at most three times and the
solutions to Φ are in one-to-one correspendence to the solutions
to Φ'. For Φ' we invoke a reduction in [?] from 3-Bounded-2-SAT
to the restricted assignment problem, i.e., the problem of scheduling
a set of jobs J on a set of machines M to minimize the makespan
such that for each job j∈ J there is a set of machines M_j⊆ M
and we are allowed to assign j only to the machines in M_j.
For the resulting instance let J and M denote the set of jobs
and machines, respectively. We consider the polyhedron P(J,M) which
in a sense pretends that we are allowed to assign each job to any
machine. Then we argue that there is a face P'(J,M) of P(J,M)
in which each job j is assigned to a machine in M_j and in
which the makespan is 2. The extension complexity of P(J,M) is
at least as large as the extension complexity of P'(J,M). Finally,
we show that there is a projection of P'(J,M) to the set of all
satisfying assignments of Φ, implying that P'(J,M) and thus
P(J,M) has large extension complexity.


Let n∈ℕ. For any given SAT formula Φ with n
variables we define the polytope SAT(Φ) as the convex
hull of all satisfying assignments, i.e., SAT(Φ):=conv({y∈{0,1}^n:Φ(y)=1}).
We use the following theorem that follows easily from <cit.>. 

For every n∈ℕ there exists
a 2-SAT formula Φ with O(n) variables and O(n) clauses
such that xc((Φ))≥2^Ω(n/log n). Each
clause of Φ contains exactly two literals.



Let n∈ℕ. In <cit.>
it is shown that there exists a graph G=(V,E) with n vertices
such that for its independent set polytope P_G it holds that
(P_G)≥2^Ω(n/log n), i.e., P_G⊆[0,1]^n
is the convex hull of all incidence vectors of independent sets of
G. Moreover, the degree of G is bounded by a global constant
that is independent of n. Based on G we construct a 2-SAT formula
Φ. For each node v∈ V we introduce a variable x_v,
the intuition being that x_v is true if v is in the independent
set. For each edge {u,v}∈ E we introduce a clause ( x_v∨ x_u),
modelling that not both u and v can be in the independent set.
The number of variables is n and since G has bounded degree
each variable appears in at most O(1) clauses. Hence, the number
of clauses is also O(n). Each satisfying assignment of Φ
corresponds to an independent set of G and vice versa. Therefore,
xc((Φ))≥2^Ω(n/log n).



Let Φ denote the formula due to Theorem <ref>.
We transform Φ into an equivalent 3-Bounded-2-SAT formula Φ'
using a standard reduction

i.e., Φ' is a 2-SAT formula in which each variable appears at
most three times. Let x_i be a variable in Φ and assume
that x_i occurs k times. We introduce k new variables x_i^(1),...,x_i^(k)
and for each ℓ∈[k] we replace the ℓ-th occurrence of x_i
with x_i^(ℓ). Additionally, we add the clauses ( x_i^(ℓ)∨ x_i^(ℓ+1))
for each ℓ∈{1,...,k-1}

and the clause ( x_i^(k)∨ x_i^(1)). Hence, in any satisfying
assignment of the resulting formula, either x_i^(ℓ)=1 for
each ℓ∈[k] or x_i^(ℓ)=0 for each ℓ∈[k]. We do
this transformation with each variable in Φ. Let Φ' denote
the resulting formula. By construction, we have that Φ' has
O(n) variables and O(n) clauses, using that both quantities
are linear in the number of literals in Φ and the latter is
bounded by O(n). By construction, each variable appears exactly
three times and at most two times positively and at most two times
negatively. Also, each clause contains exactly two literals.



 §.§ Reduction to the restricted assignment problem


Construction. Next, based on Φ' we construct an instance of the restricted
assignment problem. We invoke the reduction from <cit.>.
For each variable x in Φ' we introduce a machine i(x),
a machine i( x), and a job j(x). The job j(x) has processing
time p_j(x)=2 and it can be assigned only on i(x) and i( x),
i.e., M_j(x)={i(x),i( x)}. 
The intuition behind is that if j(x)
is scheduled on i(x) then x is true and if j(x) is scheduled
on i( x) then x is false. For each clause c we introduce
one machine i(c). For each variable x that occurs in c we
introduce a job j(c,x) with p_j(c,x)=1. If x occurs positively
in c then we define M_j(c,x)={i(c),i( x)}, otherwise
we define M_j(c,x)={i(c),i(x)}. Finally, for each clause c
we introduce a job j(c) with p_j(c)=1 and M_j(c)={i(c)}.

Since the total number of variables and clauses is O(n), we introduced
O(n) jobs and machines. 


Let J' denote
the set of jobs and let m̅ denote the number of machines
defined so far. 
We want that in solutions with makespan 2 each machine has a load of exactly 2. 
To this end,
we introduce a set D of 2m̅-∑_j∈ J'p_j dummy jobs of length
1 each. 
For each dummy job j∈ D, it can be assigned to any machine, i.e.,
M_j=M.


Correctness. For each satisfying assignment of Φ' there is a schedule of
makespan 2: If a variable x is assigned to be x=1 in the satisfying
assignment then we schedule j(x) on machine i(x), otherwise
we schedule j(x) on machine i( x). Consider a clause c.
There must be at least one variable that satisfies c. For each
such variable x, if x occurs positively in c then we assign
j(c,x) on i( x), otherwise we assign j(c,x) on i(x).
For each variable y that does not satisfy c we assign j(c,y)
to i(c). Also, we assign j(c) to i(c). Using that each variable
appears at most twice positively and at most twice negatively, one
can check that the resulting makespan is 2. Finally, we assign the
dummy jobs to the machines such that each machine still has a makespan
of at most 2. 
This is the optimal solution since the largest processing time is 2.
One can also easily show that if there is a solution of makespan 2
then there exists a satisfying assignment for Φ', see <cit.>
for details.




  
*Faces of scheduling polytope.

Let J and M denote the set of jobs and machines in the construction
above, respectively. Also, let M_j denote the set of allowed
machines for each job j∈ J. We consider the polyhedron P(J,M).
Note that P(J,M) ignores the sets M_j of allowed machines
for each job j. We argue that there is a face P'(J,M) of P(J,M)
such that each vertex of P'(J,M) corresponds to a schedule in which
each job j∈ J is assigned on a machine in M_j and the makespan
is 2. Observe that the inequalities ∑_j∈ J∑_i∈ M∖ M_jx_ij≥0
and T≥2 are valid inequalities for P(J,M). Hence, the set

    P'(J,M)=P(J,M)∩{(x,T):∑_j∈ J∑_i∈ M∖ M_jx_ij=0 and T=2}

is a face of P(J,M). Also, xc(P'(J,M))≤xc(P(J,M)).




We describe now a linear projection f:P'(J,M)→SAT(Φ')
of P'(J,M) to (Φ'). Given a point x∈ P'(J,M) we
define that the component of f(x) corresponding to the variable
y_ℓ equals to x_i(y_ℓ),j(y_ℓ). By the construction
above and the proof of correctness of the reduction, for each integral
point y∈SAT(Φ') there exists a feasible schedule
for (J,M) with makespan 2 in which each job j is assigned to
a machine in M_j. Additionally, for each variable y in Φ'
it holds that if y=1 then j(y) is assigned on machine i(y) in this schedule.
Thus, there exists an integral point x∈ P'(J,M) such that f(x)=y.
Similarly, for each integral point x∈ P'(J,M) we have that f(x)∈SAT(Φ').
Thus, f(P'(J,M))=SAT(Φ') and therefore, ((Φ'))≤xc(P'(J,M)).
Finally we give a linear projection g:(Φ')→(Φ).
Recall that for each variable x_i in Φ we introduced a
set of new variables x_i^(1),...,x_i^(k) in Φ'. By
construction, in each satisfying assignment for Φ' all these
variables x_i^(1),...,x_i^(k) have the same value. Therefore,
we define that the component of g(x) corresponding to x_i
equals x_i^(1) for each variable x_i in Φ. We obtain
g(SAT(Φ'))=SAT(Φ). Therefore, ((Φ))≤((Φ')).
Hence, xc(P(J,M))≥xc(P'(J,M))≥((Φ'))≥((Φ))≥2^Ω(n/log n).
This completes the proof of Theorem <ref>.

Since already the face P'(J,M) of P(J,M) containing the optimal solutions
to (J,M) has extension complexity 2^Ω(n/log n)
we obtain the following corollary.




 §.§ Omitting some non-optimal solutions.


The polyhedron P(J,M) above contains all optimal solutions
to (J,M) and also all non-optimal solutions and we proved
that it has high extension complexity. This raises the question whether
one can construct an integral polyhedron P̅(J,M) with P̅(J,M)⊆ P(J,M)
with small extension complexity such that P̅(J,M) contains
all optimal solutions to (J,M) and potentially some non-optimal
solutions. Our construction above rules this out since already the
face of all optimal solutions has extension complexity 2^Ω(n/log n). 


Assume that we had such a polyhedron P̅(J,M). We define P̅'(J,M):=P̅(J,M)∩{(x,T)|∑_j∈ J∑_i∈ M∖ M_jx_ij=0∧ T=2}
which is a face of P̅(J,M). Then P̅'(J,M) contains
exactly the optimal solutions to (J,M) and the above maps f,g
yield a linear projection to SAT(Φ). Hence, the extension
complexity of P̅(J,M) is at least 2^Ω(n/log n).



For every n there exists an instance
(J,M) of P|p_j∈{1,2}|C_max with O(n) jobs, O(n)
machines, and (J,M)=2 such that for any integral polyhedron
P̅(J,M)⊆ P(J,M) that contains all optimal and possibly
also some other solutions to (J,M) it holds that xc(P̅(J,M))≥2^Ω(n/log n). 





 §.§ Extensions


Above we proved that P(J,M) has large extension complexity. The
polyhedron P(J,M) is defined using the variable T which represents
an upper bound on the makespan of the respective solution. This raises
the question whether there exist compact extended formulations in
the space defined only via the variables x, without the variable
T. 
Formally, we consider the polyhedron 

    Q(J,M)=conv({ x∈{0,1}^M× J:∑_i∈ Mx_ij=1  for all  j∈ J})

describing the set of all schedules, including all optimal ones. 


    min    0
    s.t.   ∑_i∈ Mx_ij    =1   ∀ j∈ J
        x_ij   ∈{0,1}   ∀ j∈ J ∀ i∈ M


One can easily show that its extension complexity is O(nm) by simply
taking its linear relaxation. Observe that Corollary <ref>
rules out such a polyhedron in the space lifted with the variable T.

The polyhedron Q(J,M) has extension
complexity O(nm). 
























This follows by observing that the extreme points of the linear relaxation are integral. 

Let x be a feasible point in the relaxation such that x_ij∈(0,1) for some machine i∈ M and some job j∈ J. 
Due
to Equality (<ref>) there must be another
machine ℓ i such that x_ℓ j∈(0,1). For sufficiently
small ϵ>0 we define a new solution x̃ =x+ε (1_ij-1_ℓ j),
where 1_a is the canonical vector with value 1 at entry a and zero otherwise.






Similarly, we define a new solution x̂=x+ε (1_ℓ j-1_i j).




We can find ε>0 such that x̃,x̂≥0 and
x=1/2(x̃ +x̂), and hence x is not an extreme point.
Therefore,
the extension complexity of Q(J,M) is O(nm).




However, when we minimize the makespan, we are interested only in
the set of all integral points in Q(J,M) that correspond to optimal
solutions. Note that their convex hull 
corresponds
to the face of P(J,M) containing all points (x,T) with T=.
Due to Corollary <ref> this polytope has
extension complexity 2^Ω(n/log n). We can strengthen this
statement. In the instance (J,M) constructed above the optimal
makespan is 2 and any non-optimal solution has a makespan of at least
3. Thus, all integral polytopes Q̅(J,M)⊆ Q(J,M) that
contain all optimal solutions to (J,M) and possibly some (3/2-ϵ)-approximate
solutions have large extension complexity. Note that this contrasts
the fact that P||C_max admits an EPTAS <cit.>.

Let ϵ>0 with ϵ≤1/2.
For every n there exists an instance (J,M) of P|p_j∈{1,2}|C_max
with O(n) jobs, O(n) machines, and (J,M)=2 such that for
any integral polytope Q̅(J,M)⊆ Q(J,M) whose vertices
consist of all optimal solutions and possibly some (3/2-ϵ)-approximate
solutions to (J,M) it holds that xc(Q̅(J,M))≥2^Ω(n/log n). 


Next, we show that there cannot be an integral polytope of polynomial
extension complexity containing all α-approximate
solutions of Q(J,M) for any α≤ n^1-ϵ. 

For every n∈ℕ and every
α≥1 there exists an instance (J',M') of P|p_j∈{1,2}|C_max
with O(α n) jobs and O(α n) machines such that for
any integral polytope Q̃(J,M)⊆ Q(J,M) whose vertices
are all α-approximate solutions to (J',M') it holds that
xc(Q̃(J,M))≥2^Ω(n/log n). In particular,
if α=n^1/ϵ for some ϵ>0 then the instance
has n̅=O(n^1+1/ϵ) jobs and machines and xc(Q̃(J,M))≥2^n̅^Ω(ϵ). 






Assume by contradiction that
such a polytope exists and suppose that α∈ℕ. Take
the instance (J,M) defined above. We add (2α-2)|M| dummy
jobs of length 1 each, denote them by . Also, we add (α-1)|M|
dummy machines, denote them by . Note that the optimal makespan
is still 2 and thus any α-approximate solution has makespan
2α. Let (J',M') denote the resulting instance and observe
that it has O(α n) jobs and machines. We consider Q̃(J',M').
Then for each dummy machine i∈ the inequality ∑_j∈ J'x_ij≥0
is a valid inequality. Also, consider an assignment of the jobs in
 to the machines M'∖ such that each machine i∈ M'∖
gets a load of 2α-2 in this way. Formally, we define a map
g:→ M'∖ such that |g^-1(i)|=2α-2
for each i∈ M'∖. Then for each job j∈ the
inequality x_g(j)j≤1 is a valid inequality. Therefore, the set Q̃'(J',M') defined as

    Q̃(J,M)∩{x:∑_j∈ J'x_ij=0   for all  i∈ and  x_g(j)j=1   for all  j∈}

is a face of Q̃(J,M). Therefore, Q̃'(J',M') contains
exactly the solutions in which the dummy jobs are assigned as described
by the map g and the non-dummy jobs J=J'∖ are assigned
such that they give a load of 2 on each machine. Thus, there is a
linear projection of Q̃'(J',M') to the polytope Q̅(J,M)
as defined in Theorem <ref>. This implies that
(Q̃(J',M'))≥(Q̃'(J',M'))≥(Q̅(J,M))≥2^Ω(n/log n).




Finally, we can show that our lower bounds from Theorem <ref>
and Corollary <ref> are almost tight by giving
an upper bound of 2^O(n)m. 

























Let (J,M) be an instance of P||C_max
with n jobs and m machines. Let  denote
the convex hull of the vertices corresponding to all optimal solutions
to (J,M) in It holds that (Q̅(J,M))≤2^O(n)m
and (P(J,M))≤2^O(n)m. 





by defining an extended formulation of the convex hull of all optimal
solutions to Q(J,M) of size 2^O(n)m. By an easy transformation
this yields an extended formulation of the convex hull of all optimal
solutions to P(J,M) of the same size.

In the following we prove Theorem <ref>. 
Given an instance (J,M),
we first describe
a dynamic program that computes a solution to (J,M) in time 2^O(n)m
for some given target makespan T, assuming that such a solution
exists. 
Then based on it we define an extended formulation of Q̅(J,M)
of size 2^O(n)m. 


Dynamic program.  We introduce a cell (J',m',T) for each
subset J'⊆ J of jobs and each integer m'∈{1,…,m}.
In (J',m',T) we want to store a schedule for the jobs J' on
the machines {m',…,m} such that each machine has a makespan of
at most T, assuming that such a schedule exists. 
Consider the case m'=m, that is, we look for a schedule in the single machine m. 
For each set of jobs J' with p(J')≤ T we store
in the cell (J',m,T) the schedule that assigns all jobs in J'
to machine m. For each set of jobs J' with p(J')>T we store
 in the cell (J',m,T), indicating that no feasible schedule
exists for (J',m,T). 
Now suppose we are given a cell (J',m',T) with
m'<m. If there is a subset J”⊆ J' with p(J”)≤ T
such that in the cell (J'∖ J”,m'+1,T) we stored a schedule
(and not ) then in (J',m',T) we store the schedule that
assigns J” on machine m' and the schedule in the cell (J'∖ J”,m'+1,T)
on the machines {m'+1,…,m}. If no such set J”⊆ J' exists
then we store  in (J',m',T). Finally, if we stored a schedule
(J,1,T) then we output this schedule, otherwise (J,1,T) contains
 and we output that there is no schedule for J on m machines
with makespan at most T. 
This dynamic program table has 2^nm cells
and evaluating one cell takes 2^n time, which yields a total
running time of 2^O(n)m.

In the transition above, for each cell (J',m',T) we took an arbitrary
subset J” such that p(J”)≤ T and (J'∖ J”,m'+1,T)
does not contain . In fact, we can construct any schedule
of makespan at most T in this way if for each cell (J',m',T)
we choose for J” the set of jobs that the respective schedule
assigns on machine m'. In the sequel, we define a graph G
with 2^O(n)m vertices including two special vertices s and t such
that any path from s to t corresponds to a solution that the
above dynamic program might compute for suitable choices for J”. 
Then we define
a linear program whose vertices are exactly these paths which then
yield an extended formulation to Q̅(J,M) if we choose T=.


Construction of the graph. Let T≥.
Let 𝒱_T be the set of cells (J',m',T) of the dynamic program table such that there exists a schedule for the jobs J'
on machines {m',…,m} of makespan at most T. 
For convenience we add a dummy element (∅,m+1,T) to 𝒱_T.
Then, in our graph G the set of vertices corresponds to 𝒱_T.
For each J',J̅'⊆ J,m'∈{1,...,m}
we introduce an arc ((J',m',T),(J̅',m'+1,T)) if and
only if (J',m',T),(J̅',m'+1,T)∈𝒱_T and there
is a set J”⊆ J' with p(J”)≤ T such that J̅'=J'∖ J”.
Let s=(J,1,T) be the source and t=(∅,m+1,T) the sink. 
We call 𝒜_T the set of arcs, and then G=(𝒱_T,𝒜_T).







Every s-t path in the graph G corresponds to a schedule S
of makespan at most T. 
Furthermore, every schedule S of makespan at most T induces an s-t path in G.






Let P be an s-t path with vertices

(J'_1,1,T),(J'_2,2,T),...,(J'_m,m,T),(J'_m+1,m+1,T),

where J'_1=J and J'_m+1=∅.
Then, our construction of G guarantees that p(J'_ℓ+1∖ J'_ℓ)≤ T
for each ℓ∈{1,...,m}. 
Thus, for each arc ((J'_ℓ,ℓ,T),(J'_ℓ+1,ℓ+1,T))
we assign the jobs in J'_ℓ∖ J'_ℓ+1 to machine ℓ which yields
a schedule of makespan at most T. 
Conversely, consider a schedule
S of makespan at most T and for each i∈{1,…,m} let J_i⊆ J be the jobs that are assigned to machine i in S. 
Then,
there is a path that for each i∈{1,...,m+1}
visiting the vertex (⋃_ℓ=i^mJ_ℓ,i,T). 
Observe that for each i∈{1,…,m} we have that ((⋃_ℓ=i^mJ_ℓ,i,T),(⋃_ℓ=i+1^mJ_ℓ,i+1,T))∈𝒜_T since ⋃_ℓ=i^mJ_ℓ∖⋃_ℓ=i+1^mJ_ℓ=J_i and p(J_i)≤ T.





































Extended formulation. 
We define a linear program with a variable y_a for
each arc a∈𝒜_T. We add constraints
that describe a flow in G such that we send exactly one unit of
flow from s to t. In particular, we require that one unit of
flow leaves s, one unit of flow enters t, and on all other vertices
there is flow conservation. 
For every job j∈ J, let 𝒥^T_ij={((J',i,T),(J̅'̅,i+1,T))∈𝒜_T:j∈ J'∖J̅'}
which are the arcs such that if one of them is contained in an s-tpath P then in the schedule corresponding to P job j∈ J is
assigned on machine i∈ M.
Then, consider the following linear program

	 ∑_a∈δ^+(v)y_a-∑_a∈δ^-(v)y_a                        =    0      for all  v ∈𝒱_T∖{s,t},
1      if v=s,
 -1      if v=t.          


  ∑_a∈𝒥_ij^Ty_a     =  x_ij     for all  i∈M,  for all  j∈J,

  x_ij     ≥0         for all  i∈M,  for all  j∈J,

  y_a     ≥0        for all a∈𝒜_T, 



where for each vertex v, 
we have that δ^+(v),δ^-(v) denote the out-going and in-going edges at v∈𝒱_T, respectively.


























For T=, we project the polytope of the linear program above
to Q̅(J,M)
by defining x_ij according to (<ref>) for each job j∈ J and each machine i∈ M.



By Lemma <ref> this yields an extended formulation of size 2^O(n)m. 
We describe now how to extend the above to an extended formulation
for P(J,M) of size 2^O(n)m. 
For that, we show how to modify the dynamic program used for constructing the extended formulation of Q̅(J,M).

Note that for the makespan of
any feasible solution there are only 2^n options since the makespan
equals the sum of the processing times of the jobs on some machine
and there are only 2^n options for this quantity. Let 𝒯
be a set containing all these options. We define a cell (J',m',T)
for each subset J'⊆ J of jobs, each integer m' with
m'∈{1,…,m} and for each T∈𝒯. 
For each such cell in
which the previous dynamic program above does not store  we define a vertex 

like above and also arcs 

as before. 
Note that there are no arcs between two vertices (J',m',T),
(J̅',m̅',T̅) with TT̅. 
We define
a new source vertex s' and introduce an arc (s',(J,1,T)) for each
T∈, assuming that the vertex (J,1,T) exists. 
Similarly, we
define a new sink vertex t' and an arc ((∅,m+1,T),t')
for each T∈. 
A path from s' to t' represents
the choice of a makespan T∈ and defining a schedule with makespan
at most T. 



As before, consider a linear program computing s-t paths in this new graph, using a flow formulation and y variables as before, that is, constraints (<ref>) and (<ref>).
We lift this linear program by adding a variable T
and introducing a new constraint 

    T≥∑_T∈T· y_(s',(J,1,T)).

Then we project each point (y, T) in the resulting polyhedron
to the point (x, T)∈ P(J,M) by setting 
x_ij=∑_T∈∑_a∈𝒥_ij^Ty_a for each i∈ M and each j∈ J.







That concludes the proof of the theorem.

 we define T̃ to be the upper bound on the obtained makespan
(denote by T in Figure <ref>).


This completes the proof of Theorem <ref>.





§ APPROXIMATE POLYNOMIAL SIZE EXTENDED FORMULATION



In the previous section we showed
in Corollary <ref> that there can be no polynomial
size extended formulation of Q(J,M) whose vertices are exactly
all α-approximate solutions, for essentially any α.
However, in this section we show that there is a small extended formulation
that contains all optimal schedules and some approximate
schedules. 
Our formulation works even in the more general setting of unrelated
machines, i.e., R||C_max, where the processing time of a job
j can depend on the machine i that it is assigned to and for
each such combination the input contains a value p_ij∈ℕ∪{∞}.
In this setting the polytope Q(J,M) defined exactly in the same as way as before,
however, now a solution x is optimal if ∑_j∈ Jx_ijp_ij≤
for each machine i∈ M.



Construction of the extended formulation. In the sequel let T≥. The intuition behind our construction
is the following. We define a bipartite graph G in which we have
one vertex v_j for each job j∈ J and n vertices w_(i,1),...,w_(i,n)
for each machine i∈ M. 
Each vertex w_(i,ℓ) corresponds to
a slot for machine i. We search for a matching that assigns
each job vertex v_j to some slot vertex w_(i,ℓ) and we
allow this assignment if and only if p_ij≤ T/ℓ, i.e., we
introduce an edge {v_j,w_(i,ℓ)} if and only if p_ij≤ T/ℓ.
The intuition is that in  for each machine i there can be
at most one job j assigned to i with p_ij∈(T/2,T], at
most two jobs j with p_ij∈(T/3,T] and more general at most
ℓ jobs j with p_ij∈(T/(ℓ+1),T]. Hence, there is
a matching in G that corresponds to . On the other hand,
in any matching the total processing time of the jobs on any machine
i is bounded by T+T/2+T/3+...+T/n=T· H_n=O(Tlog(n)) 
which is at most · O(log(n)) if T=O() (e.g., set T= or
set T to be the makespan found by a 2-approximation algorithm
for R||C_max <cit.>).


We define an integral polytope that models this bipartite matching. 
For each (i,ℓ)
let J_iℓ be the subset of jobs j whose vertex v_j
has an edge incident to w_(i,ℓ). For each edge {v_j,w_(i,ℓ)}
we have a variable y_jiℓ that intuitively indicates whether
job j is assigned to the slot (i,ℓ). On top of this, we project
the resulting polytope to the space of the variables x of
Q(J,M) which yields Q̅(J,M).



∑_j∈J_iℓy_jiℓ     ≤1             for all i∈M, for all ℓ∈{1,…,n},


∑_i∈M∑_ℓ=1^ny_jiℓ     =1             for all j∈J, 

∑_ℓ:j∈J_iℓy_jiℓ     =x_ij             for all i∈M, for all j∈J,


x_ij     ≥0             for all i∈M, for all j∈J,

y_ijℓ     ≥0             for all i∈M, for all j∈J,  for all ℓ∈{1,…,n}.




 Given an instance (J,M) of R||C_max
there exists an extended formulation of size O(n^2m) for an integral
polytope Q̅(J,M)⊆ Q(J,M) whose vertices correspond
to all optimal solutions and some O(log n)-approximate solutions
to (J,M). 



Consider an optimal schedule and let x be its corresponding solution in Q(J,M). 
For each machine i∈ M, let J_i(x) be the subset of job vertices v_j in G such that x_ij=1, that is, J_i(x)={v_j:x_ij=1}, and consider G_i the bipartite subgraph of G that is induced by the vertices J_i(x) ∪{w_(i,1),...,w_(i,n)}.
We check that there exists a matching in G_i that covers J_i(x).
Consider W⊆ J_i(x).
There exists at least one job in t∈ W with processing time at most T/|W|, otherwise x would exceed the makespan T in machine i.
Therefore, job t is connected to w_(i,ℓ) for every ℓ≤ |W|, and its degree in G_i is at least |W|.
In particular, W is connected to at least |W| slots in the bipartite subgraph G_i.
By Hall's theorem we conclude that exists a matching in G_i covering every job in J_i(x).
For every job in J_i(x) we define y_jiℓ=1 if v_j is connected to w_(i,ℓ) in the matching, and y_jiℓ=0 otherwise.
By construction the solution (x,y) satisfies the constraints in the program above.






On the other hand, consider a vertex solution (x,y).
The integrality of (x,y) comes from the fact that the linear program restricted to y variables is a bipartite matching formulation.
We bound the makespan of the schedule obtained from x.
For each machine i∈ M, we have

    ∑_j∈ Jp_ijx_ij=∑_j∈ Jp_ij∑_ℓ:j∈ J_iℓy_jiℓ=∑_ℓ=1^n∑_j∈ J_iℓp_ijy_jiℓ.

For every j∈ J_iℓ, we have that p_ij≤ T/ℓ.
This, together with constraint (<ref>) allows us to upper bound the last summation above by


    ∑_ℓ=1^nT/ℓ∑_j∈ J_iℓy_jiℓ≤ T∑_ℓ=1^n1/ℓ=T· H_n=O(Tlog n).






§ EXTENSION COMPLEXITY OF CONFIGURATION-LP


An alternative way to formulate P||C_max as an integer linear program is
via a configuration integer program. For a given target makespan T≥0 we define
the set of all configurations (T) to be all subsets of
jobs whose total processing time is at most T, i.e., (T):={L⊆ J:∑_j∈ Lp_j≤ T}.
For each machine i∈ M and each configuration C∈(T) we
introduce a variable y_iC∈{0,1} that models whether machine
i gets exactly the jobs in configuration C assigned to it. Denote
by P_config(J,M,T) the convex hull of all solutions
to the integer program below.









	
	 ∑_i∈M∑_C∈(T):j∈C y_iC                           =  1           for all  j∈J,   

	 	 ∑_C∈(T) y_iC                           =  1           for all  i∈M,   

  

						    y_iC                  ∈{0,1}           for all i∈M,  for all  C∈(T).


For arbitrary values of T the number of variables of P_config(J,M,T)
can be exponential in the input length. However, for constant T
there are only a polynomial number of variables (and constraints)
since the number of possible configurations is bounded by n  T=n^O(T).
This raises the questions whether P_config(J,M,T) admits
a small extended formulation for such values of T. 
If T=2 and p_j∈{1,2} for each j∈ J Theorem <ref> implies a lower bound of 2^Ω(n/log n)
since there is an easy projection of the configuration-LP to P(J,M). We strengthen this to the case where p_j=1 for each j∈ J and to a lower bound of 2^Ω(n).





For every n∈ℕ there is an instance (J,M,T) of P||C_max
with n machines and O(n) jobs such that the polytope P_config(J,M,T)
has an extension complexity of 2^Ω(n). It holds that T=2
and p_j=1 for each j∈ J. 




For every n∈ℕ we construct an instance of (J,M,T) by T=2,
M contains n machines, and J contains 2n jobs with p_j=1
for each j∈ J. The set (T) is thus the set of all pairs
of jobs. We show that there is a linear map that projects each solution
to P_config(J,M,T) to a matching in a complete graph
on 2n vertices. Let G=(V,E) be the complete graph on 2n vertices,
i.e., G=K_2n. Consider the perfect matching polytope of G, given by

    PM(G)=conv({χ_M∈ℝ^E:M⊆ E   is a perfect matching}).

We define a linear map f:P_config(J,M,T)→PM(G)
as follows: for each edge e={u,v}∈ E we define f_e(y):=∑_i∈ My_i{u,v}.
For each vertex y of P_config(J,M,T) it holds that
f(y)∈PM(G) and therefore f(P_config(J,M,T))⊆PM(G).
On the other hand, let x be a vertex of PM(G),
i.e., x represents a perfect matching {{u_1,v_1},{u_2,v_2},...,{u_n,v_n}}
in G. Then we can construct a vertex y of P_config(J,M,T)
such that f(y)=x as follows: assume that the machines are numbered
{1,...,n}. Then for each machine i we define y_i{u_i,v_i}=1
and y_iC=0 for each C∈(T)∖{{u_i,v_i}}.
Then f(y)=x. Rothvoss showed that the extension complexity of PM(G)
is 2^Ω(n) <cit.>. Our construction implies
that P_config(J,M,T) is an extended formulation for
PM(G). Therefore, the extension complexity of P_config(J,M,T)
is also 2^Ω(n).















































§ AN EXTENDED FORMULATION WITH SMALL PARAMETERIZED SIZE


In this section we consider an abstraction of the configuration integer program that exhibits low extension complexity parameterized by T.

Instead of encoding configurations as subsets of jobs, we consider how many jobs in the configuration have a certain processing time p.
That is, in this context a configuration is a multiset C of {p_j:j∈ J}, and let m(p,C) be the multiplicity of p in C, namely, the number of times that p appears in C. 
For every p∈{p_j:j∈ J}, let n_p be the number of jobs in J with processing time equal to p.
We denote by (T) the set of configurations having total processing time at most T. 
The key fact about this encoding is that two or more machines can be scheduled in the same configuration and 
there are fewer solutions overall than for the configuration-LP. 


As before, we propose a formulation where for every combination of machine i∈ M and configuration C∈(T) we have variable y_iC indicating whether i is scheduled according to C.
That is,



	
	 ∑_C∈(T) y_iC                           =  1           for all i∈M,   

  
  ∑_i∈M∑_C∈(T) m(p,C)y_iC      =   n_p         for all  p ∈{  p_j: j∈J } , 

						    y_iC                  ∈{0,1}           for all i∈M,  for all  C∈(T).





The extension complexity of the integer hull for the above formulation is O(f(T)·poly(n,m)) for some function f.







We define a program deciding for each configuration C∈(T) how many machines get configuration C such that we have enough 
slots for all jobs, that is,






	
	 ∑_C∈(T) z_C                           =  m         ,      

  
  ∑_C∈(T) m(p,C)z_C      =   n_p         for all  p ∈{  p_j: j∈J } , 

						    z_C                  ∈ℕ               for all  C∈(T).


We denote P_*(J,M,T) the convex hull of the solutions to the integer program above. 
Since the number of processing times ranges in [1,T], the total number of configurations in (T) is upper bounded by T^T.




There exists a function h such that the number of vertices of the polytope P_*(J,M,T) is upper bounded by h(T).


Observe that the lemma above holds even when number of machines and jobs on the right hand side of the integer program above are not necessarily bounded by a function of T, which is in general the case. 
Now we can prove Theorem <ref> via a Dantzig-Wolfe reformulation with a variable for each of the h(T) vertices of P_*(J,M,T).
Since the size of P_*(J,M,T) is bounded by h(T), we have at most that many variables of this type.
Then, we model the values of the variables y_iC as the solution to a suitable transshipment problem.


































































































Consider an optimal schedule and let x be its corresponding solution in Q(J,M). 
For each machine i∈ M, let J_i(x) be the subset of job vertices v_j in G such that x_ij=1, that is, J_i(x)={v_j:x_ij=1}, and consider G_i the bipartite subgraph of G that is induced by the vertices J_i(x) ∪{w_(i,1),...,w_(i,n)}.
We check that there exists a matching in G_i that covers J_i(x).
Consider W⊆ J_i(x).
There exists at least one job in t∈ W with processing time at most T/|W|, otherwise x would exceed the makespan T in machine i.
Therefore, job t is connected to w_(i,ℓ) for every ℓ≤ |W|, and its degree in G_i is at least |W|.
In particular, W is connected to at least |W| slots in the bipartite subgraph G_i.
By Hall's theorem we conclude that exists a matching in G_i covering every job in J_i(x).
For every job in J_i(x) we define y_jiℓ=1 if v_j is connected to w_(i,ℓ) in the matching, and y_jiℓ=0 otherwise.
By construction the solution (x,y) satisfies the constraints in the program above.






On the other hand, consider a vertex solution (x,y).
The integrality of (x,y) comes from the fact that the linear program restricted to y variables is a bipartite matching formulation.
We bound the makespan of the schedule obtained from x.
For each machine i∈ M, it holds that 

    ∑_j∈ Jp_ijx_ij=∑_j∈ Jp_ij∑_ℓ:j∈ J_iℓy_jiℓ=∑_ℓ=1^n∑_j∈ J_iℓp_ijy_jiℓ.

For every j∈ J_iℓ, we have that p_ij≤ T/ℓ.
This, together with constraint (<ref>) allows us to upper bound the last summation above by


    ∑_ℓ=1^nT/ℓ∑_j∈ J_iℓy_jiℓ≤ T∑_ℓ=1^n1/ℓ=T· H_n=O(Tlog n).



































Let w
be a vertex of the polytope P_*(J,M,T). We argue that there are
at most h(T) possibilities for w for some suitable function
h. For a value g(T) to be defined later define a new point w^1
by setting w_C^1:=w_C if w_C≤ g(T) and w_C^1:=0
otherwise for each configuration C∈(T). Define w^2=w-w^1≥0,
which is feasible for the following integer linear program 



∑_C∈(T)z_C     =m-∑_C∈(T)w_C^1  ,              


∑_C∈(T)m(p,C)z_C     =n_p-m(p,C)w_C^1            for all p∈{p_j:j∈J}, 

z_C     ∈ℕ             for all C∈(T).

One can easily show that w^2 is a vertex of the integer hull
of the solutions to the program above, since otherwise w is non-trivial
convex combination of feasible solutions of P_*(J,M,T). Let '(T)⊆(T)
denote the configurations in the support of w^2. We identify
each configuration C∈'(T) with a vector which is the column
in the matrix of the program above corresponding to C, i.e., the
first entry of each such vector is a 1 and the other entries are given
by the values m(p,C)_p∈{p_j:j∈ J}. If the vectors in
'(T) are linearly independent then the above IP has a unique
solution. Hence, there is at most one vertex w of P_*(J,M,T)
of the form w=w^1+ŵ where ŵ is a solution to the
above IP. In the sequel we argue that it cannot be that the vectors
in '(T) are linearly dependent if g(T) is sufficiently
large. Then the claim of the lemma follows since the vector w^1
satisfies that w_C^1∈{0,...,g(T)} for each C∈(T)
and the number of such vectors can be bounded by a value h(T). 

If the vectors in '(T) are not linearly independent then
there exists a configuration C∈'(T) and a set of linearly
independent vectors C_1,...,C_k∈'(T) and values λ_1,...,λ_k
such that C=∑_i=1^kλ_iC_i. Let Λ denote
the smallest value Λ'∈ℕ such that Λ'C=∑_i=1^kΛ'λ_iC_i
such that Λ'λ_i∈ℤ for each i. If g(T)≥Λ
and g(T)≥Λλ_i for each i then we can write w^2
as the convex combination of two integral vectors and hence w^2
is not a vertex. To ensure the former we define g(T) to be the
maximum over all values Λ and Λλ_i that
we can obtain in this way, i.e., by selecting one C∈(T),
expressing it as a linear combination C=∑_i=1^kλ_iC_i
of a set of linearly independent configurations C_1,...,C_k∈(T),
and finding the smallest value Λ'∈ℕ such that
Λ'λ_i∈ℤ. Note that the number of values
Λ' obtained in this way is finite and hence g(T) is well-defined
(and finite). 

In the following we prove that the number of vertices of the integer
hull of the program above is bounded by the value of a certain function
on T. For every possible S⊆(T), we restrict the
program above to find a solution z with support contained in S.
Observe that the number of possible supports is bounded by 2^|(T)|≤2^T^T.
Consider the columns indexed by the configurations in S on the
matrix representation of the left-hand side of the program. In the
case where they are linearly independent we have a unique possible
vertex obtained from that support. If the columns are not linearly
independent, consider a configurations C∈ S and S'⊆ S
such that the columns indexed by S' are linearly independent. Therefore,
for a solution z to the program restricted to have support S,
we have that for every R∈ S' there exists a unique value λ_S
such that z_C=∑_R∈ S'λ_Rz_R, and let Λ_S(T)=min{α∈:α·λ_R∈ℤ for all R∈ S'}.
conclusion missing 




Let V(J,M,T) be the set of vertices in the polytope P_*(J,M,T).
By Lemma <ref>, there exists a function h such that the size V(J,M,T) is bounded by h(T).
Since we can restrict the optimization problem to its set of vertices, we consider the linear program obtained by lifting the integer program above by the Dantzig-Wolfe reformulation using the set of vertices V(J,
M,T).
For each vertex v∈ V(J,M,T), consider a variable λ_v indicating whether we pick or not the vertex solution v.  
In addition, for each configuration we consider as before a variables z_C indicating how many times the configuration C is used.
Finally, for each combination of machine i∈ M and configuration C∈(T) we have a variable y_iC indicating whether machine i is scheduled according to C.
 
The idea behind the extended formulation is to first select a vertex v∈ V(J,M,T) by using the Dantzig-Wolfe reformulation in the variables (λ,z), which provides for each configuration C∈(T) the number of times, z_C, that is used. 
Then we formulate a transportation problem between machines and configurations satisfying the offer z_C for each configuration.

More specifically, consider a complete bipartite graph G where we have one vertex v_i for each machine i∈ M, and we have a vertex w_C for each configuration C∈(T).
For each vertex w_C we have an offer z_C, and every vertex v_i has a demand of 1.
The variable y_iC indicates whether the demand of the machine vertex v_i is satisfied by the configuration vertex w_C. 
More specifically, consider 


	
	 ∑_v∈V(J,M,T)    λ_v                       =  1,         

  
  ∑_v∈V(J,M,T)vλ_v      =   z,       


	∑_C∈(T) z_C                           =  m,          

  
  ∑_C∈(T) m(p,C)z_C      =   n_p         for all  p ∈{  p_j: j∈J } , 

						    ∑_i∈My_iC                  = z_C               for all  C∈(T),

						    ∑_C∈(T)y_iC                  = 1               for all  i∈M,


						     λ_v                  ≥0               for all  v∈V(J,M,T),
	
						    z_C                  ≥0               for all  C∈(T),
	
						    y_iC                  ≥0               for all i∈M,  for all  C∈(T).								    		

Observe that constraints (<ref>) and (<ref>) guarantees that the total demand equals the total offer in the transportation problem over G.
It holds that a vertex (λ,z,y) of the linear program above is integral. 

If not, suppose that λ is fractional, otherwise the integrality of λ implies the integrality of z and in turns the integrality of y since the transportation program in the graph G given by constraints (<ref>)-(<ref>) is integral. 
If λ is fractional, z is a non-trivial convex combination of the vertices {v∈ V(J,M,T):λ_v>0}, and each of these vertices is feasible for the constraints (<ref>)-(<ref>),
which implies that (λ,z) is a convex combination of the vectors {(e_v,v):λ_v>0}, where e_v∈{0,1}^V(J,M,T) is the canonical vector that is 1 for entry v and zero otherwise.
For each v such that λ_v>0, the constraints (<ref>)-(<ref>) solve a transportation problem between the machine vertices {v_i:i∈ M} and the configurations vertices {w_C:C∈(T)}, where the offer for w_C is equal to z_C.
The vertices with positive offer are given by 𝒞_v={w_C:v_C>0}, and then any solution to this problem is a convex combination of the integral solutions to the transportation problem over G.
Since every solution is supported over M×𝒞_v, and therefore we contradicted the fact that (λ,z,y) is a vertex of the polytope. 




plain

