Skip to main content

Questions tagged [linear-programming]

For questions related to problems that optimize (i.e., minimize or maximize) a linear objective subject to linear constraints.

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

Optimal way to formulate a piecewise linear function

I am working on LP problem whose objective function includes a piecewise linear function. I would like to figure out the optimal way to formulate the piecewise linear function in order to minimize the ...
Apostolos's user avatar
3 votes
1 answer
62 views

Enforcing Order in a Linear Programming Question

I have an optimization model to fulfill the water requirements of a city's distribution network. The model includes water sources from rainfall collection, river extraction, reservoir storage, and ...
snek's user avatar
  • 31
1 vote
1 answer
38 views

Multi-Commodity Flow with "group edges"

I'm currently working on a special variation of the Multi-Commodity flow problem. My goal is to solve this variation via column generation, because the graph can become very large. Description Given......
jatsqi's user avatar
  • 13
1 vote
2 answers
151 views

My Professor couldn't complete the model for this optimization problem. how do i model this problem?

(Edit: there was a slight translation error, to be clear, we tried this since the start with Binary variables (IP), even then we couldn't crack it) I'm an undergraduate in Industrial Engineering and ...
Eduardo Gehrs's user avatar
0 votes
1 answer
65 views

How to write conditional constraints and sum the result in Linear Programming in Python?

I want to use the sum of a series of linear expressions as objective and constraints. These linear expressions are chosen to be included or not based on some conditions. I can achieve it in Excel ...
Shwing's user avatar
  • 13
1 vote
0 answers
57 views

Integrality gap vs Gurobi Gap

I was wondering what the difference is between the integrality gap (i.e. best known solution in relation to the LP relaxation) and the gap from the MIP solver from Gurobi, for example. As I understand ...
ornewbie's user avatar
0 votes
0 answers
46 views

Need help for the python scheduling code

I'm working on a Python application using PuLP for optimization, and I'm having trouble ensuring that only one material is produced on a given day. The constraint prob += pulp.lpSum(production_flag[m][...
Beau Ryan's user avatar
1 vote
0 answers
45 views

How to set up the master and subproblem

I have the following question. I have a classical scheduling model with the following constraints: Demand coverage One shift per day Minimum and maximum number of consecutive working days Forward ...
marvelfab12's user avatar
6 votes
2 answers
1k views

Multiple Travelling Salesmen - How to make the second slowest salesman matter?

I'm building a Mixed Integer Linear Program for a variant of TSP I'm dealing with, where there are multiple salesmen. The way I have formulated the problem is that each agent has a time variable $T_i$ ...
John Smith's user avatar
2 votes
1 answer
36 views

How to generate random bounded polytope by MATLAB defined by Ax=b, x≥0

How can one create a random bounded polytope in MATLAB, specified by the conditions $‎\lbrace‎x:~ Ax = b,~ x \geq 0‎\rbrace‎$
Optimization Online's user avatar
1 vote
0 answers
72 views

Solve scheduling model using a greedy heurisitc

I have the following scheduling problem. Relatively simple and not very complex (only serves as an example). The indexes are $I$ worker, $T$ days and $J$ shift. The decision variable is $x_{ijt}$, ...
Uni ewr's user avatar
  • 71
1 vote
2 answers
67 views

Best approach to initialize column generation

I was wondering what the typical approaches are for generating an initial solution for the first column in a COlumn Generation approach and which usually work best and are easiest to implement (Gurobi)...
nflgreaternba's user avatar
0 votes
1 answer
69 views

Adopt constraint formulation

I have this constraint which ensures that there are at least $F$ consecutive days off. F.e. for $F=2$, an 1-0-1 is prevented. $$1+y_{it}\ge y_{i(t-1)}+y_{ik}~\forall i\in I, t\in\left\{ 2,\ldots,T- {F}...
Karl Seidl's user avatar
0 votes
1 answer
66 views

Inconsistencies in modeling a binary variable that indicates a switch

this is a follow-up question to this post here and to @RobPratt's answer. I have implemented the whole thing, and now it happened that on day 1 the machine did not run and was only used for the first ...
marvelfab12's user avatar
1 vote
0 answers
73 views

Surrogate metric for Linear Program problem

I am working on a constrained optimization problem modeled as a Mixed-Integer Linear Program, $\textrm{argmax}_x c \cdot x \hspace{3mm}$ such that $\hspace{3mm} Ax \leq b \hspace{5mm}$ (1) . ...
user810643's user avatar
2 votes
2 answers
174 views

Are McCormick Envelopes exact for the following class of optimization problems?

I have the following optimization problem: \begin{align*} \text{minimize} \quad &\mathbf{c^T x} \\ \text{such that} \quad &\mathbf{x} \in S. \end{align*} Here, $S$ is a polyhedron of the form $...
graphtheory123's user avatar
8 votes
1 answer
1k views

Why do I get a binary solution even when I solve an LP problem with continuous variables?

I have a MILP in the following form maximize $${\bf c}^T{\bf x}$$ subject to $${\bf Ax}\le {\bf b}$$ Matrix ${\bf A}$ is a binary matrix, and very sparse. It is a larger matrix with 300 rows and 1000 ...
KGM's user avatar
  • 2,377
2 votes
2 answers
87 views

Optimizing calls to a separation problem in branch and cut

I have a MIP in which I am able to generate cuts at intermediate relaxation solutions using the context class. These cuts are derived from a separation problem. However, after adding them, the code ...
tr244's user avatar
  • 21
2 votes
1 answer
75 views

Minimizing sum(abs(Ax-c)) for binary decision variables - terminology and methods?

My problem requires choosing a fixed number of vectors from a large set of vectors such that the sum of these vectors is close to some known target vector. That is, given known parameters: $$ l, m, n \...
G_B's user avatar
  • 1,857
-1 votes
0 answers
40 views

Optimize model notation

I have slightly rephrased the old question nine. I have this constraint. $\alpha, \beta, \delta$ are positive integers, and $I$ and $ T$ are the indices. $$1+x_{it}\ge x_{i(t-1)}+x_{is} \forall i\...
Derd Cff's user avatar
0 votes
2 answers
100 views

Combine two constraints into one

I have these two constraints, where the indices are $i$ person, $j$ shift and $t$, the day. $x_{ijt}$ is the shift assignment, $m_{ijt}$ the motivation of the person in a shift (only takes values $m_{...
nflgreaternba's user avatar
2 votes
1 answer
219 views

Set a limit on value change of a binary variable

I am working on an Energy Management problem. The objective is to minimize the electricity bill for the customer. I have a time-series data with 15 min. intervals spanning the course of 1 year. The ...
Kushagr Goyal's user avatar
2 votes
0 answers
50 views

Using BigM and auxiliary variable to linearise model leads to incorrect results

I am working on a Pyomo optimization model that aims to select the cheapest fuel for production at different facilities over several time periods. The model should select Mode1 for Tech1 when Fuel1 is ...
Jamie Bull's user avatar
3 votes
1 answer
104 views

Restrict the number of non-zero variables to any constant in MILP

I am designing an MILP in which given a set $[n]$ of $n$ agents, we create for each $i \in [n]$ a real variable $x_i$. The variables $x_i$ are between 0 and 1 ($0 \leq x_i < 1$). I would like to ...
Samuel Bismuth's user avatar
1 vote
1 answer
71 views

How to compare models?

I have the following problem. I have a staff scheduling model that explicitly considers employee motivation in the modeling (this is modeled by additional constraints that sum up the number of ...
nflgreaternba's user avatar
0 votes
0 answers
55 views

Linear sum assignment, but with ranked assignments?

Let's say I have 5 tasks that I have to assign to 5 agents, with a cost matrix: ...
Dan's user avatar
  • 1
1 vote
1 answer
94 views

Conditional binary programming

I am currently trying to model the relationship that if the binary variables $b_{it}=0$ and $c_{it}=1$, and for the integer non-negative variable $b^{n}_{i(t-1)}=0$, then the new binary variable $a_{...
mingabua's user avatar
0 votes
0 answers
37 views

Scheduling categories of jobs with completion time requirements

Consider a discrete time slotted, system with two categories of jobs $J_1$ and $J_2$, where each job from the category $J_1$ has completion time requirement of $C_1$ and the jobs from category $J_2$ ...
ephemeral's user avatar
  • 917
1 vote
1 answer
83 views

Schedule monotony constraints

Suppose I have a model for creating a nurse's duty roster. The model has the indices $i$ for the person, $t$ for the day and $s$ for the shift. I have the binary variable $x_{its}$ which indicates ...
manofthousandnames's user avatar
1 vote
0 answers
97 views

Knapsack problem - reducing the number of decision variables

I am trying to solve something similar to a knapsack problem: $$\max \sum v_{n}P_{n}$$ subject to some basic weight constraints. However, what makes this problem difficult to solve is that $P_{n}$ is ...
BenBernke's user avatar
  • 185
1 vote
1 answer
87 views

Help modeling linear constraints

I have the following variables and indices. I have $y_{ijk} \in [0;1]$ which indicates how performant a machine $i$ is on day $j$ in the interval $k$. The binary variable $z_{ijk}$ indicates whether a ...
mingabua's user avatar
0 votes
1 answer
84 views

Single Machine Job Scheduling With Release Dates and No Idling Constraint

I'm trying to model a linear job scheduling optimisation problem. There is a single machine and N jobs $J_1, J_2, ..., J_N$. Each job consists of one step with processing time $p_1, p_2, ..., p_N$. ...
Ralph Melish's user avatar
1 vote
0 answers
56 views

Does getting the second optimal solution in a general MILP require solving a MILP again?

This general question popped into my mind if finding all optimal solutions takes not much more time than finding just one optimal solution in a MILP why not gettting all of them in Gurobi?
Red shoes's user avatar
  • 153
2 votes
1 answer
122 views

How to model the constraints of min and max in cvxpy

I have a continuous variable $x_{ij}\in[0,1]$ and I need to write the following constraint: $$M_i-m_i+1\leq C_i$$ where $M_i=\max\{j: x_{ij}>0\}$ and $m_i=\min\{j: x_{ij}>0\}$
zdm's user avatar
  • 403
1 vote
1 answer
126 views

Graphical understanding of the primal and dual problem

I have a relatively simple question. Assuming we have a simple numerical example of an LP with two decision variables and two constraints (non-negativity excluded), how can I visualize the graphical ...
Derd Cff's user avatar
2 votes
2 answers
123 views

Deriving linear constraints from logical notation

I have the following two logical implications. $x_{it}$ and $y_{it}$ are binary, $N$ is an integer number. $i$ and $k$ are indexes. $$\sum_{k=1}^{t}x_{ik}\ge N~\implies y_{it}=1$$ $$\sum_{k=1}^{t}x_{...
manofthousandnames's user avatar
4 votes
2 answers
304 views

Linear condition between two continuous variables

There are two real variables $x$ and $y$. The conditions are such that: if $y\le 0$, then $x=0$ if $y>0$, then $x=y$ How to write linear equations or inequalities to satisfy both the conditions?
Lorentz's user avatar
  • 41
0 votes
1 answer
104 views

How to model this constraint in a better way?

I have a resource allocation problem. There are $M$ users and $N$ resources (machines). One user can be assigned to multiple resources/machines. But maximum $B$ machines can be activated at a time for ...
KGM's user avatar
  • 2,377
1 vote
0 answers
43 views

Primal-dual simplex method for general LP

I've learned the primal-dual method for standard LP, but for a general LP written as \begin{align} \min_{x\in \mathbb{R}^n} ~~~ &c^\top x \\ s.t. ~~& l^{s}\leq Ax \leq u^{s},\\ ...
andy's user avatar
  • 77
0 votes
0 answers
59 views

What's the dual of an LP in its general form?

For an LP written as \begin{align} \min_{x\in \mathbb{R}^n} ~~~ &c^\top x \\ s.t. ~~& l^{s}\leq Ax \leq u^{s},\\ &l^{x}\leq x \leq u^{x} \end{align} how can we get its dual ...
andy's user avatar
  • 77
3 votes
1 answer
194 views

Reformulate constraints

I have the following constraints and am wondering whether I can formulate the whole thing more narrowly and with fewer constraints. $x_{itk}$ is binary and $u_{it}, v_{itk}\in [0,1]$. $M$ is a Big-M ...
manofthousandnames's user avatar
3 votes
1 answer
67 views

What approximation is guarantees when solving an LP with floating-point numbers?

Given a linear program $$\begin{align} \text{maximize} \quad & c^{T}x \\ \text{s.t.} \quad & A x \leq b \end{align} $$ I can solve it exactly in polynomial time, using e.g. interior-point ...
Erel Segal-Halevi's user avatar
1 vote
1 answer
86 views

How to track the first timestep at which a binary variable becomes 1 in an IP? [duplicate]

I have an MIP where I have a binary variable $y_t$ which is set to 1 or 0 and is indexed by time t. It can be set to 1 at multiple timestamps but it is never continuously 1 for more than single ...
Demitri's user avatar
  • 33
1 vote
1 answer
45 views

Converting a function composing of multipe pieces into a linear equation

I have a variable (alpha) which depends on some other binary variables, denoted as X_i. So, for some combination of other variables, alpha may take a value (Beta_j). I added some auxillary variables (...
Sam's user avatar
  • 97
1 vote
1 answer
86 views

How to model $\max\limits_{x\in X} \min\limits_{y\in Y} \max\limits_{z\in Z} f(z)$ as single MILP

I have the following optimization problem: \begin{align*} \max\limits_{x\in X} &\min\limits_{y\in Y} \max\limits_{z\in Z} & f(z) \\ &\text{such that} & (x, y, z)\in P \end{align*} ...
graphtheory123's user avatar
2 votes
1 answer
90 views

Why this ILP and LP are equivalent?

Let's consider a competition with $n$ questions. Each question has a price $p_i$ and a score $v_i$. To advance to the next round of the competition, we need to accumulate a minimum score of $D$. We ...
occasional's user avatar
1 vote
1 answer
95 views

A tool for finding integer solutions to linear systems

I have a system of linear equations $A x = 0$, where $A$ is an integer matrix, and I want to find a non-zero solution, if it exists. In that case, a rational solution exists. Multiplying by the common ...
Erel Segal-Halevi's user avatar
0 votes
0 answers
49 views

Solving convex separable programming problem using interior point method?

In my engineering application, all decision variables are non-negative and everything is convex separable. In addition to that, the only function that I am trying to approximate with grid point are $f(...
Tuong Nguyen Minh's user avatar
1 vote
1 answer
92 views

Economic interpretation of shadow/dual variables in LP

I have recently read a text which deals with the dual variables attached to constraints. In an economic sense, one can interpret them as shadow variables indicating market clearing for resource ...
Marlon Brando's user avatar
4 votes
3 answers
326 views

How to maximize the number of variables with value at least 0?

Given a matrix $A$ and a vector $b$, I would like to find a vector $x$ satisfying the set of linear constraints $A x \leq b$, and subject to that, contains as many variables as possible with ...
Erel Segal-Halevi's user avatar

1
2 3 4 5
17