Questions tagged [mixed-integer-programming]
For questions about mathematical optimization problems involving both continuous and binary or general integer variables.
814
questions
0
votes
0
answers
35
views
How to linearize such a constraint?
My original content was like this:
Assuming that server $k$ can only allocate corresponding computing functions to MU $i$ after receiving their tasks. Let
$$ y_{i,k,t} = \begin{cases} 1 & \text{if ...
- 1
0
votes
1
answer
30
views
How to linearize the waiting time
My question is this:
I want to express the time it takes for multiple servers to complete tasks for multiple users. I divide the time into $t$ time slots, and each task may occupy multiple time slots. ...
- 1
1
vote
1
answer
28
views
$\min\{f(x_1),\dots,f(x_n)\}$ with other constraints
I have an optimization problem which goes:
\begin{align*}
\text{Minimize:}
\\
& \sqrt{x} + \sqrt{y} \tag{NL-objective}
\\
\text{Subject to:}
\\
&3x + 2y \geq 2 &...
- 11
2
votes
1
answer
90
views
Find the minimum number of equipment required for a service period
I'm starting to learn operations research and trying to get my head around this problem that I have.
Problem statement: Find the minimum number of equipment needed to run a service schedule.
There are ...
- 21
1
vote
2
answers
94
views
Quality of the defined initial solution in column generation
In the context of column generation, specifically, price and branch or delayed column generation like Gilmore-Gomory (GG-CG) procedure, it needs to define an initial feasible solution as a trigger of ...
- 7,549
0
votes
1
answer
74
views
Mixed Integer Programming - How to model a term in objective function with a constant multiplied by (1-Decision Variable)
I am solving an optimization problem, where I want to minimize the objective function
$$Z = \sum_q \left(D_q \text{fare}_q - \sum_{p \ne q} \Delta D^p_q \text{fare}_q \right) (1-Z_q)$$
Each $q$ is an ...
1
vote
1
answer
59
views
Workforce scheduling MIP formulation
I am working on a large scale workforce scheduling problem with a large number of hard and soft constraints. The soft constraints are modeled as objectives with penalties for violating them. So my ...
5
votes
4
answers
829
views
Rewriting if-then constraints of binary summations
Suppose both $x_{i,j}^{ab}$ and $y_{i,j}^a$ are binaries. Then how can I rewrite the following if-then in linear form?
$\sum_b x_{i,j}^{ab} \ge 1 \implies \sum_{i,j} y_{i,j}^a = 0$
I was thinking of ...
- 163
0
votes
3
answers
120
views
Using PULP to model machines in a factory
Complete revision:
I have all 4 machines that can run in positive and negative directions which results in 2 outputs:
$ P_1 = \begin{cases}
-390 \le P_1 \le -300 & \text{for neg mode}\\
0 &...
- 1
1
vote
2
answers
146
views
how to satisfy time constraints with meeting points?
I have a specific pickup and delivery problem to work on and am thinking how to incorporate time windows effectively. The problem has some driver with some time window [$a_d, b_d$] which is the start ...
- 11
2
votes
2
answers
206
views
Model Complexity and Constraints in Mathematical Modeling
I have a few questions about mathematical modeling (MILPs mainly). My understanding is that the complexity of a model is primarily determined by the number of decision variables, rather than the ...
- 41
1
vote
1
answer
100
views
Rational LP, its Rational solution and a minimum precision
Suppose we have an LP with rational coefficients.
To my knowledge, this implies that the optimal solution to that LP is also rational. In other words, every variable may be written as:
$$x_{i}^{\star} ...
- 143
2
votes
3
answers
105
views
Is there a name for this variation of the generalized assignment problem?
All the input variables are positive float (x > 0). We have $M$ agents with limited amount of time $t_1,\dots,t_M$, $N$ tasks $task_1,\dots,task_N$ associated with duration $d_1,\dots, d_N$. Cost ...
- 21
6
votes
0
answers
89
views
MIP formulation for graph planarity test
In this question, it was asked wether a MIP formulation exists to test for a graph's planarity. The inputs are the graph's nodes and edges, and the output would be a certificate which guarantees that ...
- 12.3k
4
votes
1
answer
200
views
MIP Model with relaxed integer constraints takes longer to solve than normal model, why?
I am currently working on my undergrad thesis which is a mathematical optimization problem of the territory design family of problems. I am using the mathematical formulation of the problem to solve ...
1
vote
1
answer
49
views
Assistance in formulating implication constraints for inequalities
I would like to seek some advice on modeling the following logical implications, where $\delta$ is a binary variable, $D_{j}$ and $A_{j}$ are nonnegative discrete variables, and $p_{j}$ are ...
- 707
1
vote
0
answers
43
views
Plant Network model
I am looking for some help in Plant Network Optimization- as an example scenario would be to optimize the Plant network based on the below inputs and figure out best possible plants to use to service ...
- 11
1
vote
1
answer
73
views
Traffic lights optimization (part 2)
This is a follow up question of this thread, in which it is asked how to model a circular layout of a given set of cliques of a graph, which represent simultaneous movements at an intersection.
@...
- 12.3k
3
votes
2
answers
77
views
Knapsack Constraint
Is the following expression a knapsack constraint?
$ \sum_i a(i) y(i) \ge W$, where $y(i)$ binaries, $a(i),W$ reals.
What confuses me is the $\ge$ sign.
Alternatively, do solvers generate cuts out of ...
- 2,132
0
votes
1
answer
84
views
How to identify which node is serving each customer?
I have a linear programming problem. There are two questions:
Consider 2 centers (1,2) that should serve clients [s,b,c,t], What it the minimum distance cost. The formulation is straight forward.
The ...
- 1,120
4
votes
3
answers
480
views
How can I formulate this 'if-then' constraint problem?
I have five integer variables, and I need to write some constraints on them:
$x_0$ , $[x_1, x_2, x_3, x_4 ]$. $1 \leq x_i \leq 3$
if $x_0 =1$ then no constraint on $[x_1, x_2, x_3, x_4 ]$
if $x_0 =...
- 1,120
1
vote
2
answers
107
views
Minimal infeasible constraint set
Many modern SAT and SMT solvers offer a feature where they can report why a problem is unsatisfiable, something called an "unsat core."
Are there any optimization solvers (in my case, ...
- 113
2
votes
0
answers
51
views
Big M Modelling [duplicate]
It is advised that in a big M constraint, M should be chosen as small as possible.
Is this recommendation a hard fact or heuristics?
- 2,132
1
vote
4
answers
65
views
Coloring of nodes of a sensor network
It is the same problem as posted at Coloring of nodes in a sensor networks.
Its about coloring a weighted graph.
@RobPratt suggested a very good solution that solves the problem directly.
However, we ...
- 2,191
2
votes
1
answer
38
views
A tighter relaxation of the mix logical constraints
Suppose the following logical form there exists.
$$Iff: (x_{j,m} \land x_{k,m}) \implies ((C_{j} \leq S_{k}) \lor (C_{k} \leq S_{j}))$$
This is well-known as a no_overlap_constraint in the parallel ...
- 7,549
0
votes
1
answer
66
views
Coloring of nodes in a sensor networks
I have weighted graph for sensor networks with aggregation nodes and sensors. There is a edge between two nodes associated with a weight.
Higher the weight, stronger the interference between the ...
- 2,191
7
votes
2
answers
307
views
Traffic lights optimization
I am interested in the following problem dealing with the optimization of traffic lights on the intersection illustrated below:
The goal is maximize the duration during which each movement $m\in M=\{...
- 12.3k
0
votes
1
answer
61
views
How to formulate an MIP so that a binary variable is 0 or 1 depending on whether another variable is nonzero?
I have a binary indicator variable $i \in \{ 0, 1 \}$ and an integer variable $c \in \mathbb{Z}$.
I am trying to come up with a formulation in which $i = 0$ if $c = 0$ and $i = 1$ if $c \neq 0$.
...
- 143
2
votes
2
answers
78
views
Small negative decision variable returned in Gurobipy model
I have a multi-period model in gurobipy with 7 types continuous decision variables and 1 type of binary (Thousands indexed total). The model solves properly and the solution has passed many validation ...
- 105
1
vote
0
answers
31
views
Auxiliary parameters for two uncertain parameters Robust Optimization
I have the following constraint for robust counterpart formulation, where two uncertain parameters appear at the same time;
$\sum{QG_{ij}}$*${\theta}$+$\sum_{}\sum{QD_{ij}}*p $ * ${\theta}$
where;
${...
- 81
1
vote
0
answers
30
views
Which Python package is suitable for finding the optimal non dominated set in multiobjective optimization?
I would like to know how to use pyhon or Cplex or both for finding the whole optimal pareto front for a biobjective mixed integer linear programming problem?
Thanks
- 11
1
vote
2
answers
56
views
Is it possible to route based only upon shortest path?
I have a routing problem and am wondering if it is even possible to only use the $k^{th}$ shortest path?
There are a set of people with cars and a set of other people with no cars, each has its own ...
- 41
2
votes
1
answer
94
views
Using networkx predecessors in Pyomo initialize method
I am working on the directed graph by using the Networkx package and what I need is to use its predecessors' method on an optimization model. Let's say, there exists a directed graph with just $12$ ...
- 7,549
3
votes
2
answers
635
views
Writing a constraint of an integer programming in a linear form
I modeled an optimization problem in an integer programming format. The main constraint I came up with is now nonconvex. I would like to see if there is another equivalent formulation in which the ...
- 133
2
votes
1
answer
74
views
Structuring an MINLP solver
Folks, I am working on a project in which I have to code some C++ algorithms for smooth MINLPs.
Such algorithms are Extended Cutting Plane, Extended Supporting Hyperplane, and Outer Approximation. I ...
- 1,059
3
votes
2
answers
326
views
How to model C1 = C2 implies b1 = b2
Suppose $C_1 \ge 0$, $C_2 \ge 0$ are continuous variables and $b_1$, $b_2$ are binary variables.
How could I model the following?
$C_1 = C_2 \implies b_1 = b_2$, the opposite does not hold.
- 2,132
0
votes
0
answers
62
views
Resource selection problem with non-linear objective function
I have an optimisation problem to solve but I can't model it correctly. Any insight is welcome :)
It has been a few years since my optimisation classes in university, and while I have forgotten a lot ...
- 1
0
votes
3
answers
46
views
Maintaining Pair Preference that is neutral at outset
I am trying to model a job-shop scenario where - given a certain number of workers (W) and parts (P) such that P>W - each worker spends each shift (k) working on a specific part. Due to reasons of ...
3
votes
3
answers
189
views
Quantifying a measure of standard deviation in MILP
I am trying to set up a MILP for production scheduling. The specific details I'm not sure are important but in general a plant has M machines running N parts, each part requiring W workers. The model ...
- 33
1
vote
4
answers
155
views
Multi-period Inventory Balance in Gurobipy
I would like to get the inventory balance in the oponed facility $\text{C}$ such that, the Inventory at time $t$ is equal to the previous one, plus the inflow minus the outflow. I have tried to create ...
- 81
2
votes
3
answers
119
views
Linearization the product of three variables (two binary & one continuous)
Consider the following binary variable $x \in \{0,1\}$ and two continuous real variables $y,p \in \mathbb{R}$.
I am trying to model the following conditional equations as constraints:
\begin{cases}
...
- 103
1
vote
1
answer
64
views
how to minimize the distance to the final points with incomplete information?
Suppose we have a transportation problem similar to pickup and delivery problems. So, we have a set of drivers and a set of passengers. each passenger has predefined origins and destinations. I'd ...
- 163
1
vote
1
answer
118
views
Linearize conditional constraint
Consider a variable c from the domain {-1,0,1}. I have the following constraint:
IF $c = 1 \Rightarrow x = 1 $ ELSE $x = 0$
How do I linearize this constraint?
- 21
2
votes
3
answers
139
views
Is there any "not bad" algorithm that can solve the minimax problem in 0/1 integer programming?
As title, recently I got a minimax problem, after formalizing, the model is like this.
$$\text{minimise } \max_{k \in K} \sum_{i \in I} b_{i,k} \cdot f_i$$
such that: $$ \forall i \in I,\, \sum_{k \in ...
- 23
1
vote
2
answers
61
views
How to tackle online scheduling problems?
In scheduling problems, one usually has different options as objective functions (makespan, tardiness, etc). However, for any such type of scheduling problem one can consider an online version of it ...
- 199
1
vote
2
answers
63
views
Fixing binary variables in an Binary Integer Program
I have a Binary Integer Program with two binary decision variables and additionally have an expected solution. At the time of execution of this program I expect the parameters to change slightly. I am ...
- 392
1
vote
1
answer
80
views
Solver for Flexible Job Shop Scheduling Problem
I have a FJSSP that I would like to solve. However, the jobs in this problem have deadlines and in addition there are setup times between two jobs. Because of this, my objective function is not just ...
- 199
2
votes
0
answers
54
views
The linearization of the logical constraints
I know the logical constraints can be linearized by either the logical representation of whose relation, (for pure binary variables e.g. CNF/DNF) or for general form by using Big-M formulation. As I ...
- 7,549
2
votes
3
answers
431
views
Any Idea why PuLP is ignoring binary variables?
When I solve the following code, the binaries for the lines_selection variable is not respected by PuLP. Can anyone please point me out to the reason why this could ...
- 21
1
vote
0
answers
53
views
bi-objective mixed integer linear programming (MILP) problem
I have a bi-objective mixed integer linear programming (MILP) problem, which contains two specially sub-objective functions. The first linear objective function, only contains integer variables, while ...
- 11