hdavid16/disjunctiveprogramming.jl

A JuMP extension for Generalized Disjunctive Programming

disjunctiveprogramming.jl's Issues

Add sum of indicator binaries = 1

Clean up code and document

• Check comments
• Add docstrings
• Remove unnecessary args or kwargs
• Consider cleaning functions by using args... or kwargs...
• Use Documenter

Due to limitations in Symbolics.jl, does not support models with variables that are DenseAxisArray or SparseAxisArray

Equivalent symbolic containers do not exist in Symbolics.jl

interval arithmetic function fails with nonlinear functions

if nonlinear functions are used that contain a string that is the same one of the model variables, the Big-M reformulation fails.

For example: exp(x) gets converted to e[-1,1]p[-1,1] if x gets substituted with the interval [-1,1]

Big-M for nonlinear constraints

The following lines in the BMR function fail if there is a nonlinear constraint:

    add_to_function_constant(ref, -M)
    bin_var_ref = variable_by_name(ref.model, string(bin_var[i]))
    set_normalized_coefficient(ref, bin_var_ref , M)

What this is doing is adding the Big-M term to the constraint: i.e., M*(1-bin_var_ref).

However, for NL constraints, this needs to be treated as discussed in #7

support interval arithmetic for quadratic expressions

need an analytical expression to find the min/max of the quadratic

Code needs to be made more robust

Flexibility in constraint inputs:

• A disjunct could be a code block (begin...end)
• A disjunct could be a code block with some or all named constraints
• A disjunct could be a single constraint
• A disjunct could be a named constraint
• A disjunct could be an anonymous constraint
• the constraint expressions could be defined in the macro itself. Create a disjunction object to extend JuMP.

Constrain splitting:

• When a constraint set is bounded (i.e. 0<= x <= 1), it needs to be split into two constraints to allow implementing CHR and BMR

Checking variables in a constraint

I hope this helps. You shouldn't need to do the string parsing stuff

using JuMP

function _variable_list(
    list::Set{Int}, 
    nlp::MOI.Nonlinear.Model, 
    expr::MOI.Nonlinear.Expression,
)
    for node in expr.nodes
        if node.type == MOI.Nonlinear.NODE_MOI_VARIABLE
            push!(list, node.index)
        elseif node.type == MOI.Nonlinear.NODE_SUBEXPRESSION
            _variable_list(list, nlp, nlp.expressions[node.index].nodes)
        end
    end
    return
end

function variable_list(c::NonlinearConstraintRef)
    list = Set{Int}()
    nlp = nonlinear_model(c.model)
    constraint = nlp[index(c)]
    _variable_list(list, nlp, constraint.expression)
    return map(sort!(collect(list))) do i
        return VariableRef(c.model, MOI.VariableIndex(i))
    end
end

variable_list(c::ConstraintRef) = variable_list(constraint_object(c).func)

variable_list(c::AffExpr) = collect(keys(c.terms))

model = Model()
@variable(model, x)
@variable(model, y)
@variable(model, z)
c1 = @NLconstraint(model, sin(x) <= z)
c2 = @constraint(model, x + y <= 0)
variable_list(c1)
variable_list(c2)

Warn user if big M provided is too small

Copy extension objects to support copying model

https://jump.dev/JuMP.jl/stable/developers/extensions/#The-extension-dictionary

Upcoming refactoring of JuMP's nonlinear API

The upcoming release of JuMP v1.2 will break DisjunctiveProgramming.jl. Read more here: https://discourse.julialang.org/t/ann-upcoming-refactoring-of-jumps-nonlinear-api/83052

The problem is the use of internal functions and structs here:

DisjunctiveProgramming.jl/src/constraint.jl

Lines 145 to 151 in a51b0b9

	#replace original constraint with lb <= func
	lb_constr = JuMP._NonlinearConstraint(
	JuMP._NonlinearExprData(m, constr_func_expr),
	lb,
	Inf
	)
	m.nlp_data.nlconstr[constr.index.value] = lb_constr

Unfortunately, I don't know if we have a safe, publicly documented way of doing this.

x-ref: jump-dev/JuMP.jl#2955

Please ping me if you have questions.

Only disaggregate variables involved in disjunction constraints (Hull reformulation)

Currently, all variables are being disaggregated, which means that many variables are created unnecessarily, affecting performance.

Allow user to have already created the disjunction binary variable before calling the disjunction macro

Need to check that the dimension matches the number of disjuncts

Bug: Big-M Reformulation for `MOI.EqualTo` constraints

x + y = 1 needs to be replaced by 1 <= x + y <= 1 and then split into two separate constraints to allow proper Big-M implementation.

checking proposition expressions fails

this fails:

@proposition(ngdp, ¬(ngdp[Symbol("Y_$i")][1]) ⇒ ¬(ngdp[Symbol("N_$(i)_$t")][1]))
ERROR: AssertionError: Logical expression does not use valid Boolean symbols: ∨, ∧, ¬, ⇒, ⇔.

Leverage JuMP extension infrastructure

See https://discourse.julialang.org/t/error-handling-in-quote-block-using-jump/79362/10?u=hdavid16

Add tests

Quadratic constraints that are modeled using `@constraint`

Since quadratic constraints can be modeled using the standard constraint macro, these can be reformulated without the hack in #7.

These constraints are nonlinear so they need to be reformulated as such.

Use throw(ErrorName) Instead of error()

Calculate BigM parameter for nonlinear constraints

build and solve an NLP to get the maximum big-M value for the nonlinear constraint

TagBot trigger issue

This issue is used to trigger TagBot; feel free to unsubscribe.

If you haven't already, you should update your TagBot.yml to include issue comment triggers.
Please see this post on Discourse for instructions and more details.

If you'd like for me to do this for you, comment TagBot fix on this issue.
I'll open a PR within a few hours, please be patient!

Variable Lower Bound

If variables don't have a lower bound and Convex Hull Reformulation is selected, the program will error.
Instead of erroring, the program should assign 0 as the lower bound and give a warning about this.

Fix propositions in paper example

Bug in choose! function in example

Need to support multiple disjunctions

Binary variables can be modelled as a Matrix of binaries (2 indices: 1st index is the number of disjuncts, 2nd index is the number of disjunctions). A SparseAxisArray might be better suited for this since not all disjunctions have the same number of disjuncts.

Add support for propositional logic

Waiting for Symbolics.jl to support CNF: JuliaSymbolics/Symbolics.jl#59

Need to delete NLconstraint after reformulating its respective perspective function when using CHR

This will require rebuilding the model or waiting until delete of an NLconstraint is supported: see jump-dev/JuMP.jl#2355

Extend XOR operator for multiple arguments

Update code to access a Nonlinear constraint name when supported by JuMP

The following trick is done to get the names of nonlinear constraints (which requires accessing the object dictionary to find the constraint). This is done because name is not supported for Nonlinear constraints (jump-dev/JuMP.jl#3069)

DisjunctiveProgramming.jl/src/utils.jl

Lines 73 to 80 in dcab5d6

	function gen_constraint_name(constr::NonlinearConstraintRef)
	constr_name = findfirst(==(constr), constr.model[:original_object_dict])
	if isnothing(constr_name)
	constr_name = gensym("constraint")
	end
	return Symbol(constr_name)
	end

The object dictionary is currently stored so that any deletions of Nonlinear constraints do not break the object dictionary:

DisjunctiveProgramming.jl/src/reformulate.jl

Line 16 in dcab5d6

@expression(m, original_object_dict, object_dictionary(m))

Big-M Tightness

IntervalArithmetic won't necessarily give you the tightest Big-M value for nonlinear GDP.

Using nothing for an empty disjunction

Only works if using big M. Otherwise, the empty disjunct will set the values of all variables to 0 if chosen.

Improve performance of `distribute_and_over_or!`

Should be done from the bottom up on the expression tree for best performance. However, it is currently done from the top down, which is why we run it in a loop until all clauses are in CNF.

Reformulation method specific to constraint

It might be useful to allow the user to specify the type of reformulation for each constraint (add a field to DisjunctConstraint to specify method).

Error when adding disjunctions in a loop with EqualTo constraints

There might be an issue with nested indexed disjunctions that use EqualTo constraints. These are converted to SparseAxisArrays and then can't be found (see plant design_scheduling example)

Allow support for iterators in Boolean operators

Example:

∨(x[i] for i = 1:2)

which is equivalent to

x[1] ∨ x[2]

Nested operators should be supported

Use expressions for the constraints used in the disjunctions

https://jump.dev/JuMP.jl/stable/manual/expressions/

This is probably a better approach for the internals of this package. This way, constraints are not modified, but the expressions are reformulated and then added as constraints.

option to reformulate disjunctions with indicator variables

only supported on some solvers and constraints must be linear

indexed variables are not working properly in Symbolics manipulation

Issue occurs when eval(lhs) if lhs is an expression that contains an indexed variable

Allow reformulation when optimize! Is called

`check_logical_proposition` should be more robust

Don't rely on Suppressor.jl

`@disjunction` macro requires a name to be passed to the disjunction

When using a tuple to build a disjunction with @disjunction, a name must be provided or the transformation fails.

julia> fc1=Model()
A JuMP Model
Feasibility problem with:
Variables: 0
Model mode: AUTOMATIC
CachingOptimizer state: NO_OPTIMIZER      
Solver name: No optimizer attached.       

julia> @variables(fc1,begin
       0 ≤ z ≤ 6
       0 ≤ x ≤ 3
       end)
julia> @disjunction(fc1, z==x+3, (z≤0,x≤0), reformulation=:big_m, M = 100)

ERROR: UndefVarError: disj_##638 not defined
Stacktrace:
 [1] top-level scope
   @ C:\Users\HD\.julia\packages\DisjunctiveProgramming\fJZjn\src\macros.jl:71      

Interval arithmetic can't be applied to quadratic constraints to insert big M value

Update methods to avoid this

Add fixed cost parameter in disjunction

This requires reformulation of the objective function.

Allow nested disjunctions

Use nested tuples or tuples if no tuples are used in the top layer.

Look into Alternate CNF

Alternate approaches exist for converting to CNF, which involve preserving clause satisfiability rather than clause equivalence. These approaches prevent exponential size increase in clauses and yield logically consistent results.

Paul Jackson and Daniel Sheridan. Clause form conversions
for boolean circuits. Theory and Applications of Satisfiability
Testing, page 183–198, 2005. doi:10.1007/11527695_15.

infer bigM needs to support `@NLconstraint`

prelim code:

using JuMP

m=Model()
@variable(m,0<=x[i=1:2]<=1)
@variable(m,0<=y<=1)
@NLconstraint(m,e[i=1:2],exp(x[i]) + y >= 0)

e1 = string(e[1])
e1split = split(e1," ")
idx = findfirst(part -> occursin(r"[>=,<=,==]",part), e1split)
e1join = join(e1split[1:idx-1])

vars = all_variables(m)
varnames = [split(string(var),"[")[1] for var in vars]
union!(varnames)

new constraints output for nonlinear models

Since reformulations of nonlinear (or quadratic if using the hull reformulation) constraints requires deleting the original constraint and creating a new constraint, the section in reformulate_disjunction that creates the dictionary with new constraints errors because the disj has been modified.

DisjunctiveProgramming.jl/src/reformulate.jl

Lines 30 to 32 in a118804

	new_constraints = Dict{Symbol,Any}(
	Symbol(bin_var,"[$i]") => disj[i] for i in eachindex(disj)
	)

`infer_bigm` without parsing expressions or using IntervalArithmetic

Access the constraint object func and then use the func.terms mapping to apply interval arithmetic.

Perspective function

Epsilon should not be a JuMP variable. Make it a scalar and a keyword argument.

Are mixed-integer constraints allowed inside a disjunct?

This isn't standard, but is currently allowed in the CHR function

Implement more Reformulation Methods

https://www.sciencedirect.com/science/article/pii/S0098135415000587