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
6
votes
1answer
168 views

What is the performance improvement when using semi-continuous variables instead of binary + continuous variable pair?

I have a MILP model that solves a master production schedule including capacity decisions. In the model I have a production quantity that should either be 0 or at least the amount that can be produced ...
3
votes
1answer
80 views

How do I interpret the CPLEX Optimization Studio MIP gap output?

I'm having difficulties understanding my FlowControl output compared to what the Engine Log shows me. My output from the FlowControl into the Scripting Log (yellow marks) is ...
3
votes
2answers
89 views

Relaxation and complexity of two formulations

I have two different MILP formulations for the same scheduling problem with the same complexity but with different running times. Why it is recommended to compare the relaxed versions of each ...
5
votes
1answer
159 views
+50

Multi-period linear dynamic programming with differing in-period dependencies and changes

I’m not sure if I’m wording this right but in a nutshell, my problem is: I’m modelling potential actions a boat owner can do to their boat. Let’s say he wants to know over the 50 year lifespan of the ...
3
votes
1answer
67 views

confusing results of two models with different complexity

i have two models that address the same problem. the first one is : the second one is: for different instances for the same size (n=30) i found the following results ( the first column on the left ...
2
votes
1answer
53 views

MIP for assigning tasks with prerequisite tasks

I have a modified assignment problem for which I'm having difficulty formulating the constraints mathematically. I have a set of workers and a set of tasks which should be completed in the minimum ...
5
votes
1answer
225 views

Can GLPK be used to solve an optimal team selection problem?

My Problem I am quite new to optimisation, so any advice is appreciated. I am currently trying to solve a problem as follows: Given a pool of people, we want to create n teams such to find the optimal ...
4
votes
2answers
71 views

Benders subproblem with product of continuous and discrete variables

I am trying to solve the following problem. The decisions in the problem are $x, y, v, $ and $W$, where $x, y$ are binary and $v, W$ are continuous variables. \begin{equation}\label{eq:3} \begin{...
6
votes
1answer
89 views

Does the weighted sum approach find all pareto-optimal solutions in MILP

I use the weighted sum approach for a multiobjective optimization problem that is formulated as a MILP. This means that the objective function is linear. I read quite often that the weighted sum ...
1
vote
1answer
63 views

A discrete location problem

I have a discrete optimization problem in which there are some predetermined nodes in the set A. a vehicle must visit them as the traveling salesman problem. there are some other nodes in the set B ...
2
votes
0answers
63 views

Indicator function for integer variable with inequality constraint

I have $n$ integer variables $\vec{x}$ with the following integer programming problem. $$ COST = \sum^{n-1}_{i = 0} a_i x_i + \sum^{n-1}_{j=0} b_j I(x_j > 0) $$ Here, $a_i, b_j \in \mathbb{R}_+$ ...
3
votes
1answer
136 views

Issue in solving a large scale MIQP problem

I am solving a large scale MIQP optimisation problem at each step of a model predictive control problem. The problem description is as below. \begin{align} \min_{u} \quad (x_{k}&-x_\text{ref})^{T}...
2
votes
1answer
35 views

Portfolio optimization with indicator function constraints in Cvxpy

I have the following portfolio optimization problem that I want to solve using Cvxpy: However I am having troubles implementing the last constraint involving an indicator function. Any ideas on how ...
2
votes
0answers
78 views

Condition for an integer program and its linear relaxation to have the same value

Let $A$ be a $(0,1)$-matrix where no row or column is a zero vector, and consider the following optimization programs \begin{align}(1):\min&\quad y\cdot1\\\text{s.t.}&\quad yA\ge w\\&\quad ...
1
vote
1answer
53 views

Issues modeling portfolio optimization with rebalancing in gurobipy

I want to solve the following portfolio optimization problem by means of the Python API of Gurobi: I have implemented the problem in the following code: ...
1
vote
0answers
32 views

Interger programming using gray encoding

Could anyone suggest me a tool or library which takes an integer programming problem written in DOCPLEX or CVXPY as input and outputs the equivalent problem using Gray binary encoding? I am happy to ...
1
vote
2answers
121 views

Formulate a problem as Mixed Linear Programming problem

I need to formulate the following problem as a Mixed Integer Linear Programming problem A farmer needs to establish a 17-year business plan where he will decide when to sell or buy a new truck. The ...
2
votes
2answers
190 views

Does it make sense to use a MILP solver for a scheduling problem but without the obligation to schedule all the tasks?

I know that MILP solvers are bad with scheduling problems. However, if we are allowed to keep unscheduled some tasks (i.e a solution with 0 scheduled tasks is a feasible solution but we add the ...
2
votes
2answers
322 views

How can I identify the reason that makes a MILP model hard for solvers such as CPLEX?

I'm solving a MILP model whose native lower bound (via linear relaxation) is very poor. We could provide a lower bound by providing a given value (derived based on the problem itself). I know that ...
6
votes
4answers
719 views

Can this be formulated as one inequality

I have two binary variables $x_1$ and $x_2$ and a non-negative continuous variable $y$. In addition, I have the following two parameters $u>q>0$. I would like to formulate the following ...
2
votes
1answer
58 views

distance specific constraint

I have some points with determined coordinates $(a_i,b_i)$. A vehicle can move between these points based on rectangular distance. In more detail, we consider that the path between points is an ...
-1
votes
2answers
137 views

How to model y = floor(x)

I went through this question Modeling floor function exactly but I still do not get how to model y = floor(x) Is that question answered and I just do not see it?
1
vote
2answers
78 views

How this problem can be defined as MultiObjective optimisation

I need to optimize the end-to-end latency of a multi-component application. Assuming that the application has 10 components, component 1-5 is hosted by device 1, and device 2 is hosting the other 5 ...
0
votes
0answers
57 views

Benders Decomposition Problem

$$r_{m_h,s}(n)=\frac B{m_hb_\ell s}\log_2(1+\gamma_{m_h,s}(n))$$ How to deal with multiple subproblems in Benders decomposition when the original objective function is in product form of an integer ...
3
votes
3answers
98 views

How to write distance specific constraint?

Suppose there are a few plants (p) and few customers (c). The supply (Sp), distance (Dpc), cost (COSTpc) and demand (DEMANDc) between them is given. I have a constraint that 90% of total demand of all ...
4
votes
3answers
195 views

How to linearize the Min function while letting the binary variable to be fixed for x1==x2 as well?

As discussed here, the min function, i.e $X = \min\{x_1,x_2\}$, can be linearized as follows: \begin{align} X & \le x_1 \\ X & \le x_2 \\ X & \ge x_1 - ...
2
votes
1answer
111 views

Is my formulation correct and how to formulate this IF-THEN constraint?

I have system with $N_U$ users and $N_T$ transmitters. Multiple transmitters can transmit to a single users and one transmitter can transmit to many users, i.e., two sets of transmitters serving two ...
4
votes
1answer
88 views

Formulating these logical constraint in an ILP

I have these two constraints : $z \leq My$ $t \leq M'y $ where $z$ and $t$ are two integer variables $ z, t\geq 0$, $y$ is a binary variable, and $M$, $M'$ are two big numbers. So basically these ...
1
vote
1answer
88 views

How can I have minimum amount of resources wasted in this resource allocation problem?

I have a demand, $d$ I also have supply from 1000 sources. The supplies from those $N$ (for example, $N=1000$) sources are given by $s_1,s_2,s_3,\cdots,s_N$. So,the total supply is : $s_1+s_2+\cdots+...
3
votes
1answer
276 views

Branch and Price Algorithm

Can branch and price be a good solution approach for a routing problem with min-max objective function? For example, minimizing the max length of any vehicle route in a VRP. In the literature, I haven'...
3
votes
1answer
108 views

Semi continuous constraints in CPLEX Python

I have a semi-continuous optimization problem reformulated as a MIQP optimization problem. My objective has a quadratic form $x^{T}Qx$ and my $x_{i}$ are such as $x_{i} \in [m,M] \cup \{0\}$. ...
1
vote
1answer
204 views

Mixed integer quadratic programming (MIQP) in CVXPY

There's something I don't understand about CVXPY's example on its MIQP use. It says that the algorithm returns a solution $x \in \mathbb{Z}^n$ but I thought in general the point of MIQP algorithms was ...
6
votes
1answer
146 views

Strong MIP formulations for a large-scale mixed-integer nonlinear feasibility problem

I'm trying to construct a strong MIP formulation for the following integer nonlinear feasibility problem. Informally: We have a $m \times n$ decision matrix of binary variables Each row of the matrix ...
12
votes
2answers
416 views

How to handle an IP sub-problem with an objective function in Benders Decomposition

I have a question on Benders Decomposition (BD). Suppose I have an MILP model which can be decomposed into a master problem (MP) including integer and continuous variables and a subproblem (SP) ...
3
votes
2answers
212 views

How to formulate this problem?

I have a matrix in the size of $S \in \mathbb{R}^{M\times N}$ with only binary values $0..1$. I want to select $m<M$ rows from $S$ and sum the $m$ rows to get a new vector $v$. I wish $v$ to be ...
4
votes
1answer
123 views

Column Generation algorithm

I want to solve a VRP with a column generation algorithm. The objective of the problem is makespan minimization. but there is a point in calculating the arrival time of the vehicle in each node. the ...
3
votes
1answer
33 views

How can I change decision variable type in Concert Technologies (with Java)

I have a MILP model with continuous variables ($y_{ij}$) and binaries ($x_{ij}$). I am using Java and cplex 12.8 for implementation. Is there a way by which - using the Java-cplex API - I would be ...
3
votes
1answer
91 views

Logical constraint in ILP

I want to write the following constraint: Let $z$ be an integer variable such that $0\le z\le M$, and $t$ be a binary variable where $M$ denotes big-M. The logical constraint is as follows: if $z \...
3
votes
1answer
108 views

How to express this logical constraint for an ILP?

I am trying to write an ILP for a problem but I have this logical constraint and I'm stuck. In my model I have: two binary variables: $x$ and $y$ One Integer variable: $z$ The logical constraint I am ...
3
votes
1answer
89 views

A Question on A tutorial on column generation and branch-and-price for vehicle routing problems by Dominique Feillet

I am reading A tutorial on column generation and branch-and-price for vehicle routing problems by Dominique Feillet to learn the column generation approach, but I have a problem. in section 3.3 ...
5
votes
1answer
181 views

Column Generation algorithm for vehicle routing problem

I want to solve a VRP with a column generation algorithm. The objective of the problem is makespan minimization. In more detail, I want to minimize the arrival time of the last vehicle in the depot. I ...
4
votes
1answer
182 views

Best way to solve an allocation problem

I have the following problem: I have products with different attributes (price, weight, category) and I have a list of clients. Every client has an "affinity value" with every product, the ...
-2
votes
1answer
165 views

Optimized Production Planning & Scheduling

I want to create an optimized schedule and production to meet demand of four different buyers. I am starting with Pulp but not able to account for continuous production variable and discrete dispatch ...
5
votes
0answers
69 views

Are there any good models for min-max vehicle routing problem?

I am trying to model a min-max VRP problem with multiple delivery vehicles and I have come up with a model using branch and cut but I do not think it is strong enough as it takes lot of time to ...
4
votes
1answer
126 views

Mixed integer programming vs Constraint programming

I see that certain studies are comparing MIP and constraint programming (CP) performances. And generally, they claim that CP outperforms MIP. But I believe that it is not completely true. Because ...
2
votes
1answer
99 views

Scenario based approach to value-at-risk optimization using mixed-integer programming

For a discrete set of scenarios, minimising value at risk can be formulated as a mixed integer linear programming problem. If each scenario has equal probability then this can be written as \begin{...
4
votes
1answer
147 views

Column generation when intractable variables appear in the objective function

Is it possible to implement a column generation for a problem that the variables in the "complicating" constraint appear in the objective function? Suppose the MIP is: \begin{align} z = \...
2
votes
0answers
67 views

Finding Optimal Route using different Paths

I have a list of paths e.g. path 1 takes you from point A to B. A person needs to complete 5 of such paths. $$Route1 = path1 + ...
2
votes
1answer
99 views

Is a convex or MILP (without big-M) formulation possible for this problem

Assume we are given a directed acyclic graph (DAG) $G(V, A)$, where $|V| = n, |A| = m$, and the graph contains a source node $\mathbf{s}$ (i.e. every node in $V \backslash \mathbf{s}$ is connected by ...
8
votes
2answers
108 views

(Iterative?) Solutions to a certain quadratic program with non-convex constraints

Let $y\in\mathbb{R}^m$, $\tau\in\mathbb{R}$ and $X\in\mathbb{R}^{m\times n}$, with $\tau>0$ I would like to efficiently solve the following problem: Problem 1 Choose $\alpha,z\in\mathbb{R}^m,\beta\...

1
2 3 4 5 6