Questions tagged [mixed-integer-programming]

For questions about mathematical optimization problems involving both continuous and binary or general integer variables.

Filter by
Sorted by
Tagged with
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 ...
Yunqi Li's user avatar
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. ...
Yunqi Li's user avatar
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 &...
madhafakha's user avatar
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 ...
Asheesh's user avatar
  • 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 ...
A.Omidi's user avatar
  • 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 ...
Eslam Mahmoud's user avatar
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 ...
ORProfessional's user avatar
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 ...
linkho's user avatar
  • 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 &...
sino's user avatar
  • 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 ...
Hemfri's user avatar
  • 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 ...
Rainbow's user avatar
  • 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} ...
Cris's user avatar
  • 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 ...
avilog's user avatar
  • 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 ...
Kuifje's user avatar
  • 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 ...
EduardoSalazarT's user avatar
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 ...
Mike's user avatar
  • 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 ...
Sirisha G's user avatar
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. @...
Kuifje's user avatar
  • 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 ...
Clement's user avatar
  • 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 ...
Optimization team's user avatar
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 =...
Optimization team's user avatar
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, ...
Nate's user avatar
  • 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?
Clement's user avatar
  • 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 ...
KGM's user avatar
  • 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 ...
A.Omidi's user avatar
  • 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 ...
KGM's user avatar
  • 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=\{...
Kuifje's user avatar
  • 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$. ...
graphtheory123's user avatar
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 ...
TroyE219's user avatar
  • 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; ${...
Abde's user avatar
  • 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
Mansour's user avatar
  • 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 ...
Rainbow's user avatar
  • 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$ ...
A.Omidi's user avatar
  • 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 ...
Red shoes's user avatar
  • 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 ...
Matheus Diógenes Andrade's user avatar
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.
Clement's user avatar
  • 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 ...
Roegel's user avatar
  • 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 ...
StringTypeGroup's user avatar
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 ...
Dano's user avatar
  • 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 ...
Abde's user avatar
  • 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} ...
Ahmed's user avatar
  • 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 ...
linkho's user avatar
  • 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?
Waldo's user avatar
  • 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 ...
Yiichan Sun's user avatar
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 ...
John D's user avatar
  • 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 ...
Pia MiA's user avatar
  • 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 ...
John D's user avatar
  • 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 ...
A.Omidi's user avatar
  • 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 ...
lalsriv's user avatar
  • 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 ...
liam shan's user avatar

1
2 3 4 5
17