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
1 vote
2 answers
88 views

In a routing and scheduling problem with break consideration, How can I determine whether a node is met before a break or after it?

I'm working on a routing and scheduling problem in the home care services context. I consider a break as a dummy patient, so routing and scheduling are also implemented for the break node (with some ...
Hani Jamshidian's user avatar
3 votes
1 answer
450 views

How to reduce an LP problem already in its standard form?

Suppose we have a feasible LP problem in its standard form. From Ax=b we can directly determine some of its variables and thus we can reduce the problem. For example, from two constraints: x+y+z=2 and ...
andy's user avatar
  • 67
0 votes
1 answer
46 views

Order fulfilment with constraints on factory production capacity and truckload

I have about 300 orders, where each order consists of different products that comes from a city (in total I have about 30 cities and around 100 products from all orders). My job is to allocate the ...
TTY's user avatar
  • 223
1 vote
0 answers
112 views

Why the column generation algorithm remains stuck at the same solution?

I was trying to solve a MILP by a column generation algorithm, and I noticed that the algorithm was stuck at the same solution, I tried to diversify the pool of initial columns, but the problem I ...
Nada.S's user avatar
  • 409
1 vote
2 answers
147 views

Help with Mathematical Formulation for VRP with Specific Constraints

I am currently working on a Vehicle Routing Problem (VRP) with a set of specific constraints. I have a total of 19 nodes, each representing a customer location, and a depot. There are also 7 pickers ...
Ilyass's user avatar
  • 19
2 votes
2 answers
77 views

In Benders Decomposition, do you add an optimality cut together with a feasibility cut?

in the process of implementing my first BD algorithm, I am unsure how to proceed in the case that the subproblem is unbounded. Obviously, it means you get an extreme ray that you can add to the RMP as ...
Arctic_Skill's user avatar
1 vote
0 answers
41 views

The rule of the slack variable in an indicator constraint

In some cases I have seen, the indicator constraint can be written as indcons(expression, binary_var). Then it is interpreted as follows: $$LHS - slack (\leq = \geq)...
A.Omidi's user avatar
  • 8,642
2 votes
3 answers
829 views

Modeling: How to force customers visit their NEAREST facility

Let set $I$ denote the facility location set, $N$ denote the customer set, and $d_{ni}, \forall n\in N, i \in I $ is the distance between customer $n$ and facility $i$. The problem is to locate ...
Runfeng Yu's user avatar
2 votes
1 answer
211 views

Compute overlapping time

I am trying to solve an optimization problem in which there is a set of tasks, $S$, where $s_i$ and $e_i$ are the starting and ending time of task $i \in S$. Each task $i $ must be done within its ...
Christopher Expósito Izquierdo's user avatar
2 votes
1 answer
103 views

Container Loading Problem

I'd like to optimize the loading problem in first-mile delivery that maximize the occupancy of the truck. The main question to be answered is this: with the given truck, would this list of items fit ...
overboxed's user avatar
  • 593
0 votes
1 answer
66 views

Finding lower bound (maximization problem) in Lagrangian Relaxation with subgradient method

I have tried to implement a toy problem (MIP) from the literature using Lagrangian Relaxation with the subgradient method, I implemented it correctly and I got the upper bound which is updated at each ...
ABDE's user avatar
  • 1
5 votes
1 answer
121 views

Numerically stable way to optimize a lexicographical preference between two objective functions?

I am solving a mixed-integer program whose decision variables are $x \in \{0, 1\}^n$ and $y \in \mathbb{R}^m$, where $0 \leq y_j \leq u_j$ for constant upper bounds. My primary objective function is ...
Max's user avatar
  • 534
1 vote
1 answer
38 views

SET game: how to generate decks of 12 cards with 6 hidden sets?

This question was initially the second part of another question and justifies a new post. The context is a game called Set: In the game, certain combinations of three cards are said to make up a &...
Kuifje's user avatar
  • 13.2k
2 votes
4 answers
131 views

How to fill the days in sequence?

I have a scheduling problem. 20 hours of work load should be assigned to different days (max 4 days are available and the capacity of ech day is 8 hours max) $\sum_i h_i = 20$ $0 \leq h_i \leq 8$ The ...
Optimization team's user avatar
2 votes
1 answer
150 views

SET game: how to generate all sets with a MIP?

I am playing around with the game called Set: In the game, certain combinations of three cards are said to make up a "set". For each one of the four categories of features — color, number, ...
SetPlayer's user avatar
0 votes
0 answers
32 views

Joint, two-sided chance constraint of MILP reformulation of a logical constrain

I reformulated the logical constraint $x = \min\{y,z\}$ as this MILP problem $$ \begin{array}{ll} x &\leq y \\ x &\leq z \\ x &\geq y-M(1-w) \\ x &\geq z-Mw \end{array} $$ in which $...
al b's user avatar
  • 1
0 votes
0 answers
76 views

Optimize revenue function with log part

I am working on an optimization problem where I aim to maximize revenue. My current model has the following objective function: $$ Sales(P_i) * log(P_i - const_i))$$ where $P_i$ represents the price ...
MarcM's user avatar
  • 173
1 vote
2 answers
114 views

Persisting Subproblem Infeasibility Benders Decomposition

I'm currently working on an optimization problem where I'm using Benders decomposition to solve a complex problem involving the installation of charging stations. The master problem determines the ...
bcoulier's user avatar
2 votes
1 answer
98 views

Representing a Multi-Level Categorical Variable using Big-M Method in Linear programming

I'm working with a statistical linear model where I have a variable, ( N ), representing the percentage of charging of a battery. Based on ( N ), I derive another variable, ...
MarcM's user avatar
  • 173
2 votes
1 answer
69 views

How do you derive the Benders feasibility cuts?

starting off with a MIP that I want to solve using Benders. so in Benders Decomposition, you add feasibility cuts in the following form: $v^j (b - Ax) \geq 0$ with $j \in J$ being the set of extreme ...
Arctic_Skill's user avatar
2 votes
1 answer
88 views

Can a logical expression be added to the objective function of a model in docplex?

I'm working on an optimization problem using Docplex and wonder if it's possible to incorporate a logical expression into the objective function of my model. Specifically, I have three variables x, y, ...
Nada.S's user avatar
  • 409
1 vote
3 answers
95 views

Breaking symmetry

Suppose resources r1 and r2 are both able to perform jobs j1 and j2. The duration of the jobs being done is d. I would like to model the following rule: Within a time horizon H, perform j1 on r2 only ...
Clement's user avatar
  • 2,224
-1 votes
1 answer
67 views

How to linearize the multiplication of variables and transform this into an MILP?

Let $C=10$, $U=50$ $P_c,c=1,\cdots,C$ and $\alpha_{u,c},u=1,\cdots,U,c=1,\cdots,C$ are optimization variables $\alpha_{u,c}$ is binary $\sigma_{u,c}$, $d_{u,c}$ are known parameters $\min \sum_{c=1}^...
KGM's user avatar
  • 2,211
7 votes
3 answers
738 views

Binary logical constraint dependent on indices

I don't know if I can ask this here, but I've been pulling my hair out trying to think of how to represent this in constraints. I have two sets of binary variables: $X_t$ and $Y_{it}$. So, I want to ...
orpanter's user avatar
  • 517
4 votes
1 answer
70 views

Can dual values smoothing lead to generating duplicate columns?

When using smoothing for dual values stabilization in column generation, the duals used in the subproblem lie on the segment joining the stability center (inside the dual feasible region) and the ...
Инженер человеческих душ's user avatar
6 votes
2 answers
816 views

How can I find the shortest path visiting all nodes in a connected graph as MILP?

I am looking for an idea on how to formulate the following problem as a MILP. Given a connected graph, find the shortest path route starting from a node (not given) and visit all other nodes. All ...
Optimization team's user avatar
4 votes
2 answers
68 views

Late and Early Costs per minute for a delivery problem

I'm currently struggling with a MIP. Have to model a truck delivering packages for customers in the set $C = \{1,2,3,4,5\}$. The travel time from location $i$ to $j$ I've defined as $t_{ij}$. The ...
Todd's user avatar
  • 41
3 votes
1 answer
214 views

Graph coloring problem redundant constraints

Say the edges of a 4 nodes graph are 0 1, 1 2 and 1 3. The solution to the colouring problem ...
Dr.PB's user avatar
  • 133
3 votes
2 answers
124 views

Coefficient Scaling for MIP

I have a coefficient matrix for an MIP with a less than ideal range of magnitudes. For example, consider this constraint: $$\sum_{ij} {\rm cost}_{ij} \cdot x_{ij} \leq \rm Budget$$ $$x_{ij} \in \{0, 1\...
gomory-chvatal's user avatar
4 votes
1 answer
173 views

Non-Linear objective function due to piecewise component

I have the following objective function: $\sum_{n}(1-prob_{n})(1+x_n)$ Where $x$ is my decision variable. $prob_{n}$ is a piecewise function that can look like: $prob_{n} = $ \begin{cases} 0.5, ...
akkha's user avatar
  • 67
1 vote
0 answers
38 views

Why did the CONSENFOLP callback assertion fail when the problem has a primal feasible solution?

I am working on the problem that I am willing to use SCIP's conshdlr callback to check how the constraints might be added to the model. I am using the following ...
A.Omidi's user avatar
  • 8,642
1 vote
1 answer
118 views

Constraints to avoid disjointed solutions in a MIP

Given an directed graph $G= (N,E)$, where $N$ is the set of nodes and $E$ is the set of all edges, each associated with a direction. $G$ is a connected graph but not necessarily a complete graph. A ...
CHE's user avatar
  • 113
1 vote
1 answer
89 views

MILP - Find out model size

Ucame across a paper today and this paper mentioned that the model size is $O(\mid I\mid\cdot\mid T \mid)$. I am also sitting on a MILP problem right now. Does my model size also amount to this size ...
Karl Seidl's user avatar
0 votes
1 answer
113 views

Team Orienteering Problem with Time Windows infeasible using CP-SAT solver in Google OR-Tool

I am developing a TOPTW where there are a set of N nodes. Each node i is associated with a visit time, which is also the score Si. The starting point and the end point of each tour is fixed, which is ...
orman's user avatar
  • 33
1 vote
3 answers
219 views

MIP constraints with chronological ordering

I am using a MIP formulation to decide which dates and locations (i.e. stops) should be chosen for a route that maximizes the total revenue over all chosen stops. My decision variable $X$ is the ...
3Li's user avatar
  • 35
0 votes
2 answers
64 views

ILP constraint conditional on a value of a variable

If $X_{ijklm}$ are Boolean Variables, where $i,j,k,l,m$ range from $1$ to $n$, then write an ILP constraint to ensure that for each value of $k$, either all the $jth$ variables are set to $0$ or all ...
ephemeral's user avatar
  • 897
1 vote
1 answer
88 views

Setting constant values in constraints depending on actual values of variables

We have a set of constraints in an ILP of the following form : $ \gamma (X_{11} + X_{12} + X_{13}) \leq C_1$ where $X_{ij} \in \{0,1\}$ and the value of $\gamma$ is going to depend on the actual value ...
ephemeral's user avatar
  • 897
4 votes
1 answer
356 views

Is Benders decomposition and the L-shaped method the same algorithm?

I've been studying the Benders decomposition method to solve stochastic integer problems. I've also stumbled across papers using a so called L-shaped-algorithm which also divides into master problem ...
Arctic_Skill's user avatar
0 votes
0 answers
69 views

is it possible to improve the solution process of an MILP?

I am trying to optimize a charging station for EVs in matlab with intlinprog, which is connected to a PV-Modul, to an system storage systeme and to the network grid. I am using different Storage ...
tun24's user avatar
  • 11
2 votes
1 answer
501 views

Runtime of LP vs MILP

I was wondering how the run time of an LP and an MILP model compare to each other. I found out that MIPs are NP-hard, where as LPs aren't, but it don't really understand what it means. Does that mean ...
lukdooxb1's user avatar
2 votes
2 answers
377 views

Scheduling to minimize total "wait to start" time

I have a scheduling problem I am trying to work through. As I was outlining the problem, I realized it is probably of a known problem type, but I am unsure of what keywords to search for or what ...
Ike348's user avatar
  • 283
2 votes
1 answer
134 views

Conditional constraints in MILPs

I want to understand how to represent iff constraints in MILPs. For example, I want to represent the following as the constraints of a MILP $$ c = \begin{cases} 1 &\text{if } d \geq e \\ 0 & \...
Anonymous Bunny's user avatar
0 votes
2 answers
65 views

Solving a VRP variant with time constraints

I am trying to solve a VRP variant where I have a list of vehicles. If a vehicle is used/rented, a cost will be incurred. If not, there will be no cost. And even if a vehicle is rented, it can only be ...
Shibaprasad's user avatar
3 votes
1 answer
135 views

Meaning of the domain propagation in the context of mixed-integer programming

In the literature, domain propagation defines the process of inferring sequences of local domain reductions at the current node of the branch-and-bound tree. The goal is to shrink the size of the ...
A.Omidi's user avatar
  • 8,642
0 votes
2 answers
109 views

Assignment problem with multiple precedence constraints

Objective and short problem description The objective is to load as many passenger vehicles as possible on an auto-train. The train consists of multiple wagons with two levels each. The wagons are ...
Christian's user avatar
0 votes
1 answer
62 views

Min-convex function as constraint

I have a constraint that is as follows: $$ Ax - f(x) \leq 0 $$ where $f(x)=min_y(g(x,y))$. Which is convex. I can even get the gradient in $x$. How can I reformulate my constraint? or what ...
orpanter's user avatar
  • 517
1 vote
2 answers
102 views

Modeling of a special form of the precedence constraint

There exists a scheduling problem in which some tasks should be processed on some resources. Additionally, each task needs to be assigned to a specific position on each resource. Let the decision ...
A.Omidi's user avatar
  • 8,642
0 votes
1 answer
133 views

Cplex seems to terminate early as optimal when starting solution polishing

I occasionally see this slightly strange thing happen with cplex where it jumps from a MIP gap of, say 5%, to then reporting the status as optimal. This happens when it starts solution polishing after ...
James's user avatar
  • 9
1 vote
1 answer
77 views

Finding a maximum violated infeasible subset

Given a binary optimization problem of the following form: \begin{align} min\; &cx&\\ &Dx \leq e&\\ &\sum_{i\in S} x_i \leq r(S) &\forall S\in \mathbb{S}\\ &x_i binary &...
Joris Kinable's user avatar
5 votes
2 answers
550 views

What are best practices for translating of non-monetary goals to € in the objective function?

How to translate a non-monetary objectives like satisfaction maximization, co2- reduction, puncuality, on time delivery, .... to € to compare solutions? Example: Lets consider for example a production ...
user3680510's user avatar
  • 3,645

1 2
3
4 5
20