My Math Forum  

Go Back   My Math Forum > College Math Forum > Linear Algebra

Linear Algebra Linear Algebra Math Forum


Reply
 
LinkBack Thread Tools Display Modes
April 26th, 2018, 03:34 PM   #1
Newbie
 
Joined: Apr 2018
From: Berkeley

Posts: 4
Thanks: 0

MILP formulation

Hi everybody,

I am currently working on a problem which implies to formulate a MILP problem, but I am a beginner in this field.
The point is, in my opinion, mainly that I don't know if this type of problem has a name, which could help me to find posts here or somewhere else :

I want to minimize the number of unique flow rates values m_i with i being the duct number (which is several hundreds), and the flow rate can be equal to any value.

In input (already calculated) I have powers produced by each assembly (to be evacuated by those fliw rates) : Q_i

I have several linear constraints which are linear, but one is not (I think) :
Capture d’écran 2018-04-26 à 16.32.52.png
with i' taking values of each adjacent duct of the duct i.

I want to minimize would be the number of distinct values of flow rates, or maximize the number of flow rates which are strictly equal. It is very important here to get this linear nature, in order to get THE optimal result.

So, without the non-linear constraint, has this problem a name? Is there a known method to formulate it?
How would you linearize the non-linear constraint?

Thank you!
yvrob is offline  
 
May 3rd, 2018, 08:35 AM   #2
Newbie
 
Joined: Apr 2018
From: Berkeley

Posts: 4
Thanks: 0

Hi, is this question in the right category ?
If yes, can anyone help me ? I spent the whole week trying to solve my problem and still no (realistic) clue.

Thanks
yvrob is offline  
May 3rd, 2018, 08:53 AM   #3
Senior Member
 
romsek's Avatar
 
Joined: Sep 2015
From: USA

Posts: 2,009
Thanks: 1042

Quote:
Originally Posted by yvrob View Post
Hi, is this question in the right category ?
If yes, can anyone help me ? I spent the whole week trying to solve my problem and still no (realistic) clue.

Thanks
Sometimes the regulars here just don't know the answer.

Did you try here?
romsek is offline  
May 6th, 2018, 04:25 PM   #4
Newbie
 
Joined: Apr 2018
From: Berkeley

Posts: 4
Thanks: 0

Thank you I will try !
yvrob is offline  
May 10th, 2018, 11:02 AM   #5
Senior Member
 
Joined: Mar 2015
From: New Jersey

Posts: 1,390
Thanks: 100

An LP problem consists of a linear function (the objective function) which you wish to maximize or minimize subject to linear constraints. For example:
Maximize Objective Function x+2y
Subject to Constraints: $\displaystyle 2x+3y \leq 6, x\geq 0, y \geq 0$.

If you add the condition that the variables are integers, it is an ILP problem (x & y are integers).
If only some of the variables are integers, it is an MILP problem (only x is an integer).

Your problem consists of two steps:
1) Clearly define the problem (write the objective function and constraints}
2) Look for a method of solution: utube is great for this.

You can replace |a-b| $\displaystyle \leq 4$ by two linear constraints:
https://ocw.mit.edu/courses/sloan-sc...3S13_tut04.pdf
$\displaystyle |a-b|\leq 4$
$\displaystyle -4 \leq a-b \leq 4$
$\displaystyle a-b \leq 4$
$\displaystyle -a+b \leq 4$

I would first formulate and solve a problem in 2 or 3 variables to get the lay of the land.

Last edited by skipjack; May 10th, 2018 at 12:05 PM.
zylo is offline  
May 13th, 2018, 09:15 AM   #6
Newbie
 
Joined: Apr 2018
From: Berkeley

Posts: 4
Thanks: 0

Thank you for your answer.

I tried something but I am not happy with that :

I discretized the flowrates in a vector w (let's say that its length is n_fl), then created binary variables d_i,j to show that the duct i (there are n_d ducts) is cooled by the flowrate j (so number of binary = n_d * n_fl).
Then I created n_fl other variables b_j which take the value 1 if at least one the ducts is cooled by the flowrate j.

My cost function is the sum of b_j (so the number of different flowrates chosen).

Two problems however :
- the number of binary variables is HUGE (if there are 500 ducts and 200 values of discretized flowrates, there are 10^5 binaries) with a lot of constraints, and even with an HPC I can get a results in a week or even more.

- the fact that I discretized the flowrates is so random : I am not able to say that it is the optimal solution if I didn't allow the flowrates to be continuous.

Have you got a clue on that ?
yvrob is offline  
Reply

  My Math Forum > College Math Forum > Linear Algebra

Tags
formulation, milp



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
mathematical formulation mosahab Calculus 0 November 1st, 2016 05:54 AM
Formulation of integral mghg13 Calculus 2 February 12th, 2013 12:28 PM
sphere equation formulation lalitp Algebra 1 December 12th, 2012 12:27 AM
Wilson theorem new formulation? momo Number Theory 1 April 11th, 2009 09:49 PM





Copyright © 2018 My Math Forum. All rights reserved.