Skip to main content

Questions tagged [mixed-integer-programming]

A mixed-integer programming (MIP) problem is a linear program where some of the decision variables are constrained to take integer values.

Filter by
Sorted by
Tagged with
1 vote
1 answer
33 views

Reformulating Mixed-integer Bilevel program into MINLP

I am working on a problem where I have this Bilevel programming problem: $ Max \quad a+b $ $s.t.\quad \quad \alpha \in \{0, 0.5, 0.8\} $ $\quad \quad \quad \; \ a = min \ \lambda$ $ \quad \quad \; \ ...
Franz Görlich's user avatar
0 votes
0 answers
11 views

Tightening a specific constraint

I would like to know if there exists any way to reformulate the following constraint in which one can relax the binary variable $z_{j,m}$, and the solution still being an integer for that. The ...
A.Omidi's user avatar
  • 137
2 votes
2 answers
35 views

Explanation of multiple constraints from one rule [closed]

I'm trying to understand this case study: https://github.com/DorisRipley/Art-Exhibition-Optimization-A-BIP-Modeling-Approach/blob/main/Art%20Exhibition%20Optimization.pdf and I'm having trouble with ...
Sergio Morales's user avatar
1 vote
1 answer
30 views

Find the optimal solutions to a system of linear equations?

I have a linear optimization problem $\mathbf{A}\cdot \mathbf{x} < \mathbf{0}$, where $\mathbf{A}$ is a particular square matrix for my application, and $\mathbf{x} \geq \mathbf{0}$. I want to ...
user326210's user avatar
  • 17.5k
0 votes
0 answers
17 views

Mixed integer linear programming - connection of a directed graph

I am doing a simple optimization model of a directed graph with one source node and a couple of load nodes. Every load node connected to a source node, sometimes directly and otherwise over another ...
maki_b7's user avatar
1 vote
1 answer
35 views

Trading model - apply fee at specific time point

I am currently developing an energy trading model, where I look a few hours ahead of the current time. This model is runned for several time points (but discretized into hours), namely for $\tau \in T=...
osi41's user avatar
  • 97
0 votes
0 answers
18 views

Rake building through mixed integer programming

I have a problem. I need some helps. I have several coils with weight. I have to load coils on wagons. There are two types of wagons. The capacity of two types of wagons are 64 and 67 respectively. I ...
Manglu's user avatar
  • 580
1 vote
0 answers
38 views

Formulate weight lifting as MILP problem

Consider two variables $x_1$, $x_2$ describing how high a weight is in two succeeding states. I need to minimize effort of lifting the weight, but I don't care about dropping the weight: $\min w\cdot\...
Martin Stránský's user avatar
-1 votes
2 answers
56 views

Identify optimal product size configuration based on historical data and some constraints [closed]

We have historical data for the demand of a product. Product can be demanded in any quantity between 0-1000g and the historical data show the distribution of previous request sizes. We can only pack ...
user896201's user avatar
0 votes
0 answers
20 views

Feasible set formed by exclusion of two convex sets

I'm working on an optimal control problem which is almost entirely composed by elements of a quadratic programming problem. The decision variable is $u \in \mathbb{U} \subseteq \mathbb{R}^2$, where $\...
Lucca's user avatar
  • 1
0 votes
0 answers
13 views

Are there any theorems about the existence of feasible solutions to the Mixed-Integer Nonlinear Programming (MINLP) problem?

I am just wondering if there are any theorems about the existence of feasible solutions to the Mixed-Integer Nonlinear Programming (MINLP) problem. For example: Theorems about sufficient conditions ...
Shujun Tan's user avatar
2 votes
1 answer
53 views

Tractable formulation of a mixed integer program

Given constant matrices $A_1\in\mathbb{R}^{1\times l}$ and $A_2\in\mathbb{R}^{1\times l}$, and constants $b_i$, $i=1,\dots,n$. Consider the following mixed integer program (MIP) with decision ...
Jeremy's user avatar
  • 59
1 vote
2 answers
41 views

Formulating a linear programming/optimization problem with a "soft" constraint

I have an optimization problem which I hope I can formulate as a linear program. The problem involves a vector $x$ of binary decision variables (so each entry of the $x$-vector is either $0$ or $1$). ...
NiZ's user avatar
  • 13
1 vote
1 answer
41 views

Task Assignment Problem using MILP (tasks >> agents)

I have a general assignment problem that assigns a set of payload tasks $T$ to a set of workers $A$, where $|T|$ >> $|A|$. Each task $T_i \in T$ consists of a tuple $(s_i, g_i)$, which represent ...
3690219115's user avatar
2 votes
1 answer
88 views

Mixed linear programming: why is big-M needed to set a variable to the max of other variables?

Let's say I want to set a variable $z$ to the maximum of other variables. We'll assume that the objective function is not of help, that is, the objective function doesn't try to minimize the maximum. ...
StefanoTrv's user avatar
1 vote
1 answer
98 views

Non-linear optimization programming, with step function in constraint

I want to optimize a non-linear function $f(x)$, $f: \mathcal{R}^{n} \to \mathcal{R}$ (being a log-likelihood over $m$ observations, i.e. $i$ being the observation index) under constraints numerically,...
Seb L's user avatar
  • 25
0 votes
0 answers
39 views

Python Native Implementation of Mixed Integer Linear Programming

Is it possible to have pure Python implementation of Mixed Integer Linear Programming, something similar to mip, pulp, cvxpy, etc. - but such simple as https://github.com/ispaneli/lippy - it is ...
Kamil Islamov's user avatar
0 votes
0 answers
20 views

Proof of solvable constrained optimization with a subset of a larger set of constraints

Way out of my comfort zone here so apologies if I'm not providing enough or correct information. I work with an application of constrained optimization to assemble test forms (automated test assembly)....
Jon's user avatar
  • 101
0 votes
1 answer
58 views

How can linear programming condition check if variable is a multiple of number?

Let's say we have linear programming problem with x1 and x2 variables. Maximize x1 + x2 where (for example) 0.3x1 + 0.7x2 <= 2 0.2x1 + 0.3x2 <= 3 How can be added one more condition, so linear ...
Kamil Islamov's user avatar
-1 votes
1 answer
100 views

How to linearize a max function in a constraint? [closed]

I have linear program that has constraint as follows: $ \max(x,y) \geq 0 $ where $x$ and $y$ are variables. How to linearize this inequality? How to write this constraints in google or tools?
edhi wiyoto's user avatar
2 votes
0 answers
22 views

Vector simultaneous containment problem

Given a matrix $A\in\mathbb{R}^{n \times k}$, with rows $a_1,\dots,a_n \in \mathbb{R}^k$, I want to find vectors $\ell,u\in\mathbb{R}^k$ such that: The (elementwise) inequality $\ell \le a_i \le u$ ...
nth's user avatar
  • 443
2 votes
0 answers
125 views

How many hexagons to fill a square tile

I am filling a square tile of width wTile with equal hexagons stacked flat side on top of each other at an angle I call colourAngle as shown in the diagram. I call the rows of hexagons "Perp Line&...
Michael McLaughlin's user avatar
0 votes
1 answer
38 views

Mutual exclusivity variables in mixed integer programming problems

I am working on a employee scheduling problems (assigning shifts to temporary workers) by modeling it as a MIP. There is a one shift per day constraint for the employees that restricts more than one ...
SDC's user avatar
  • 1
0 votes
0 answers
22 views

Do linear optimization problems with some infinite coefficients have convex solution spaces?

I am working with an integer linear optimization problem of the form Find $\vec{x}$ such that $\mathbf{A}\vec{x} < 0$ and such that the sum of the entries of $\vec{x}$ is as small as possible. ...
user326210's user avatar
  • 17.5k
0 votes
1 answer
43 views

Does this linear integer optimization problem have a unique antichain of solutions?

I am working with an integer linear optimization problem which, abstractly, is: Find $\vec{x}$ such that $\mathbf{A}\cdot \vec{x} \leq -1$, and such that the sum of the entries of $\vec{x}$ is as ...
user326210's user avatar
  • 17.5k
1 vote
1 answer
53 views

Indicator function with multiple conditions in optimization

I have the following problem $$\begin{align*} & \min \ f(X) \newline & X = \begin{cases} 1&; x_1 \leq c_1, x_2 \leq c_2, x_3 \leq c_3, \newline 0&; \text{otherwise}. \end{cases} \...
Cherryblossoms's user avatar
1 vote
0 answers
22 views

Convert a MINLP problem with semi-continuous variables to a problem with continuous variables?

Is there a way do (approximately) convert a nonlinear optimization problem with semi-continuous design variables to a problem with continuous variables? I want to avoid the use of MINLP solvers and ...
jstollberg's user avatar
0 votes
1 answer
71 views

How to linearize or formulate optimization constraints that are stated in terms of "if-then" sentence?

I am a engineer who is working on an optimization problem and my constraints are in the form of this statement "if $x_1=1$ then $d_1=1T$" where $T$ is just a given time period. Scenario 1 ...
Tuong Nguyen Minh's user avatar
3 votes
0 answers
72 views

Column generation when number of rows depend on number of columns.

Say I have the following optimization problem: $$ \begin{align} \textrm{minimize } & \sum_{p\in P}{c_p \lambda_p} \\ \textrm{s.t. } & \lambda_{p_1} + \lambda_{p_2} \leq 1, \forall p_1,p_2 \in ...
mvc's user avatar
  • 159
1 vote
0 answers
14 views

The facet-defining inequalities for a single resource scheduling problem

Suppose, there exists a scheduling problem $S$, in this case a single resource, with the following descriptions: $$ \text{conv(S)} = \{x \in \mathbb{R}^n \ | \ \forall \lambda_{i} \in \mathbb{R}^{n+}, ...
A.Omidi's user avatar
  • 137
0 votes
1 answer
53 views

SDP relaxation of mixed-integer nonlinear program

I am having trouble understanding the semidefinite programming (SDP) relaxation of a mixed-integer nonlinear program (MINLP) from section 3 of this paper. The optimization problem in MINLP form is \...
Physics Penguin's user avatar
2 votes
3 answers
62 views

Maximize sum of absolute values over a box set

I am interested in the following linear problem: $$ \begin{array}{cl} \max & |a_{11} x_1 + a_{12} x_2| + |a_{21} x_1 + a_{22} x_2| \\ \mathrm{s.t.} & 0 \leq x_1 \leq b_1 \\ & 0 \leq x_2 \...
Eason Mao's user avatar
1 vote
1 answer
57 views

Constraint formulation for variable cleaning times - MILP optimization

I have a Mixed Integer Linear Problem where I want to schedule the production of different orders ($O$) in which in each order, there is only one product ($P$) produced. Each order can be produced ...
Ignacio Aristimuño's user avatar
0 votes
1 answer
55 views

How to apply integer cut to a simple MILP?

I'm self-studying on cutting plane methods, and I'm reviewing the following problem from Bertsimas' book (see below). I know what cutting plane methods do, and how they eliminate infeasible solutions ...
somewhere's user avatar
0 votes
1 answer
88 views

MILP to LP; is it possible?

There is a machine that can produce $x_t \in [0, \overline x]$ quantities of a good in hour $t \in T = \{1, 2, \ldots, 8760\}$. The production of a unit has linear costs of $k_t \in \mathbb R_+$. The ...
clueless's user avatar
  • 771
2 votes
0 answers
95 views

MILP constraint for connected node selection

I am formulating constraints for a network as shown in Figure . Blue circles represent a set of nodes, $N = \{1, 2, \ldots, 5\}$. Three different types of devices are connected to different nodes in ...
bsha's user avatar
  • 41
0 votes
0 answers
27 views

Maximizing the summation of reward of some users (waiting in different positions and lines) using reinforcement learning or other learning methods

There is a mathematical problem that I think can be solved using reinforcement learning and it would be great if you could help me with it. Some users are standing in some lines. There are N lines. In ...
MHB's user avatar
  • 1
0 votes
1 answer
74 views

How to write if statement for 3 dimensional problem linear programming

I have a problem regarding formulating the following with math notation. My goal is that if shop i’s arrival time is lower than all the other shop’s arrival times, then shop i must be allocated to the ...
Alexander Strarup's user avatar
1 vote
2 answers
311 views

Can I linearize this piecewise function so it can be used in an objective function for my LP optimization model?

Thanks for taking the time to read this. I am looking for methods to linearize this piecewise function so that it can be added to an optimization function of a linear programming problem. I figured ...
pennydreams's user avatar
0 votes
1 answer
43 views

What is the convex hull of nonconvex polytopes defined by mixed integer linear inequalities (with only binaries)

Define $$S=\{(x_1,x_2,y)|0\le x_1\le y\overline{x},0\le x_2\le (1-y)\overline{x},x_1,x_2\in\mathbb{R},y\in\{0,1\}\},$$ $\operatorname{conv}(S)$ is the convex hull of $S$. $\le$ is componentwise. $\...
Ruihao Wang's user avatar
1 vote
0 answers
39 views

What is the name of this type of network flow problem?

I encountered a specific type of network flow problem, and I want to know if this type of problem has already been studied before. However, I have been unable to find relevant literature because I don'...
Bosnicht's user avatar
0 votes
2 answers
53 views

Integer or mix integer objective function

I'm a beginner in the maths field, however, I have read the classification of optimization problems yet I have a quick question regarding the problem type, so I have the following objectives `obj_1=...
Shane's user avatar
  • 111
1 vote
2 answers
73 views

CNF form of the logical $atleast(b) x_{i,k}$

Suppose there exists the following logical expression: $$(\sum_{i=1}^I x_{(i,k)} \leq b) \implies (z_{(j,k)}=1) \quad \forall j \in J, k \in K \tag{1}$$ where all of variables, $x_{(i,k)}$ and $z_{(j,...
A.Omidi's user avatar
  • 137
1 vote
2 answers
153 views

Max condition in Integer programming and MILP

Assume you have 2 binary variables $b$ and $c$. Suppose you want another binary variable, $a$ to be $\max(b,c)$ always. How would you represent this in the constraints of an integer program or of a ...
Anonymous Bunny's user avatar
0 votes
0 answers
25 views

Modeling of a special form of the precedence constraint

Crossposted at Operations Research SE 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 ...
A.Omidi's user avatar
  • 137
1 vote
1 answer
310 views

Linearization of constraint in linear programming

I have the following decision variables: $x$, which is binary, and $a, b, c > 0$, which are continuous. I would like to express in linear form for a linear programming model the following ...
E-O's user avatar
  • 99
1 vote
1 answer
43 views

Formulating a particular constraint

I have a problem setting similar to bin packing but not exactly. I have to put the few boxes of certain dimensions in a square area besides each other. Like a grid. The boxes should be placed around ...
Ken Adams's user avatar
1 vote
1 answer
148 views

The optimal solution of a relaxation is optimal for the original problem

The question concerns the topic of relaxations in optimization problems. Moreover, proving the following, straightforward proposition. Let $z^P$ be the optimal solution for the problem $P$, $z^R$ be ...
DrDrunkenstein's user avatar
-1 votes
1 answer
71 views

What set of crops provide a complete diet? [closed]

I'm trying to find what combination and quantity of crops I should grow to provide a complete diet. Basically, I have a set of n possible crops that I can grow, and I have m nutritional requirements. ...
Travis's user avatar
  • 101
1 vote
1 answer
181 views

MILP constraints for connectivity in a subgraph

I have an MILP problem where I have to choose a set of vertices 'm' from complete set of vertices such that all the 'm' vertices are connected. Assume there are a set of vertices numbered 1...n. Out ...
DKumar's user avatar
  • 13

1
2 3 4 5
9