constraintsschedulingnonlinear-optimization# Formulating an optimization problem with non linear constraints

I am trying to solve a dynamic machine scheduling problem using what I think qualifies as a non linear programming constraints.

I have academic knowledge of linear programming techniques and appreciate the opportunity to try my hands at non linear programming.

However, before anything I am struggling to write down a well forumulated problem. Here is the situation:

- I have a list of tasks of various natures that are ordered by "degree of emergency"
- Several machines, that specialize in various tasks, work on those tasks based on the "degree of emergency" and their specialty
- Tasks are not preemptive (start one, finish it, no interruption)
- Completion time is statistically known based on the nature of the task and the machine assigned to it.
- All machines should be used with minimal downtime
- Workload is balanced: machines work on roughly the same number of tasks and work for the same amount of time total

Can you please help me properly formulate the problem? Here is how I started putting it:

- m in M set of machines
- S number of specialties
- t in T set of tasks
- time to complete task t by machine m
- penalty coefficient for task t for being started with a delay past acceptable time
- X_mt 1 if task t is assigned to machine m 0 otherwise

**objective function:**
Find optimal X_mt such that task are started on time (limit penalty)

**constraints:**

- work duration is balanced through the machines (epsilon being a parameter):

- number of work item is balanced through the machines (epsilon being a parameter):

- machine selects task for which it specializes (dotproduct m specialty/t characteristics )

- minimize makespan

- only assign 1 task per machine

I am also looking for an algorithm to find some epsilon-optimal solution based on how I relax the workload balancing parameter.

But before I can try to look for an algorithm, I need help to properly formulate the problem.

I've seen example where variance constraints are formulated as the minimization of the difference of upper and lower boundaries but I don't know how to apply it in this case since I have multiple variance constraints.

If this is too much, how would you translate this problem into a Reinforcement Learning one?

Solution

Let's look at one of the variance constraints:

is wrong IMHO. There should be no "for all m".

I rewrite this as:

```
v[m] = sum(t,d[m,t]) for all m
variance(v) <= eps (this is a single, scalar constraint)
<==>
v[m] = sum(t,d[m,t]) for all m
minv <= v[m] for all m
maxv >= v[m] for all m
maxv - minv <= eps (different eps. now to limit the bandwidth)
```

- Similar for the other variance constraint
- I don't see a good reason to add things to the objective.
- This is completely linear

- validation on email / postcode fields in sql/oracle
- How to truncate a foreign key constrained table?
- How to create a "unique" constraint on a boolean MySQL column?
- How to constrain a neural network model's output in Rapidminer to non-negative values?
- How to change penalized cover constraint from excess only to target in OR Tools?
- Rules of Unbounded type parameters in Generics ( C# )
- ALTERing a CHECK constraint in a DOMAIN
- What is "strictly control signal" and Why is its input unconstrained?
- How to fix the foreign key references form an incorrect parent record to another record when both already exist? (PostgreSQL 14)
- Creating a constraint in a project selection problem
- Constraint name for default value for sql server with alembic
- SQL DROP TABLE foreign key constraint
- Constraint defined DEFERRABLE INITIALLY IMMEDIATE is still DEFERRED?
- How do I define the constraints of a multiple assignment problem with Pulp?
- MySQL Removing Some Foreign keys
- deferred constraint checking
- How to check if a PersistenProperty is a constrained property in groovy?
- Applying PRIMARY KEY constraint in CockroachDB - multiple primary keys error
- C# notnull constraint with nullable types have unexpected behavior
- How to list all constraints of a table in PostgreSQL?
- Can you add a constraint to an SQL column that checks the value of an enum?
- Adding constraints programmatically makes crash
- Why do I get SQL state:23503 when I try to add a constraint to an existing table in Postgres?
- Combining constraints?
- Xcode 6.4 - Unable to set constraints on Views or ... anything
- OR constraints in CP-SAT
- Define constraints with or-tools for a carpooling problem
- In Rust, is there a way to attach a "validity check" to a returned mutable reference?
- How to use CP-SAT solver or other tools to find 3D arrays with constraints on rows, columns and tubes (representing school classes, terms and days)?
- Is there any difference between inline and out of line constraints