Getting started: MIP variables and datastructure

Hi all,

In short; I’m trying to find if and how I can formulate a MIP on a datastructure.
I have a set of orders ( with handling time, start location, end location and each location a timewindow )
And I want to combine orders these orders into tours (with some constraints)

I’d like to create a datastructure in which I can say that I have a tour, with a sorted relation to tour-actions (there is a fixed number of tour actions associated with a tour). When I assign an order to a tour, I have to assign it’s pick-up action to a tour-action and its delivery action to a tour-action of the same tour.

Ideally in the MIP contraint I’m able to say things like
(I’m well aware the syntaxt isn’t correct and that the constraints aren’t meaningfull in real life. But I hope you get what I’d like to achieve anyway):

 @variable(model, AssignOrderTour, { o in Order, t in Tour}  )
 @variable(model, AssignOrderActionTourAction, { oa in OrderAction, ta in TourAction}  )
 
 // I'd like to access the pick-up action and delivery action from order in a constraint
 // I'd like to be able to get all tour-actions of a tour
 @constraint(model, Some_test, { o in Order, t in Tour},  AssignOrderTour(o,t) >= sum( ta in t  ) AssignOrderActionTourAction(  o.PickupAction, touraction ) )
 
 // I'd like to be able to access the previous tour action in a constraints 
 @constraint(model, Some_test2, { o in Order, ta in TourAction},  AssignOrderActionTourAction(  o.PickupAction, ta ) <= AssignOrderActionTourAction(  o.DeliveryAction, ta.Previous )  )

Is it possible to built something like this in Julia + JuMP?
If so, could anyone lead me to an example on how to do this? Or point me in the right direction?

There are lots of examples in the JUMP documentation:
https://jump.dev/JuMP.jl/stable/tutorials/Mixed-integer%20linear%20programs/cannery/
There is no limit from the JuMP side on what data structures you can use. (Since JuMP is a package in Julia, you are free to use any Julia objects in a JuMP model. This is unlike something like AMPL where you are restricted to things built into AMPL.)

Your syntax is pretty close. Maybe something like:

@variable(model, AssignOrderTour[o in Order, t in Tour])
@constraint(model, Some_test[o in Order, t in Tour],  AssignOrderTour(o,t) >= sum(AssignOrderActionTourAction[o.PickupAction, ta] for ta in t))

People may be able to provide more advice if you provide a minimal working example with actual Julia code for the structs and definitions of Order and Tour, etc.

1 Like

Yes, I’ve seen the examples in the JUMP documentation, but they’re rather basic.
In your example Plants and Capacity are two separate vectors/arrays. And you just have to hope that Plant[1] matches Capacity[1].
The example would have been more interesting if they built a struct Plant with certain capacity.

The reason I ask whether it is possible at all, is that if I create such a struct; I wonder if Julia/JuMP is checking whether types match. It needs to recognize that (in my example) the variable is defined on a StoreAction and that Order.PickUpAction is indeed such a store action.
Or is Julia/JuMP not checking anything like that and just assumes you know best?

I’m also struggling to get the datastructure in Julia, but that’s due to a lack of experience. Anyway goal of today is to dive into that.

A more complicated version of the cannery problem might be:

using JuMP, GLPK

struct Plant
    name::String
    "Capacity of the plant in units"
    capacity::Float64
    "Location of the plant along the real number line"
    location::Float64
end

struct Market
    name::String
    "Capacity of the plant in units"
    demand::Float64
    "Location of the market along the real number line"
    location::Float64
end

function example_cannery()
    plants = [Plant("Seattle", 350.0, 0.0), Plant("San-Diego", 600.0, 1.0)]
    markets = [
        Market("New-York", 300.0, 0.5),
        Market("Chicago", 300.0, 0.3),
        Market("Topeka", 300.0, 0.6),
    ]
    """
    The cost of shipping 1 unit from `p` to `m`.
    """
    cost(p::Plant, m::Market) = 90 * (p.location - m.location)^2
    model = Model(GLPK.Optimizer)
    @variable(model, ship[plants, markets] >= 0)
    @constraint(model, [p in plants], sum(ship[p, :]) <= p.capacity)
    @constraint(model, [m in markets], sum(ship[:, m]) >= m.demand)
    @objective(model, Min,
        sum(cost(p, m) * ship[p, m] for p in plants, m in markets),
    )
    optimize!(model)
    println("RESULTS:")
    for p in plants, m in markets
        println("  $(p.name) $(m.name) = ", value(ship[p, m]))
    end
    return
end

example_cannery()

We do need to apply some editorial judgement to the examples to make them a bit more diverse and reflective of the types of things you can do in Julia!

1 Like

Yes, it would be great if the examples would be more diverse!

A related question, since I am using structs (like in your exmple), the variable names in the .lp file have become horribly long. By default it prints all atrributes of the struct.
Is there a way to make Julia/JuMP only print some id that I defined?

More concrete:
you have

    model = Model(GLPK.Optimizer)
    @variable(model, ship[plants, markets] >= 0)

which in lp would give

Bounds
ship( Plant("Seattle", 350.0, 0.0), Market("New-York", 300.0, 0.5) )  free
ship( Plant("Seattle", 350.0, 0.0), Market("Chicago", 300.0, 0.3) )  free
etc.

whereas ideally I would like to see (assuming cities are unique identifiers here)

Bounds
ship( Plant("Seattle"), Market("New-York") )  free
ship( Plant("Seattle"), Market("Chicago") )  free
etc.

The reason I want this; debug-ability; the lp file is impossible to read and I want to be able to read the CPLEX conflict refiner output.

( it doesn’t help that it cuts-off the variable names after certain length ).

Apologies if you know this already, you can interrogate the conflict refiner directly through JuMP; a starting point is the documentation on Conflicts here Solutions · JuMP

1 Like

Use set_name

for p in plants, m in markets
    set_name(ship[p, m], "ship_$(p.name)_$(m.name)")
end

It would make sense if we added a name keyword to JuMP, so you could go

@variable(model, ship[p=plants, m=markets], name="$(p.name)_$(m.name)")

(Yes, there is base_name, but that changes ship, not the indexing.)

Edit: Add `name` keyword to macros · Issue #2643 · jump-dev/JuMP.jl · GitHub

No problem; indeed I did know. For reasons irrelevant to explain I can’t access CPLEX in Julia, but only use it stand-alone.
So I use Julia with GLPK to get met started, then (in parallel) run and conflict refine in CPLEX for performance tests.

Thank you, that would help!
Indeed I found base_name which was not helpful.

It would be really nice if this name-keyword would become part of JuMP

1 Like

Please post the issues you have with CPLEX. We can only fix problems we know about :slight_smile:

ow, no sorry. The problem is on the software infrastructure/license side of things. Nothing Julia can fix. :wink:

1 Like

For future readers wondering about good variable names; if you work with Dictionaries, you could use the key-values for variable names.

i.e.

orders = Dict{String, Order}()
...
@variable(model, AssignOrders[ order in keys( orders ) ], Bin )
1 Like