5.258. min_size_full_zero_stretch

DESCRIPTIONLINKSAUTOMATON
Origin

Derived from the unit commitment problem

Constraint

πš–πš’πš—_πšœπš’πš£πšŽ_πšπšžπš•πš•_πš£πšŽπš›πš˜_πšœπšπš›πšŽπšπšŒπš‘(π™Όπ™Έπ™½πš‚π™Έπš‰π™΄,πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚)

Arguments
π™Όπ™Έπ™½πš‚π™Έπš‰π™΄πš’πš—πš
πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚πšŒπš˜πš•πš•πšŽπšŒπšπš’πš˜πš—(πšŸπšŠπš›-πšπšŸπšŠπš›)
Restrictions
π™Όπ™Έπ™½πš‚π™Έπš‰π™΄β‰₯0
π™Όπ™Έπ™½πš‚π™Έπš‰π™΄β‰€|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|
πš›πšŽπššπšžπš’πš›πšŽπš(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚,πšŸπšŠπš›)
Purpose

Given an integer π™Όπ™Έπ™½πš‚π™Έπš‰π™΄ and a sequence of variables πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ enforce π™Όπ™Έπ™½πš‚π™Έπš‰π™΄ to be greater than or equal to the size of the smallest full stretch of zero of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ or to |πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚| if no full stretch of zero exists.

A stretch of zero is a maximum sequence of zero, while a full stretch of zero is a stretch of zero that is neither located at the leftmost nor at the rightmost border of the sequence of variables πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚. The size of a stretch of zero is the number of zero of the stretch.

Example
(2,0,2,0,0,0,2,1,0,0,3)

FigureΒ 5.258.1 shows the smallest full stretch of zero associated with the example. The πš–πš’πš—_πšœπš’πš£πšŽ_πšπšžπš•πš•_πš£πšŽπš›πš˜_πšœπšπš›πšŽπšπšŒπš‘ constraint holds since the size of the smallest full stretch of zero of the sequence 0 2 0 0 0 2 1 0 0 3 is greater than or equal to 2.

Figure 5.258.1. Illustration of the Example slot: smallest full stretch of zero in bold and red (π™Όπ™Έπ™½πš‚π™Έπš‰π™΄=2); note that the leftmost stretch of zero of size 1 is ignored since it is located at one of the two extremities of the sequence 0 2 0 0 0 2 1 0 0 3.
ctrs/min_size_full_zero_stretch-1-tikz
Typical
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|>2
πš›πšŠπš—πšπšŽ(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›)>1
|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚|-πšŠπš–πš˜πš—πš_πšπš’πšπš_0(πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš›)>1
Symmetries
  • Items of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚ can be reversed.

  • An occurrence of a value of πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚.πšŸπšŠπš› that is different from 0 can be replaced by any other value that is also different from 0.

Counting
Length (n)2345678
Solutions9821137190263640337850291188987201

Number of solutions for πš–πš’πš—_πšœπš’πš£πšŽ_πšπšžπš•πš•_πš£πšŽπš›πš˜_πšœπšπš›πšŽπšπšŒπš‘: domains 0..n

ctrs/min_size_full_zero_stretch-2-tikz

ctrs/min_size_full_zero_stretch-3-tikz

Length (n)2345678
Total9821137190263640337850291188987201
Parameter
value

1-916025754507288244119330432
29917628754993296667220958912
3-6417629005043697539421117888
4--62529005047297617821132416
5---77765047297622721133568
6----11764997622721133632
7-----209715221133632
8------43046721

Solution count for πš–πš’πš—_πšœπš’πš£πšŽ_πšπšžπš•πš•_πš£πšŽπš›πš˜_πšœπšπš›πšŽπšπšŒπš‘: domains 0..n

ctrs/min_size_full_zero_stretch-4-tikz

ctrs/min_size_full_zero_stretch-5-tikz

See also

common keyword: πšœπšπš›πšŽπšπšŒπš‘_πš™πšŠπšπš‘Β (sequence).

Keywords

characteristic of a constraint: joker value, automaton, automaton with counters, automaton with same input symbol.

combinatorial object: sequence.

constraint network structure: alpha-acyclic constraint network(3).

Automaton

FigureΒ 5.258.2 depicts the automaton associated with the πš–πš’πš—_πšœπš’πš£πšŽ_πšπšžπš•πš•_πš£πšŽπš›πš˜_πšœπšπš›πšŽπšπšŒπš‘ constraint.

Figure 5.258.2. Automaton of the πš–πš’πš—_πšœπš’πš£πšŽ_πšπšžπš•πš•_πš£πšŽπš›πš˜_πšœπšπš›πšŽπšπšŒπš‘ constraint
ctrs/min_size_full_zero_stretch-6-tikz
Figure 5.258.3. Hypergraph of the reformulation corresponding to the automaton (with two counters) of the πš–πš’πš—_πšœπš’πš£πšŽ_πšπšžπš•πš•_πš£πšŽπš›πš˜_πšœπšπš›πšŽπšπšŒπš‘ constraint where l=|πš…π™°πšπ™Έπ™°π™±π™»π™΄πš‚| (since all states of the automaton are accepting there is no restriction on the last variable Q n )
ctrs/min_size_full_zero_stretch-7-tikz